From Truth Conditions to a Complete Table
In Logical Connectives, we defined negation, conjunction, disjunction, implication, and the biconditional. We evaluated compound statements by determining their component truth values and applying these definitions. A truth table organizes the same work for every possible assignment of truth values.
We continue to use \(p\), \(q\), and \(r\) as placeholders for complete propositions. In a table, T means true and F means false. These are labels for truth values, not numbers.
A row does not claim that its assignments are the actual truth values of particular mathematical statements. It says: if the components have these values, then the compound statement has the value shown. Once specific propositions are substituted, their actual truth values select the applicable row.
The Basic Connective Tables
Negation has one input, so its table has two rows. The entries below simply record its definition from the previous tutorial.
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
For two distinct proposition letters there are four assignments: both true, only the first true, only the second true, and both false. We can place several output columns beside these same four assignments.
| \(p\) | \(q\) | \(p\land q\) | \(p\lor q\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
| \(p\) | \(q\) | \(p\to q\) | \(p\leftrightarrow q\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | F |
| F | F | T | T |
The implication column has just one F: a true antecedent paired with a false consequent. The biconditional column has T exactly where the input values agree, including the row where both are false. These entries should be read from the definitions, rather than from an informal interpretation of “if.”
How Many Rows Are Needed?
Proof. For the first letter there are exactly two choices, T and F. Each assignment to the first letter extends in exactly two ways when a second letter is added: give the new letter T or give it F. More generally, adding a new letter doubles the number of assignments to the letters already listed.
No extensions are duplicates: extensions of different old assignments still differ on an old letter, while the two extensions of one old assignment differ on the new letter. No assignment is missed: every assignment to the enlarged list consists of an old assignment together with one of the two values for the new letter. Starting with two assignments and doubling once for each of the remaining \(n-1\) letters gives \(2^n\) assignments.
Thus one letter requires \(2\) rows, two require \(4\), three require \(8\), and four require \(16\). The count depends on the number of distinct letters, not the number of times they occur. For example,
requires four rows, not sixteen. Each occurrence of \(p\) has the same value within a row, and so does each occurrence of \(q\). A compound expression such as \(\neg p\) is computed from \(p\); it is not a new independent input.
A reliable row order uses blocks. With three letters, let \(p\) be T for four rows and F for four rows. Let \(q\) alternate in blocks of two, and let \(r\) alternate on every row. Other orders are equally valid, provided every assignment appears exactly once.
Building a Table from the Inside Out
The main task is to respect the grouping of the formula. First evaluate the smaller parts, then use those results as inputs to the next connective. The final column belongs to the whole formula.
Count them to determine the required number of assignment rows.
Use a fixed block pattern so that none are omitted or repeated.
Read the parentheses and place each needed component before the expression that uses it.
Use values from the same row only. Treat a computed component just as you would a single proposition.
Identify exactly which assignments make the formula true and which make it false.
Worked Example: Negating a Conditional
Construct a table for \(\neg(p\to q)\). The outermost connective is negation, so first compute \(p\to q\), then reverse each value in that column.
| \(p\) | \(q\) | \(p\to q\) | \(\neg(p\to q)\) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | T | F |
| F | F | T | F |
The final column is true only when \(p\) is true and \(q\) is false. In particular, when both components are false, the conditional is true and its negation is false.
For a concrete instance, let \(p\) be “\(3+2=5\)” and \(q\) be “\(4<4\).” Arithmetic gives \(p=\mathrm{T}\) and \(q=\mathrm{F}\), so the second row applies. The statement \(\neg(p\to q)\) is true.
The parentheses matter. For \((\neg p)\to q\), the intermediate column would be \(\neg p\), and the final operation would be implication, not negation. At \(p=\mathrm{T}\), \(q=\mathrm{T}\), that formula is true, whereas the formula in the example is false.
A Three-Letter Truth Table
Worked Example: A Compound Antecedent
Consider the formula
There are three distinct letters, so we need eight rows. The antecedent is the entire conjunction \(p\land q\). We compute it before applying implication.
| \(p\) | \(q\) | \(r\) | \(p\land q\) | \((p\land q)\to r\) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | F |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |
In the second row, both requirements in the antecedent hold, but the consequent fails. This makes the implication false. In the fourth row, \(p\) is true and \(r\) is false, but the implication is nevertheless true: \(q\) is false, so the whole antecedent is false.
The final column shows that the formula fails exactly when \(p\) and \(q\) are both true and \(r\) is false. None of the other seven assignments makes it false.
What the Final Column Tells Us
A complete final column describes the truth of a formula under every assignment to its letters. Three standard terms distinguish the possible patterns.
| Classification | Definition | Final column |
|---|---|---|
| Tautology | A formula true under every truth assignment. | Only T entries. |
| Contradiction | A formula false under every truth assignment. | Only F entries. |
| Contingency | A formula true under at least one assignment and false under at least one assignment. | Both T and F entries. |
The two worked examples above are contingencies. Each final column contains both values. A single T entry shows that a formula is not a contradiction; a single F entry shows that it is not a tautology. To establish that the final column has only one value, every row must be accounted for.
Proof by truth table. There is only one distinct proposition letter, so the following two rows exhaust all assignments.
| \(p\) | \(\neg p\) | \(p\lor\neg p\) | \(p\land\neg p\) | \(\neg(p\land\neg p)\) |
|---|---|---|---|---|
| T | F | T | F | T |
| F | T | T | F | T |
If \(p\) is true, its negation is false; if \(p\) is false, its negation is true. Thus in each row their disjunction is true and their conjunction is false. Negating that conjunction gives true in each row. Both asserted formulas therefore have only T entries and are tautologies. The table also proves that \(p\land\neg p\) is a contradiction.
This is a proof because it checks all possible cases, not because it checks several representative examples. For any proposition substituted for \(p\), classical logic assigns it one of the two truth values, and the corresponding row gives the claimed result.
Logical Possibilities and Mathematical Facts
A truth table evaluates logical structure. It does not, by itself, determine which rows can arise from particular mathematical predicates.
For example, take \(p\) to mean “\(x>2\)” and \(q\) to mean “\(x>0\)” at a specified real input \(x\). The abstract table for \(p\to q\) includes a false row where \(p\) is true and \(q\) is false. But no real input realizes that assignment: if \(x>2\), then \(x>0\) by the ordering of the real numbers.
The other three rows are realized: \(x=3\) gives T, T; \(x=1\) gives F, T; and \(x=-1\) gives F, F. The abstract table includes all four assignments because it treats the letters as unrestricted inputs. The mathematical interpretation imposes an additional relationship between them.
Similarly, the proportion of T entries is not automatically a probability. The three-letter example has seven T entries out of eight, but this does not say that a related mathematical or clinical assertion is true with probability \(7/8\). A truth table supplies no model assigning probabilities to its rows.
Finally, all entries presuppose meaningful propositions with definite classical truth values. An undefined expression does not supply a third truth value, and an unspecified predicate is not made into a complete proposition simply by placing it in a table.
Check Your Understanding
List every assignment when a complete table is requested, and label intermediate columns clearly.
- How many rows are needed for \((p\lor q)\land(\neg p\to q)\)? How many are needed for \((p\lor q)\land(r\to p)\)? Explain why repeated occurrences of \(p\) do not add new input choices.
- Construct the complete truth table for \((p\lor q)\land\neg(p\land q)\). Use separate columns for the disjunction, the conjunction, and its negation. Which rows make the final column true?
- Construct the table for \((\neg p)\to q\). In which assignments does its final column differ from that of \(\neg(p\to q)\)?
- Construct an eight-row truth table for \((p\lor q)\land r\). State exactly when it is true, and classify it as a tautology, contradiction, or contingency.
- Use complete tables to classify \(p\to p\), \(p\leftrightarrow\neg p\), and \(p\land q\). Explain why the full table, rather than one favorable row, justifies each classification.
- At specified real inputs, let \(p\) mean “\(x>0\)” and \(q\) mean “\(x>2\).” Which abstract assignment to \(p,q\) cannot occur? Give a value of \(x\) that makes \(p\to q\) false, and explain why the abstract table alone does not find that value.