A rule that is true or false
A truth table is a list of every way some statements can be true or false, with the answer for each. It lets you test a rule without guessing.
A shop says: "Students get a discount if they show a card." Is a customer with no card breaking that rule? This lesson gives you a way to settle questions like that, and to prove that two rules mean the same.
By the end of this lesson
Note
I can build a truth table and decide whether two statements are equivalent.
Key words
| Word | What it means |
|---|---|
| Statement | a sentence that is either true or false |
| Connective | a word such as and, or, not that joins statements |
| Truth table | a list of every case with its answer |
| Implication | the statement "if P then Q" |
| Equivalent | having the same answer in every case |
| Tautology | a statement that is true in every case |
The cells students fill in are left blank in this preview.
And, or and not each have a table
A statement is true or false, never both. "The server is up" is a statement. "Is the server up?" is not.
We join statements with connectives. P and Q is true only when both are true. P or Q is true when at least one is true. Not P flips the answer. A truth table lists every case.
Truth table: and, or, not
| P | Q | P and Q | P or Q | not P |
|---|---|---|---|---|
| True | True | True | True | False |
| True | False | False | True | False |
| False | True | False | True | True |
| False | False | False | False | True |
The cells students fill in are left blank in this preview.
Check the first column pair
python3 -c "print(True and False, True or False, not True)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
If P then Q fails in one case
An implication says: if P is true, then Q is true. A promise works the same way. "If you pass, I will buy lunch" is broken only when you pass and get no lunch.
If you fail, the promise says nothing, so it is not broken. That is why a false P always makes "if P then Q" true.
Truth table: if P then Q
| P (you pass) | Q (lunch) | If P then Q |
|---|---|---|
| True | True | True: promise kept |
| True | False | False: promise broken |
| False | True | True: nothing promised |
| False | False | True: nothing promised |
The cells students fill in are left blank in this preview.
Print the table of if P then Q
python3 -c "print([(p, q, (not p) or q) for p in (True, False) for q in (True, False)])"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think "if P then Q" is false when P is false. It is not. The promise is broken only when P is true and Q is false. When P is false, the statement is true by default.
Equivalent statements have the same table
Two statements are equivalent when their columns match in every row. Build both columns, then compare them.
The test below is a proof by cases: there are only four cases, so checking all four proves it. A statement true in every row is a tautology.
Worked example: not (P and Q)
| P | Q | not (P and Q) | (not P) or (not Q) |
|---|---|---|---|
| True | True | False | False |
| True | False | True | True |
| False | True | True | True |
| False | False | True | True |
The cells students fill in are left blank in this preview.
Test the two columns by program
python3 -c "print(all((not (p and q)) == ((not p) or (not q)) for p in (True, False) for q in (True, False)))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Which reversed promises are equivalent?
Take "if P then Q". Its contrapositive is "if not Q then not P", and it is equivalent. Its converse is "if Q then P", and it is not.
In Python, p <= q reads as "p implies q", because False is less than True. The next Run tests both claims.
Contrapositive, then converse
python3 -c "ps = (True, False); print(all((p <= q) == ((not q) <= (not p)) for p in ps for q in ps), all((p <= q) == (q <= p) for p in ps for q in ps))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Try it: print the table yourself
# Every case of P and Q, with "if P then Q".
for p in (True, False):
for q in (True, False):
implication = (not p) or q
print(p, q, implication)
# Change the last line to print (not q) or p. That is the converse.
# Which rows change?