2.2 Truth Tables, Implication, and Equivalence

Section 2.1 taught us to evaluate a compound proposition after choosing truth values for its atomic parts. One chosen assignment describes only one possible world. To compare formulas reliably, we need to inspect every possible assignment. A truth table organizes that complete inspection.

This section develops three connected tools:

• truth tables enumerate all possible input worlds;

• implication expresses a conditional promise and identifies exactly when it is broken;

• logical equivalence compares complete truth-table columns rather than surface wording.

Construct every input row systematically

Suppose an expression contains two atomic propositions, $p$ and $q$. Each one has two possible truth values. Therefore there are

assignments. A standard row order is

Notice the pattern: the $p$ column changes slowly, while the $q$ column alternates more quickly. With three atomic propositions $p,q,r$, there are $2^3=8$ rows. The first column stays true for four rows, the next changes every two rows, and the last changes every row. This counting reuses the independent-choice idea from the power set in Chapter 1.

To build the truth table for

do not try to calculate the entire formula at once. Create one column for each needed subexpression:

Read one row as a trace. In row 2, $p=\mathrm{T}$ and $q=\mathrm{F}$. Therefore $p\lor q=\mathrm{T}$, $\neg q=\mathrm{T}$, and the final conjunction is true. Every other row is computed by the same local rules.

A dependable construction process is:

1. list every atomic proposition;

2. create all $2^n$ input rows, where $n$ is the number of atomic propositions;

3. add columns for the smallest subexpressions;

4. work outward until the final expression has a column;

5. recheck any row in which the output changes from the row above.

Implication is a promise, not a claim of causation

The implication

is read “if $p$, then $q$.” Proposition $p$ is called the hypothesis or antecedent, and $q$ is called the conclusion or consequent.

Use a policy example:

> If a file is confidential, then the file is encrypted.

Let $p$ mean “the file is confidential” and $q$ mean “the file is encrypted.” The policy is broken only when the file is confidential but is not encrypted. Its truth table is therefore

The last two rows often surprise beginners. The implication does not say that encryption happens only for confidential files. It makes a promise about what must happen when $p$ is true. When $p$ is false, that particular promise has not been violated.

This meaning gives a useful equivalence:

The symbol $\equiv$ means “has the same truth value under every assignment.” The expression $\neg p\lor q$ is false only when $\neg p$ is false and $q$ is false—that is, when $p=\mathrm{T}$ and $q=\mathrm{F}$. It therefore fails in exactly the same row as the implication.

The patrol simulation makes the conditional a rule that can be violated. Sort all four worlds. The important observation is not merely which cargo pod fails, but why the other three pods do not constitute counterexamples to the stated promise.

Related conditionals are not interchangeable

Starting from $p\to q$, three related statements can be formed:

The original and contrapositive are logically equivalent. The converse and inverse are logically equivalent to each other, but usually not to the original.

Return to the file policy. From “if confidential, then encrypted,” the converse says “if encrypted, then confidential.” That need not be true because a public file may also be encrypted. One concrete encrypted public file is enough to refute the converse.

The contrapositive says “if not encrypted, then not confidential.” This restates the same policy from the failure side: an unencrypted file cannot be confidential if the original policy is obeyed.

Do not accept these equivalences by word order alone. In the next part, truth-table columns give a complete test.

Equivalence means matching in every possible world

Two compound propositions are logically equivalent when they have the same truth value for every possible assignment. We write

Here $P$ and $Q$ may stand for whole compound expressions. To test equivalence:

1. place both expressions in the same truth table;

2. calculate their final columns;

3. compare the columns row by row;

4. declare equivalence only if every pair matches.

For example, De Morgan’s law from Chapter 1 becomes

The two highlighted final ideas are represented by the fourth and seventh columns. Their truth values match in every row, so the equivalence is established.

If columns differ in even one row, that row is a counterexample to equivalence. A counterexample is a specific assignment that makes one expression true and the other false.

Tautologies, contradictions, and contingencies

A final truth-table column also tells us how an expression behaves:

• A tautology is true in every row.

• A contradiction is false in every row.

• A contingency is true in some rows and false in others.

For example,

is a tautology because either $p$ is true or its negation is true. Meanwhile,

is a contradiction because $p$ cannot be both true and false in one assignment. The expression $p\land q$ is a contingency because its value depends on the chosen row.

The biconditional

is read “$p$ if and only if $q$.” It is true exactly when $p$ and $q$ have the same truth value. It can be understood as requiring both directions:

The scanner treats a final truth-table column as a four-bit signature. Search for matching expression pairs, then deliberately choose a nonmatching pair and locate the first counterexample row. Both actions are essential: equivalence requires all rows, while non-equivalence requires only one.

Bridge to the next section

Truth tables work well when a formula contains a small fixed number of propositions. Many claims instead concern every object in a collection or the existence of an object with a property. Section 2.3 returns to the open statement $P(x)$ and gives “for every” and “there exists” precise meanings through predicates and quantifiers.