Propositional Logic and Truth Tables

A proposition is a declarative sentence that is definitely true or definitely false — never both, never neither. "7 is prime" is true; "2 + 2 = 5" is false; "close the door" and "x > 3" are not propositions (one is a command, the other has no fixed truth value until we know x). Propositional logic is the algebra of these true/false atoms — the same true/false thinking you met with statements and conditions, now made fully mechanical.

We label atomic propositions with letters — P, Q, R — and glue them together with connectives to build compound propositions like (P \wedge Q) \rightarrow \neg R. The magic is that the truth of the whole is fixed entirely by the truth of its atoms: logic has no grey areas, so we can compute it. The tool that does the computing exhaustively is the truth table.

A real machine that runs on this

This is not a philosopher's toy — it is literally how computers work. Inside every chip, wires carry a voltage that is high (1) or low (0), and tiny circuits called logic gates combine them: an AND gate outputs 1 only when both inputs are 1, an OR gate when at least one is, a NOT gate flips its input. Stack a few billion of them and you get a processor. When an engineer writes out "for which inputs is this circuit on?", they are writing a truth table. So 1 = \text{true} and 0 = \text{false} is a habit worth keeping.

The five connectives

Almost all of propositional logic is built from five connectives. Learn what each does to true/false inputs and you can read any formula.

Each connective is completely pinned down by what it does on every combination of inputs — and listing every combination is exactly what a truth table is for.

What a truth table is

A truth table for a formula lists every possible assignment of true/false to its atomic propositions, one per row, and records the resulting truth value of the formula. With n distinct atoms there are

2^n \text{ rows}

— one atom gives 2 rows, two atoms 2^2 = 4, three atoms 2^3 = 8, and so on (each new atom doubles the count). Because the list is exhaustive, a truth table settles any question about the formula with zero cleverness required: you just fill it in.

The interactive table below is built the way you would build one by hand. The two left columns list all four true/false combinations of P and Q; the three right columns compute P \wedge Q, P \vee Q, and P \rightarrow Q for each row. Press play (or step through) to reveal the rows one at a time and watch the enumeration fill up. Notice the P \rightarrow Q column: it is true on three of the four rows.

Building a compound table, column by column

For a bigger formula you add one working column per connective and fill it from the inside out, just like evaluating an arithmetic expression. Take \neg P \vee Q. First enumerate P, Q, then compute \neg P, then \vee it with Q:

\begin{array}{cc|c|c} P & Q & \neg P & \neg P \vee Q \\ \hline T & T & F & T \\ T & F & F & F \\ F & T & T & T \\ F & F & T & T \end{array}

Compare that final column with the truth values of P \rightarrow Q (true, false, true, true). They match, row for row. That is not a coincidence — it is a genuine discovery about the connectives, which brings us to equivalence.

Tautology, contradiction, contingency

Read a formula's final column and it falls into exactly one of three types.

Two formulas are logically equivalent, written \equiv, when their truth tables have identical final columns — they agree on every row. Two headline equivalences: Equivalently: P \equiv Q exactly when P \leftrightarrow Q is a tautology.

Equivalence is what lets you rewrite a formula into a simpler or handier form without changing its meaning — the algebra of logic. Verifying one is completely mechanical: build both tables, compare the last columns, done.

Worked example: is De Morgan really an equivalence?

Let us check \neg(P \wedge Q) \equiv \neg P \vee \neg Q by putting both sides in one table. Fill P \wedge Q first, negate it, then separately compute \neg P \vee \neg Q:

\begin{array}{cc|c|c|c} P & Q & P \wedge Q & \neg(P \wedge Q) & \neg P \vee \neg Q \\ \hline T & T & T & F & F \\ T & F & F & T & T \\ F & T & F & T & T \\ F & F & F & T & T \end{array}

The two rightmost columns are identical — F, T, T, T — so the equivalence holds. In words: "not (both P and Q)" says exactly the same thing as "not P, or not Q". That is why negating an "and" turns it into an "or" (and vice versa) — a rule you will use constantly when negating statements in proofs and when simplifying conditions in code.

The single biggest shock in propositional logic is that P \rightarrow Q is true whenever P is false — regardless of Q. Both bottom rows of the P \rightarrow Q column are true. This is called vacuous truth: the promise "if P then Q" is only broken when P happens and Q fails to follow. If P never happens, the promise was never tested, so we count it as kept.

So "if pigs fly, then 2 + 2 = 4" is true, and so is "if pigs fly, then 2 + 2 = 5" — the antecedent is false, so both hold vacuously. And crucially, \rightarrow is not causation: P \rightarrow Q makes no claim that P causes or even relates to Q. It is a pure bookkeeping rule about truth values, nothing more.

In everyday English "or" is slippery. "Coffee or tea?" usually means one or the other, not both — that is exclusive or (XOR). But "students who take Latin or Greek get a badge" clearly means you still get the badge if you take both — that is inclusive or.

Logic and mathematics settle the ambiguity by decree: P \vee Q is always inclusive — true when either or both hold, false only when both fail. Exclusive or gets its own symbol, P \oplus Q, true when the two differ. You can even build it from the basics: P \oplus Q \equiv (P \vee Q) \wedge \neg(P \wedge Q) — check it with a truth table and see the "not both" clause do its job.