1.2 Truth tables and equivalence

This section turns propositional formulas into something we can calculate with. Once the atomic propositions have been fixed, a truth table lets us test a compound statement by checking every possible assignment of truth values.

That may sound mechanical, but the point is mathematical: a truth table is a complete argument. If a formula depends on $n$ proposition variables, then there are exactly $2^n$ possible assignments, so there are no hidden cases once those rows have been checked.

What a truth table records

Definition

Truth table

A truth table for a propositional formula $\varphi$ lists every possible assignment of truth values to the variables in $\varphi$, together with the resulting truth value of $\varphi$ in each case.

For example, if a formula involves only $P$ and $Q$, then there are four rows:

$$(T,T), \quad (T,F), \quad (F,T), \quad (F,F).$$

The truth table is therefore not just a picture. It is an exhaustive case analysis.

A row-by-row construction protocol

A table is reliable only when its rows and columns follow a stated procedure. For $n$ atomic variables, make $2^n$ rows. Keep one row order from the beginning (for three variables, for example, TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF) and use it for every intermediate column. Then add one column per subformula, starting with the innermost connective. A final column written without these checks is not an argument that can be audited.

Worked example

Build $(A ∨ B) → C$ in stages

First compute $A ∨ B$, then use that column as the antecedent of the implication.

$A$	$B$	$C$	$A ∨ B$	$(A ∨ B) → C$
T	T	T	T	T
T	T	F	T	F
T	F	T	T	T
T	F	F	T	F
F	T	T	T	T
F	T	F	T	F
F	F	T	F	T
F	F	F	F	T

The last column is false exactly when the computed antecedent is true and $C$ is false. The table has eight rows because there are three independent variables.

The same discipline handles nested implications. In $A → (B → A)$, calculate the inner $B → A$ first. Its four values, in the two-variable order $TT, TF, FT, FF$, are $T, T, F, T$; the outer implication then has values $T, T, T, T$. The formula is therefore a tautology. Notice that the repeated $A$ is not a reason to skip the inner column: each occurrence has a scope determined by its connective.

A first important equivalence

Worked example

Why $P \to Q$ and $\neg P \lor Q$ say the same thing

Consider the formulas $P \to Q$ and $\neg P \lor Q$.

$P$	$Q$	$\neg P$	$P \to Q$	$\neg P \lor Q$
T	T	F	T	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

The last two columns match in every row.

Therefore

$$P \to Q \equiv \neg P \lor Q.$$

This is one of the most useful equivalences in elementary logic. It explains why an implication fails only in the case "true hypothesis, false conclusion."

Logical equivalence

Definition

Logical equivalence

Two formulas $\varphi$ and $\psi$ are logically equivalent if they have the same truth value under every assignment of their variables. We write

$$\varphi \equiv \psi.$$

Logical equivalence is stronger than saying that two formulas happen to agree in one example. It means they define the same truth function.

Do not confuse two related but different ideas:

• $\varphi \leftrightarrow \psi$ is a new Boolean formula;
• $\varphi \equiv \psi$ is a statement about two formulas.

These are connected, but they are not literally the same notation.

Theorem

Equivalence and biconditionals

Two formulas $\varphi$ and $\psi$ are logically equivalent if and only if the formula

$$\varphi \leftrightarrow \psi$$

is a tautology.

So a biconditional can be used as a test for equivalence: if its final column is all true, then the two formulas match in every row.

Tautologies, contradictions, and contingent formulas

Definition

Three basic types of formula

Let $\varphi$ be a propositional formula.

• $\varphi$ is a tautology if it is true in every row.
• $\varphi$ is a contradiction if it is false in every row.
• $\varphi$ is contingent if it is true in some rows and false in others.

Standard examples are:

$$P \lor \neg P$$

which is a tautology, and

$$P \land \neg P$$

which is a contradiction.

The distinction matters because many short logical arguments amount to showing that some formula is always true or always false.

A second worked example

Worked example

Checking De Morgan's law by truth table

We test

$$\neg(P \lor Q) \equiv (\neg P) \land (\neg Q).$$

$P$	$Q$	$P \lor Q$	$\neg(P \lor Q)$	$\neg P$	$\neg Q$	$(\neg P) \land (\neg Q)$
T	T	T	F	F	F	F
T	F	T	F	F	T	F
F	T	T	F	T	F	F
F	F	F	T	T	T	T

The fourth and seventh columns agree row by row, so the formulas are logically equivalent.

This is a typical use of truth tables: not merely evaluating one formula, but proving a law of equivalence.

From an argument to one truth-table column

Theorem

Test finite propositional consequence

For premises $P_1,\ldots,P_n$ and conclusion $Q$, with $n\ge1$, the argument is valid exactly when

$$(P_1\land\cdots\land P_n)\to Q$$

is a tautology. This conditional is false exactly when all premises are true and the conclusion is false: precisely a countermodel. Rows with a false premise cannot refute the argument.

Worked example

Compare two premise lists

For premises $P\to Q,P$ and conclusion $Q$, the test is $((P\to Q)\land P)\to Q$. Its only row with both premises true is $P=T,Q=T$, where $Q$ is true; every other row makes the outer implication true through its false antecedent. For premises $P\to Q,Q$ and conclusion $P$, the test instead fails at $P=F,Q=T$. Changing a premise changes the argument being tested.

Worked example

Replace an equivalent component

In $R\land(P\to Q)$, replace $P\to Q$ by $\neg P\lor Q$. For any assignment the two inner expressions have equal truth values, so conjoining either with the same value of $R$ produces equal results. Thus $R\land(P\to Q)\equiv R\land(\neg P\lor Q)$. The outer connective and its scope stay fixed.

A controlled rewriting workflow

The equivalences introduced above give a practical way to put a formula into a more uniform shape before making a table. First replace every biconditional by $(P → Q) ∧ (Q → P)$. Then replace every implication using $P → Q ≡ ¬P ∨ Q$; use De Morgan's laws to move a negation inward; and remove double negations. Use distributivity when a conjunction or disjunction must be regrouped. For example,

$$¬(P → (Q ∧ R)) \equiv ¬(¬P ∨ (Q ∧ R)) \equiv P ∧ ¬(Q ∧ R) \equiv P ∧ (¬Q ∨ ¬R).$$

At each line, the formula is replaced by a logically equivalent formula, so the truth table's final column is preserved. The point of this workflow is auditability: a formula with only $¬$, $∧$, and $∨$ makes its subformula columns visible. These identities justify the rewrites; they do not remove the need to check the original formula's scope.

For this workflow, the target is negation normal form: a formula built from $¬$, $∧$, and $∨$, with each $¬$ immediately in front of an atomic proposition. It is a useful table-building target, not a claim that every proof can be replaced by a rewrite.

Worked example

Equivalence is different from entailment

The formulas $P ∧ Q$ and $P$ are not equivalent: at $P = T, Q = F$, the first is false while the second is true. Nevertheless, the argument $P ∧ Q$, therefore $P$, is valid, because there is no row with the premise true and the conclusion false. Its associated test formula $(P ∧ Q) → P$ is a tautology. Thus equivalence asks for matching columns in both directions, while entailment asks only whether a forbidden premise-true/conclusion-false row exists.

Commutativity, associativity, and distributivity

The following truth-table identities are useful when rearranging a formula:

$$A \land B \equiv B \land A,\qquad A \lor B \equiv B \lor A$$ $$A \land (B \land C) \equiv (A \land B) \land C,\qquad A \lor (B \lor C) \equiv (A \lor B) \lor C$$ $$A \lor (B \land C) \equiv (A \lor B) \land (A \lor C),\qquad A \land (B \lor C) \equiv (A \land B) \lor (A \land C).$$

Commutativity permits an exchange of two operands. Associativity permits a change of parentheses when the same connective is repeated. Distributivity is the expansion step that changes the connective structure. For instance,

$$R \lor (P \land Q) \equiv (R \lor P) \land (R \lor Q).$$

To apply this step in a larger expression, identify the whole left-hand pattern, replace it by the right-hand pattern, and then continue evaluating the new subformulas. Every row keeps the same final value because each displayed identity is a truth-table equivalence.

From table patterns to logical identities

The commutativity biconditional is a tautology:

$(A → B) ∨ (B → A)$ is also a tautology. If $A$ is true and $B$ is false, then $B → A$ is true; if $A$ is false and $B$ is true, then $A → B$ is true; when the values match, both implications are true.

The following biconditionals have the same value in every row:

Therefore $A ↔ B ≡ ¬A ↔ ¬B$. This is a statement about two formulas, not a claim that $↔$ and $≡$ are the same connective.

Worked example

Full table for $(P ∧ Q) → P$

The full table for $(P ∧ Q) → P$ is:

$P$	$Q$	$P ∧ Q$	$(P ∧ Q) → P$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

Its final column is all true, so it is a tautology and the argument “$P ∧ Q$, therefore $P$” is valid.

Negating a biconditional and reading a cycle

The negation of $P ↔ Q$ is true exactly when the two values differ:

$$\neg(P \leftrightarrow Q) \equiv (P \land \neg Q) \lor (\neg P \land Q).$$

This is the exclusive-difference condition, obtained by listing the two rows in which the biconditional is false.

For a cyclic implication exercise, avoid ambiguous chain notation. The three implications $A → B$, $B → C$, and $C → A$ force all three atomic values to agree, so the precise equivalent condition is

$$(A \leftrightarrow B) \land (B \leftrightarrow C).$$

This explicit conjunction states the two required biconditionals; it avoids silently treating $A ↔ B ↔ C$ as one primitive three-place connective.

Why this section matters later

Truth-table reasoning is not the endpoint of mathematical logic, but it trains two habits that remain important:

• separating syntax from meaning;
• checking whether a claim is valid in every case, not merely in one example.

Later, when the course turns to quantifiers, sets, and proof, that same demand for complete case analysis returns in a more sophisticated form.

Common mistakes

Common mistake

One matching row is not enough

If two formulas agree on one row, or even on several rows, that does not prove equivalence. Equivalence requires agreement on every possible assignment.

Common mistake

Do not confuse $\leftrightarrow$ with $\equiv$

The formula $\varphi \leftrightarrow \psi$ belongs inside a truth table. The notation $\varphi \equiv \psi$ is a metalogical statement saying that two formulas define the same truth function.

Try it yourself

Quick checks

Checkpoint

How many rows are needed in a truth table for a formula involving exactly three proposition variables?

Use the rule for the number of possible truth assignments.

Solution · Answer

There are $2^3 = 8$ rows, because each of the three variables can be either true or false independently.

Checkpoint

Why is $P \lor \neg P$ a tautology?

Think row by row, not by slogan.

Solution · Answer

If $P$ is true, then $P \lor \neg P$ is true because the left side is true. If $P$ is false, then $\neg P$ is true, so the disjunction is still true. Every row therefore gives T.

Checkpoint

Is the formula $P \land Q$ logically equivalent to $P \lor Q$?

Compare at least one row where the two formulas behave differently.

Solution · Answer

No. For example, when $P = T$ and $Q = F$, we get $P \land Q = F$ but $P \lor Q = T$. Since they differ on that row, they are not equivalent.

Continue to quantified statements

This page builds directly on 1.1 Propositional logic and prepares for 1.3 Quantifiers and negation.