The Lumenary · Grades 9–12

Propositional logic and truth tables

Name: ______________________

Date: ______________________

You will learn to

Build truth tables for compound statements and classify formulas as tautologies, contradictions or contingent
Test logical equivalence with truth tables, and prove De Morgan's laws and $\neg(P \to Q) \equiv P \wedge \neg Q$
Distinguish an implication from its converse, inverse and contrapositive, and explain why only the contrapositive is equivalent to it
Negate compound and quantified statements, including implications
Recognise valid argument forms such as modus ponens and modus tollens, and the fallacy of affirming the consequent

1.
Is the statement “If $7$ is even, then $7$ is divisible by $4$ ” true or false?
- A.True
- B.False, because $7$ is not divisible by $4$
- C.Neither: it is meaningless because $7$ is odd
2.
Which statement is the contrapositive of “If a shape is a square, then it is a rectangle”?
- A.If a shape is not a rectangle, then it is not a square.
- B.If a shape is a rectangle, then it is a square.
- C.If a shape is not a square, then it is not a rectangle.
- D.A shape is a square and it is not a rectangle.
3.
Which statement is the negation of “If it is a public holiday, then the bakery is closed”?
- A.It is a public holiday and the bakery is open.
- B.If it is a public holiday, then the bakery is open.
- C.If it is not a public holiday, then the bakery is open.
- D.It is not a public holiday and the bakery is open.
4.
What is the negation of “Amara speaks Hausa and Yoruba”?
- A.Amara does not speak Hausa or she does not speak Yoruba.
- B.Amara speaks neither Hausa nor Yoruba.
- C.Amara speaks exactly one of Hausa and Yoruba.
5.
How many rows does the truth table of $(P \wedge Q) \to (R \vee \neg S) \leftrightarrow T$ have?
6.
Which of these formulas are tautologies? (Choose all that apply.)
- A. $P \vee \neg P$
- B. $(P \to Q) \to (Q \to P)$
- C. $\big((P \to Q) \wedge \neg Q\big) \to \neg P$
- D. $P \to (P \vee Q)$
- E. $\big((P \to Q) \wedge Q\big) \to P$
7.
Each card has a letter on one side and a whole number on the other. You see E, M, 6 and 3. Rule: “If a card has a vowel on one side, then it has an even number on the other.” Which cards must you turn over to check the rule? (Choose all that apply.)
- A.E
- B.M
- C.6
- D.3
8.
Which statement is the negation of “Every whole number divisible by $4$ is divisible by $8$ ”?
- A.Some whole number is divisible by $4$ but not by $8$ .
- B.Every whole number divisible by $4$ is not divisible by $8$ .
- C.Every whole number divisible by $8$ is divisible by $4$ .
- D.No whole number divisible by $8$ is divisible by $4$ .
9.
Which Lean statement says that a conditional is equivalent to its contrapositive (for all propositions p and q)?
- A.(p → q) ↔ (¬q → ¬p)
- B.(p → q) ↔ (q → p)
- C.(p → q) ↔ (¬p → ¬q)
- D.¬(p → q) ↔ (p ∧ q)
10.
Write is_tautology(f, n), which returns True exactly when the Python function f of n boolean arguments returns True for every combination of arguments. Then write equivalent(f, g, n) using it. (Hint: itertools.product([True, False], repeat=n) lists all rows.)
Computational — Practice

Answer key — Propositional logic and truth tables

1.
Both $P$ and $Q$ are false. The conditional $P \to Q$ is false only in the row $P = \mathrm{T}$ , $Q = \mathrm{F}$ , so here it is true — vacuously true, because its hypothesis never holds.
2.
With $P$ = “square” and $Q$ = “rectangle”, the contrapositive $\neg Q \to \neg P$ reads “If a shape is not a rectangle, then it is not a square.” It is equivalent to the original, so it is true as well. The converse and the inverse are both false.
3.
The statement $P \to Q$ is false exactly when $P$ is true and $Q$ is false, so $\neg(P \to Q) \equiv P \wedge \neg Q$ : “It is a public holiday and the bakery is open.” The negation of an “if” statement is an “and” statement.
4.
“ $P$ and $Q$ ” is false as soon as at least one part is false. So its negation is $\neg P \vee \neg Q$ : “Amara does not speak Hausa, or she does not speak Yoruba” (inclusive or).
5.
There are five variables $P, Q, R, S, T$ , each true or false independently, so there are $2^5 = 32$ rows.
6.
$P \vee \neg P$ , modus tollens $\big((P \to Q) \wedge \neg Q\big) \to \neg P$ and $P \to (P \vee Q)$ are tautologies. The other two fail in the row $P = \mathrm{F}$ , $Q = \mathrm{T}$ : there $P \to Q$ and $Q$ are true but $P$ is false.
7.
The rule $V \to E$ is broken only by a vowel together with an odd number. E might hide an odd number, and 3 might hide a vowel, so these two must be turned. M ( $V$ false) and 6 ( $E$ true) cannot break the rule. Checking 3 is checking the contrapositive $\neg E \to \neg V$ .
8.
The statement is $\forall n\,\big(4 \mid n \to 8 \mid n\big)$ . Its negation is $\exists n\,\big(4 \mid n \wedge 8 \nmid n\big)$ : “some whole number is divisible by $4$ but not by $8$ .” The negation is true ( $n = 4$ ), so the original statement is false.
9.
The contrapositive of p → q is ¬q → ¬p, so the statement is (p → q) ↔ (¬q → ¬p). In the lesson, contrapositive_iff proves it (the backward direction by contradiction), and contrapositive_iff_library applies Mathlib's not_imp_not.

10.

from itertools import product

def is_tautology(f, n):
    return all(f(*row) for row in product([True, False], repeat=n))

def equivalent(f, g, n):
    return is_tautology(lambda *row: bool(f(*row)) == bool(g(*row)), n)

Because a formula in $n$ variables has only $2^n$ rows, this check is a complete proof of a propositional law — but the number of rows doubles with every new variable.