Before this lesson
M01.6.1 Sets and Venn diagrams
After this lesson you can
In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
A spam filter flags an email when it has a link and its sender is unknown. A colleague wants every email that is not flagged, and writes the rule “no link and a known sender”. On eight emails the filter flags two, yet the colleague’s rule finds only two of the other six. What went wrong, and how could a truth table have caught it before anything was counted?
From the last lesson
1. On the running example, what are \({A \cap B}\) and \({A - B}\)?
\({A \cap B = \{2, 4\}}\), the overlap, and \({A - B = \{6, 8\}}\), the part of \({A}\) outside \({B}\).
2. State De Morgan’s two laws in words.
The complement of a union is the intersection of the complements, and the complement of an intersection is the union of the complements.
A statement is a sentence that is either true or false. “7 is odd” is a true statement and “\({2 + 2 = 5}\)” is a false one. A sentence with a variable in it, such as “\({x}\) is even”, is not yet a statement: it is an open sentence, which becomes a statement once \({x}\) is chosen. For \({x = 4}\) it is true; for \({x = 7}\) it is false.
Take two open sentences about the numbers of the last lesson’s universe, \({U = \{1, \ldots, 8\}}\):
Each number \({x}\) makes \({P}\) true or false and \({Q}\) true or false. That gives four possible pairs of answers, and they are exactly the four regions of the Venn diagram.
Every row of a truth table is a region of the Venn diagram. The badge in each region names its row.
A truth table lists every combination of truth values, one per row. With two statements there are four rows, written in the order TT, TF, FT, FF (T for true, F for false). So a truth table is a Venn diagram written as a list, and everything this lesson builds with words like “and” and “or” is a choice of rows, just as the last lesson’s operations were a choice of regions.
Step 1. Not. The negation \({\neg P}\), read “not \({P}\)”, is true when \({P}\) is false and false when \({P}\) is true. Its truth table has two rows, because it involves one statement:
| \({P}\) | \({\neg P}\) |
|---|---|
| T | F |
| F | T |
Step 2. And, or. The statement \({P \wedge Q}\), read “\({P}\) and \({Q}\)”, is true only when both parts are true. The statement \({P \vee Q}\), read “\({P}\) or \({Q}\)”, is true when at least one part is true:
| \({P}\) | \({Q}\) | \({P \wedge Q}\) | \({P \vee Q}\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
The “or” of mathematics is inclusive: it counts the case where both parts hold. “Tea or coffee?” in a café usually means one but not both; mathematics never uses “or” that way, and says “exactly one of” when it means it.
Step 3. If-then. The statement \({P \Rightarrow Q}\), read “if \({P}\), then \({Q}\)”, is false in one row only: when \({P}\) is true and \({Q}\) is false. Think of it as a promise.
If-then as a promise. Only a high score with no prize breaks it.
If you score below 90, the promise says nothing about you, so whatever happens it has not been broken. A statement is either true or false, and an unbroken promise counts as true. That is why both cases with \({P}\) false are T.
Step 4. Turning an if-then around. From \({P \Rightarrow Q}\) come two related statements. The converse is \({Q \Rightarrow P}\). The contrapositive is \({\neg Q \Rightarrow \neg P}\). Take “if \({x}\) is a multiple of 4, then \({x}\) is even”, which is true for every number. Its converse, “if \({x}\) is even, then \({x}\) is a multiple of 4”, is false: 2 is even and not a multiple of 4. Its contrapositive, “if \({x}\) is odd, then \({x}\) is not a multiple of 4”, is true. A converse is a different claim; a contrapositive is the same claim in other words, as the formal statement proves.
Step 5. If and only if. The statement \({P \Leftrightarrow Q}\), read “\({P}\) if and only if \({Q}\)”, says both \({P \Rightarrow Q}\) and \({Q \Rightarrow P}\). It is true when \({P}\) and \({Q}\) have the same truth value: both true or both false.
Step 6. Logic is the algebra of sets. Put \({P}\) = “\({x \in A}\)” and \({Q}\) = “\({x \in B}\)”. Then “\({x \in A}\) and \({x \in B}\)” picks the rows where both are true, which is the region \({A \cap B}\). Each connective matches an operation of the last lesson:
| logic | sets | in words |
|---|---|---|
| \({P \wedge Q}\) | \({A \cap B}\) | in both |
| \({P \vee Q}\) | \({A \cup B}\) | in at least one |
| \({\neg P}\) | \({A^c}\) | not in \({A}\) |
| \({P}\) | \({Q}\) | \({P \Rightarrow Q}\) | \({P \Leftrightarrow Q}\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | F |
| F | F | T | T |
Result 1 (the contrapositive law). \({P \Rightarrow Q}\) is logically equivalent to \({\neg Q \Rightarrow \neg P}\).
Proof. Work out \({\neg Q \Rightarrow \neg P}\) row by row, using the rule that an if-then is false only when its first part is true and its second part false.
The column reads T, F, T, T, which is the column of \({P \Rightarrow Q}\) in every row. \({\blacksquare}\)
Result 2 (De Morgan’s laws for statements). For any statements \({P}\) and \({Q}\),
\[ \begin{aligned} \neg(P \wedge Q) &\equiv \neg P \vee \neg Q, \\ \neg(P \vee Q) &\equiv \neg P \wedge \neg Q, \end{aligned} \]
where \({\equiv}\) means “is logically equivalent to”. The worked example proves the first law with a truth table. The second follows from the match with sets: with \({P}\) = “\({x \in A}\)” and \({Q}\) = “\({x \in B}\)”, the left side says \({x \in (A \cup B)^c}\) and the right side says \({x \in A^c \cap B^c}\). By De Morgan’s first law for sets, both sets are the one region neither, which is the row FF. So both statements are true in that row only: their columns agree in every row. \({\blacksquare}\)
\({P \Rightarrow Q}\) is false only in the row TF, which is the region only \({A}\). So the numbers that make “\({x \in A \Rightarrow x \in B}\)” true fill every region except only \({A}\): the set \({A^c \cup B}\). The claim “for every \({x}\) in \({U}\), if \({x \in A}\) then \({x \in B}\)” is therefore true exactly when the region only \({A}\) is empty, which is to say when \({A \subseteq B}\). For the running example it fails, because 6 and 8 sit in only \({A}\). The explorer below shades this set when you choose the regions for “\({P \Rightarrow Q}\)”.
Repair the spam filter of the opening question. Number eight emails 1 to 8. Let \({P}\) be “the email has a link”, true for emails 2, 4, 6 and 8, and \({Q}\) be “the sender is unknown”, true for emails 1, 2, 3 and 4. These are the sets \({A}\) and \({B}\) again. The filter flags \({P \wedge Q}\): emails 2 and 4. We want every other email, which is \({\neg(P \wedge Q)}\).
Build the truth table one column at a time. Each row also lists the emails that fall in it.
The worked-example trace. The left side of De Morgan’s first law and its right side give the same column, F, T, T, T.
Left side. \({P \wedge Q}\) is T only in the first row, so its negation \({\neg(P \wedge Q)}\) reads F, T, T, T.
Right side. \({\neg P}\) reads F, F, T, T and \({\neg Q}\) reads F, T, F, T. An “or” is true when at least one part is true, so \({\neg P \vee \neg Q}\) is F in the first row, where both parts are F, and T in the other three: F, T, T, T.
The two columns agree in every row, so \({\neg(P \wedge Q)}\) and \({\neg P \vee \neg Q}\) are logically equivalent. In words, an email is not flagged when it has no link or its sender is known. The rows marked T hold emails 1, 3, 5, 6, 7 and 8: six emails.
The colleague wrote \({\neg P \wedge \neg Q}\), which is T only in the last row: emails 5 and 7. It loses emails 1 and 3 (no link, but an unknown sender) and 6 and 8 (a link, but a known sender). Negating an “and” turns it into an “or”.
First a truth table built by hand. Python’s truth values are True and False, and its connectives are the words and, or and not. A small function prints T or F, and two loops, one inside the other, run through the four rows.
def tf(value):
if value:
return "T"
return "F"
print("P Q and or not")
# outer loop: P; for each P,
# the inner loop runs through Q
for P in [True, False]:
for Q in [True, False]:
print(tf(P), tf(Q), " ",
tf(P and Q), " ",
tf(P or Q), " ",
tf(not P))P Q and or not
T T T T F
T F F T F
F T F T T
F F F F TPython has no sign for if-then, but it does not need one. (not P) or Q is false only when not P is false and Q is false, that is when \({P}\) is true and \({Q}\) is false: exactly the one false row of \({P \Rightarrow Q}\).
The standard library builds the rows for you. itertools.product([True, False], repeat=2) gives the four pairs in the usual order, and each column below is a list with one truth value per row.
import itertools
def implies(P, Q):
return (not P) or Q
rows = list(itertools.product(
[True, False], repeat=2))
print(rows)
# one list for each column
if_then, contra, converse = [], [], []
dm_left, dm_right = [], []
# each pair unpacks into P, Q
for P, Q in rows:
if_then.append(implies(P, Q))
contra.append(implies(not Q, not P))
converse.append(implies(Q, P))
dm_left.append(not (P and Q))
dm_right.append((not P) or (not Q))
print("contrapositive agrees:",
if_then == contra)
print("converse agrees:",
if_then == converse)
print("De Morgan holds:",
dm_left == dm_right)[(True, True), (True, False), (False, True), (False, False)]
contrapositive agrees: True
converse agrees: False
De Morgan holds: TrueThe same connectives filter the rows of a table of data. Each email is a row of three values: its number, whether it has a link, and whether its sender is unknown.
# (number, has link, unknown)
emails = [
(1, False, True),
(2, True, True),
(3, False, True),
(4, True, True),
(5, False, False),
(6, True, False),
(7, False, False),
(8, True, False),
]
flagged, not_flagged = [], []
colleague = []
# one row at a time, unpacked
# into three names
for n, link, unknown in emails:
if link and unknown:
flagged.append(n)
if not (link and unknown):
not_flagged.append(n)
if (not link) and (not unknown):
colleague.append(n)
print("flagged:", flagged)
print("not flagged:", not_flagged)
print("colleague's rule:", colleague)flagged: [2, 4]
not flagged: [1, 3, 5, 6, 7, 8]
colleague's rule: [5, 7]Venn and truth-table explorer
Pick an expression, or tap regions to build your own set: the regions shade, the numbers 1 to 8 sort into the set or out of it, and the matching rows of the truth table light up. Choose \({(A \cup B)^c}\), then press “Other side of the law”: the shading does not move.
Wrong beside right, for the true statement “if \({x}\) is a multiple of 4, then \({x}\) is even”. The small circle sits inside the big one. Turning the claim around fails; negating and turning it around does not.
“If \({P}\) implies \({Q}\), then \({Q}\) implies \({P}\).”
That is the converse, a different claim. Every multiple of 4 is even, but 2 and 6 are even without being multiples of 4. Only the contrapositive, \({\neg Q \Rightarrow \neg P}\), is guaranteed to say the same thing. With data the slip reads: “every spam email in our set has a link, so every email with a link is spam”.
“Or means one or the other, but not both.”
In mathematics and in code, “or” includes “both”. True or True is True, and 2, which is even and at most 4, is in \({A \cup B}\).
“An if-then with a false first part is false.”
It is true: a promise that is never put to the test is not broken. “If 2 is odd, then \({2 + 2 = 5}\)” is a true statement, because its first part is false.
“The opposite of ‘\({P}\) and \({Q}\)’ is ‘not \({P}\) and not \({Q}\)’.”
This is the colleague’s mistake in the worked example: it lost four of the six emails. By De Morgan’s laws the negation of “and” is “or”: \({\neg P \vee \neg Q}\).
1. Which of these are statements: “7 is odd”, “\({x > 3}\)”, “Is 7 odd?”
Only “7 is odd”, which is true. “\({x > 3}\)” is an open sentence, a statement only once \({x}\) is chosen, and a question is never a statement.
2. When is \({P \vee Q}\) false?
Only when \({P}\) and \({Q}\) are both false.
3. When is \({P \Rightarrow Q}\) false?
Only when \({P}\) is true and \({Q}\) is false. In the other three rows it is true.
4. Give the converse and the contrapositive of “if \({x}\) is a multiple of 4, then \({x}\) is even”. Which one says the same thing?
Converse: “if \({x}\) is even, then \({x}\) is a multiple of 4”, which is false (\({x = 2}\)). Contrapositive: “if \({x}\) is not even, then \({x}\) is not a multiple of 4”, which is true and says the same thing.
5. Which set operations match “and”, “or” and “not”?
Intersection, union and complement.
1. ★ Write the truth table of the statement below, one column at a time, and check that it agrees with \({P \Leftrightarrow Q}\) in every row.
\[ (P \Rightarrow Q) \wedge (Q \Rightarrow P) \]
Row by row, \({P \Rightarrow Q}\) reads T, F, T, T and \({Q \Rightarrow P}\) reads T, T, F, T (it is false only when \({Q}\) is true and \({P}\) is false, the row FT). Their “and” is true only where both are true: T, F, F, T. That is the column of \({P \Leftrightarrow Q}\), which is true exactly when \({P}\) and \({Q}\) match.
2. ★★ For \({x}\) in \({U = \{1, \ldots, 8\}}\), use De Morgan’s laws to negate each statement in words, then list the numbers that make the negation true. (a) “\({x}\) is even and \({x}\) is at most 4”. (b) “\({x}\) is even or \({x}\) is at most 4”.
(a) The negation of an “and” is an “or” of negations: “\({x}\) is odd or \({x}\) is more than 4”. It is true for 1, 3, 5, 6, 7 and 8, every number except 2 and 4.
(b) The negation of an “or” is an “and” of negations: “\({x}\) is odd and \({x}\) is more than 4”. It is true for 5 and 7 only.
3. ★★★ Show with a truth table that \({P \Rightarrow Q}\) is logically equivalent to \({\neg P \vee Q}\). With \({P}\) = “\({x \in A}\)” and \({Q}\) = “\({x \in B}\)”, which numbers of the running example make \({P \Rightarrow Q}\) true? Explain why “for every \({x}\) in \({U}\), \({P \Rightarrow Q}\)” says that \({A}\) is a subset of \({B}\), and decide whether it holds here.
\({\neg P}\) reads F, F, T, T. An “or” with \({Q}\) (T, F, T, F) gives T, F, T, T, which is the column of \({P \Rightarrow Q}\). So the two are equivalent.
\({P \Rightarrow Q}\) is false only in the row TF, the region only \({A}\), which holds 6 and 8. It is true for the other six numbers: 1, 2, 3, 4, 5 and 7, the set \({A^c \cup B}\).
“For every \({x}\), \({P \Rightarrow Q}\)” is true exactly when no \({x}\) lands in the false row, that is when no element of \({A}\) is missing from \({B}\). That is the definition of \({A \subseteq B}\). Here it fails: 6 is in \({A}\) and not in \({B}\).
A truth table is a Venn diagram written as a list: and, or and not are intersection, union and complement.
Four regions, four rows.
\[ \begin{aligned} \neg(P \wedge Q) &\equiv \neg P \vee \neg Q \\ \neg(P \vee Q) &\equiv \neg P \wedge \neg Q \end{aligned} \]
Sources. Each was opened and checked against this lesson on 12 November 2026.
and, or and not, with and and or stopping early) and itertools.product (nested loops in odometer order; repeat=2 pairs a list with itself).Next. M01.6.3 Direct proof and counterexample uses if-then statements about every number, and shows how to prove them or knock them down.
This lesson unlocks
M01.6.3 Direct proof and counterexample