The Central Idea
Suppose a compound proposition depends on two atomic propositions, \(p\) and \(q\).
Each proposition can be either true or false, so there are four possible assignments:
| \(p\) | \(q\) |
|---|---|
| T | T |
| T | F |
| F | T |
| F | F |
A truth table evaluates a logical expression across all possible assignments.
Why Truth Tables Work
Propositional logic is truth-functional. Once the truth values of the atomic propositions are known, the truth value of a compound proposition is determined by its logical connectives.
A truth table therefore replaces guesswork with exhaustive finite analysis.
How Many Rows Are Needed?
If a truth table contains \(n\) independent propositional variables, then it requires
\[ \boxed{2^n} \]rows.
- \(1\) variable gives \(2\) rows.
- \(2\) variables give \(4\) rows.
- \(3\) variables give \(8\) rows.
- \(4\) variables give \(16\) rows.
- \(5\) variables give \(32\) rows.
A Reliable Row Pattern
For three variables,
\[ p,\qquad q,\qquad r, \]a standard arrangement is:
| \(p\) | \(q\) | \(r\) |
|---|---|---|
| T | T | T |
| T | T | F |
| T | F | T |
| T | F | F |
| F | T | T |
| F | T | F |
| F | F | T |
| F | F | F |
Here \(p\) changes every four rows, \(q\) every two rows, and \(r\) every row.
Truth Table for Negation
Negation reverses a truth value.
| \(p\) | \(\neg p\) |
|---|---|
| T | F |
| F | T |
Truth Table for Conjunction
A conjunction is true only when both component propositions are true.
| \(p\) | \(q\) | \(p\land q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Conjunction Means All Required Conditions Hold
The expression
\[ p\land q \]behaves like a two-condition requirement. If either condition fails, the conjunction is false.
Truth Table for Disjunction
Standard logical disjunction is inclusive: it is true whenever at least one component is true.
| \(p\) | \(q\) | \(p\lor q\) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Inclusive Or and Exclusive Or
Ordinary logical \(\lor\) includes the case where both propositions are true. Exclusive or, often called XOR, is true only when exactly one proposition is true.
| \(p\) | \(q\) | XOR |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Truth Table for Implication
The implication
\[ p\to q \]is false only when the antecedent is true and the consequent is false.
| \(p\) | \(q\) | \(p\to q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Why Implication Has Only One False Row
The statement \(p\to q\) promises that whenever \(p\) is true, \(q\) will also be true.
The only assignment that breaks this promise is
\[ p=T,\qquad q=F. \]When \(p\) is false, there is no true antecedent that fails to produce the required consequent.
Material Implication
This truth-functional interpretation of \(p\to q\) is called material implication.
It records a relationship between truth values. It does not, by itself, require a causal relationship between \(p\) and \(q\).
Truth Table for Biconditional
A biconditional is true when the two component propositions have the same truth value.
| \(p\) | \(q\) | \(p\leftrightarrow q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
A useful memory rule is:
\[ \boxed{\text{A biconditional is true when the two sides agree.}} \]Building a Compound Truth Table
For
\[ \neg p\land q, \]first evaluate \(\neg p\), then use that result with \(q\).
| \(p\) | \(q\) | \(\neg p\) | \(\neg p\land q\) |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | T | T |
| F | F | T | F |
Intermediate Columns
Intermediate columns are working columns for subexpressions.
For
\[ (p\lor q)\land\neg r, \]useful intermediate columns are
\[ p\lor q \]and
\[ \neg r. \]The final column then combines those results.
Example: Three Variables
Construct a truth table for
\[ (p\lor q)\land r. \]| \(p\) | \(q\) | \(r\) | \(p\lor q\) | \((p\lor q)\land r\) |
|---|---|---|---|---|
| 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 | F |
| F | F | F | F | F |
Example: Negated Conjunction
For
\[ \neg(p\land q), \]first complete the \(p\land q\) column, then reverse it.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) |
|---|---|---|---|
| T | T | T | F |
| T | F | F | T |
| F | T | F | T |
| F | F | F | T |
Example: Compound Antecedent
Consider
\[ (p\land q)\to r. \]The compound proposition is false only when
\[ p\land q=T \]and
\[ r=F. \]The entire antecedent must be treated as one truth-valued component of the implication.
Tautologies
A tautology is true under every possible truth assignment.
Consider
\[ p\lor\neg p. \]| \(p\) | \(\neg p\) | \(p\lor\neg p\) |
|---|---|---|
| T | F | T |
| F | T | T |
The final column is always true, so
\[ \boxed{p\lor\neg p\text{ is a tautology}.} \]Contradictions
A contradiction is false under every possible truth assignment.
Consider
\[ p\land\neg p. \]| \(p\) | \(\neg p\) | \(p\land\neg p\) |
|---|---|---|
| T | F | F |
| F | T | F |
Therefore,
\[ \boxed{p\land\neg p\text{ is a contradiction}.} \]Contingencies
A contingency is true under some truth assignments and false under others.
For example,
\[ p\land q \]is a contingency because its final column contains both T and F.
Classifying a Final Column
- All T values: tautology.
- All F values: contradiction.
- A mixture of T and F: contingency.
The final truth-table column summarizes the behavior of the entire formula.
Logical Equivalence
Two formulas are logically equivalent when their final truth-table columns match in every row.
If formulas \(A\) and \(B\) match under every valuation, we write
\[ \boxed{A\equiv B}. \]Example: Double Negation
| \(p\) | \(\neg p\) | \(\neg\neg p\) |
|---|---|---|
| T | F | T |
| F | T | F |
The \(p\) and \(\neg\neg p\) columns match.
\[ \boxed{\neg\neg p\equiv p}. \]Example: Implication as Disjunction
Compare
\[ p\to q \]with
\[ \neg p\lor q. \]| \(p\) | \(q\) | \(\neg p\) | \(\neg p\lor q\) | \(p\to q\) |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
The final two columns match in every row.
\[ \boxed{p\to q\equiv\neg p\lor q}. \]Example: The Contrapositive
A truth table shows that
\[ p\to q \]and
\[ \neg q\to\neg p \]have identical truth values under every assignment.
Therefore,
\[ \boxed{p\to q\equiv\neg q\to\neg p}. \]The Converse Is Different
Compare
\[ p\to q \]with
\[ q\to p. \]| \(p\) | \(q\) | \(p\to q\) | \(q\to p\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | T | F |
| F | F | T | T |
The middle rows differ, so the formulas are not logically equivalent.
Truth Tables and De Morgan Relationships
Truth tables verify that
\[ \boxed{\neg(p\land q)\equiv\neg p\lor\neg q} \]and
\[ \boxed{\neg(p\lor q)\equiv\neg p\land\neg q}. \]These relationships will be developed systematically in the later lesson on logical equivalence.
Biconditional as Two Implications
A truth table also confirms
\[ \boxed{p\leftrightarrow q\equiv(p\to q)\land(q\to p)}. \]The biconditional is true exactly when each proposition implies the other.
Testing an Argument Form
Truth tables can test whether a simple argument form is valid.
Suppose the premises are
\[ p\to q \]and
\[ p, \]with conclusion
\[ q. \]Inspect every row where both premises are true. If \(q\) is true in every such row, the argument form is valid.
A Counterexample Row
An argument form is invalid if there is at least one row in which every premise is true and the conclusion is false.
Such a row is a truth-table counterexample.
Satisfiability
A formula is satisfiable if at least one truth assignment makes it true.
In a truth table, satisfiability means that the final column contains at least one T.
A contradiction is unsatisfiable because its final column contains no T.
Truth Tables as Exhaustive Search
A truth table examines every possible assignment, so it is a finite exhaustive-search method.
The number of cases grows as
\[ 2^n. \]Every additional variable doubles the number of rows.
Connection to Binary Representation
If we temporarily associate
\[ T\leftrightarrow1,\qquad F\leftrightarrow0, \]truth-table rows resemble binary counting.
Three variables produce the same number of assignments as three binary digits:
\[ 2^3=8. \]This provides an early bridge from propositional logic to Boolean systems and digital circuits.
Common Error: Missing Rows
A complete truth table must contain all \(2^n\) assignments.
If three variables are present, a six-row table is incomplete because
\[ 2^3=8. \]Common Error: Repeating an Assignment
Every possible assignment should appear exactly once.
Repeating one row usually means another assignment has been omitted.
Common Error: Treating Or as Exclusive
Standard logical disjunction
\[ p\lor q \]is true in the \(T,T\) row.
Marking that row false would incorrectly use exclusive or.
Common Error: Misreading Implication
The statement
\[ p\to q \]is false only when
\[ p=T,\qquad q=F. \]Rows with false antecedents are true under material implication.
Common Error: Ignoring Parentheses
The formulas
\[ \neg(p\land q) \]and
\[ (\neg p)\land q \]require different intermediate columns and produce different truth patterns.
Common Error: Skipping Intermediate Columns
For a compound formula such as
\[ (p\lor q)\to\neg r, \]first compute
\[ p\lor q \]and
\[ \neg r. \]Then evaluate the implication.
Common Error: Declaring Equivalence Too Early
Two formulas are logically equivalent only if their final columns match in every row.
Agreement under one or several selected assignments is not enough.
Common Error: Confusing Satisfiable with Tautological
A satisfiable formula needs at least one true row.
A tautology requires every row to be true.
Thus every tautology is satisfiable, but many satisfiable formulas are not tautologies.
A Reliable Procedure for Constructing a Truth Table
- Identify every independent propositional variable.
- Count the variables.
- Compute the required number of rows using \(2^n\).
- List every truth-value assignment systematically.
- Identify the smallest subexpressions.
- Create intermediate columns for those subexpressions.
- Evaluate from the inside outward.
- Complete the final column.
- Interpret the final column according to the problem.
A Reliable Procedure for Testing Equivalence
- Place both formulas in the same truth table.
- Use the same truth-value rows for both.
- Build all needed intermediate columns.
- Compute each final column.
- Compare the two final columns row by row.
- If every value matches, the formulas are logically equivalent.
- If even one row differs, they are not logically equivalent.
Example: Full Workflow
Construct a truth table for
\[ (p\land\neg q)\to r. \]Three variables require
\[ 2^3=8 \]rows.
| \(p\) | \(q\) | \(r\) | \(\neg q\) | \(p\land\neg q\) | \((p\land\neg q)\to r\) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | T | F | F | F | T |
| T | F | T | T | T | T |
| T | F | F | T | T | F |
| F | T | T | F | F | T |
| F | T | F | F | F | T |
| F | F | T | T | F | T |
| F | F | F | T | F | T |
The final column contains both T and F, so the proposition is a contingency.
Practice 1: Negation
Complete the truth table for
\[ \neg p. \]Practice 2: Conjunction
Complete the truth table for
\[ p\land q. \]Practice 3: Disjunction
Complete the truth table for
\[ p\lor q. \]Practice 4: Implication
Complete the truth table for
\[ p\to q. \]Practice 5: Biconditional
Complete the truth table for
\[ p\leftrightarrow q. \]Practice 6: Compound Proposition
Construct a truth table for
\[ \neg p\lor q. \]Practice 7: Classify the Formula
Use a truth table to classify
\[ p\lor\neg p \]as a tautology, contradiction, or contingency.
Practice 8: Test Equivalence
Determine whether
\[ p\to q \]and
\[ \neg p\lor q \]are logically equivalent.
Practice 9: Count the Rows
How many rows are required for a truth table involving
\[ p,\qquad q,\qquad r? \]Practice 10: Find a Counterexample Row
Determine whether
\[ p\to q \]is logically equivalent to
\[ q\to p. \]If not, identify one row where they differ.
Practice Answers
Practice 1
\[ T\mapsto F,\qquad F\mapsto T. \]Practice 2
The \(p\land q\) column is
\[ \boxed{T,\ F,\ F,\ F}. \]Practice 3
The \(p\lor q\) column is
\[ \boxed{T,\ T,\ T,\ F}. \]Practice 4
The \(p\to q\) column is
\[ \boxed{T,\ F,\ T,\ T}. \]Practice 5
The \(p\leftrightarrow q\) column is
\[ \boxed{T,\ F,\ F,\ T}. \]Practice 6
The final column for \(\neg p\lor q\) is
\[ \boxed{T,\ F,\ T,\ T}. \]Practice 7
The expression is true in every row.
\[ \boxed{\text{tautology}}. \]Practice 8
Their final columns match in every row.
\[ \boxed{p\to q\equiv\neg p\lor q}. \]Practice 9
\[ 2^3=8. \]Therefore,
\[ \boxed{8\text{ rows}}. \]Practice 10
They are not logically equivalent.
For
\[ p=T,\qquad q=F, \]we have
\[ p\to q=F \]but
\[ q\to p=T. \]What to Remember
- A complete truth table lists every possible truth assignment.
- \(n\) independent variables require \(2^n\) rows.
- Negation reverses a truth value.
- Conjunction is true only when both components are true.
- Disjunction is true when at least one component is true.
- Implication is false only when the antecedent is true and the consequent is false.
- Biconditional is true when its components agree.
- Intermediate columns make compound evaluations reliable.
- An all-T final column is a tautology.
- An all-F final column is a contradiction.
- Matching final columns establish logical equivalence.
The central operational habit is to build the table systematically and evaluate compound propositions one structural layer at a time.
Where We Go Next
Truth tables provide a complete finite method for calculating the behavior of propositional formulas. The next lesson shifts from evaluating formulas to studying the logical operations themselves as two-valued operations.
The next lesson, Boolean Operations, develops AND, OR, NOT, and related operations as the computational building blocks of Boolean systems.