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 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 lists every possible assignment of truth values to the variables in , together with the resulting truth value of in each case.
For example, if a formula involves only and , then there are four rows:
The truth table is therefore not just a picture. It is an exhaustive case analysis.
How to construct a table carefully
When students make mistakes with truth tables, the problem is usually not the connective itself. The problem is that the rows are incomplete, out of order, or the columns are computed too quickly. A reliable method is:
- list all assignments of the atomic propositions;
- add columns for simpler subformulas first;
- compute the final formula only after the intermediate columns are correct.
This matters especially when a formula contains several connectives.
A first important equivalence
Worked example
Why and say the same thing
Consider the formulas and .
| | | | | | | --- | --- | --- | --- | --- | | 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
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 and are logically equivalent if they have the same truth value under every assignment of their variables. We write
Logical equivalence is stronger than saying that two formulas happen to agree in one example. It means they define the same truth function.
The source notes also warn you not to confuse two related but different ideas:
- is a new Boolean formula;
- is a statement about two formulas.
These are connected, but they are not literally the same notation.
Theorem
Equivalence and biconditionals
Two formulas and are logically equivalent if and only if the formula
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 be a propositional formula.
- is a tautology if it is true in every row.
- is a contradiction if it is false in every row.
- is contingent if it is true in some rows and false in others.
Standard examples are:
which is a tautology, and
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
| | | | | | | | | --- | --- | --- | --- | --- | --- | --- | | 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 |
Again the last two 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.
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 with
The formula belongs inside a truth table. The notation is a metalogical statement saying that two formulas define the same truth function.
Try it yourself
Read and try
Trace one truth table
The live builder lets you switch formulas and inspect how each row changes the final truth value.
| P | Q | P → Q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
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
Quick check
Why is a tautology?
Think row by row, not by slogan.
Solution
Answer
Quick check
Is the formula logically equivalent to ?
Compare at least one row where the two formulas behave differently.
Solution
Answer
Exercises
Quick check
Show that by constructing a truth table.
Introduce intermediate columns instead of trying to compute the final answer in one jump.
Solution
Guided solution
Read this first
This page builds directly on 1.1 Propositional logic and prepares for 1.3 Quantifiers and negation.