1.2 Truth tables and equivalence

Once the atomic propositions have been fixed, a truth table tests a compound statement under every possible assignment of truth values.

A complete truth table is an exhaustive 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 1.2.1

(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 1.2.2

(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.

Implication as a disjunction

Worked example 1.2.3

(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 1.2.4

(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 1.2.5

(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 1.2.6

(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.

De Morgan’s law

Worked example 1.2.7

(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 1.2.8

(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 1.2.9

(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 1.2.10

(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 1.2.11

(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)$.

Worked example 1.2.12

(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.

From truth values to membership and quantifiers

For a fixed element $x$, the statements $x\in A$ and $x\in B$ have truth values. The logical identities above therefore give the corresponding identities for set operations once membership is checked for every $x$. A quantifier over an infinite domain is different: a finite table of propositional truth values cannot enumerate all domain elements. The next note replaces enumeration with arbitrary elements and checked witnesses.

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

Quick check

(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.

Quick check

(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.

Quick check

(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.