When two propositions say the same thing, and how to say the opposite
Last modified: 2026-10-27 13:24:37 (PDT)
Source
Adapted from Kameron Decker Harris’s Fall 2026 lecture notes “Logic 3”, which are typed transcriptions of Scott Wehrwein’s Spring 2025 handwritten lecture notes. The truth table for the distributive law of “and” over “or” comes from those notes; the exercises are new.
Exercise 1 (A rule with a redundant part) A server grants access to a user who is an administrator, or who is an administrator and is on the office network. Let \(P\) be “the user is an administrator” and \(Q\) be “the user is on the office network”.
Make a truth table for \(P \lor (P \land Q)\). In which rows does it have the same truth value as \(P\)?
Solution 1.
| \(P\) | \(Q\) | \(P \land Q\) | \(P \lor (P \land Q)\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | F |
| F | F | F | F |
The last column matches the \(P\) column in every row, so the rule grants access exactly to the administrators, and the part about the office network changes nothing.
Definition 1 (Logical equivalence) Two propositions \(A\) and \(B\), each built from some of the propositions \(P_1, \ldots, P_n\), are logically equivalent, written \(A \equiv B\), if they have the same truth value in every row of a truth table (Definition: Truth table), that is, for every combination of truth values of \(P_1, \ldots, P_n\).
Example 1 (An equivalence) By Exercise 1, \(P \lor (P \land Q) \equiv P\) (Definition 1): the truth table of \(P \lor (P \land Q)\) has the same column as \(P\), in a table with columns for both \(P\) and \(Q\).
Remark 1 (Notation for logical equivalence). \(A \equiv B\) (Definition 1) is a claim about \(A\) and \(B\), not a new proposition built from them with a logical connective (Definition: Logical connective). Some books write \(A \Leftrightarrow B\) or \(A \iff B\) for it instead, which is easy to confuse with the biconditional (Definition: If and only if); these notes use \(\equiv\).
Logical equivalence can be chained: if \(A \equiv B\) and \(B \equiv C\), then \(A \equiv C\), since in each row \(A\) has the value of \(B\), which has the value of \(C\).
Exercise 2 (Not both) A continuous integration server runs two test suites. Let \(P\) be “the unit tests pass” and \(Q\) be “the integration tests pass”.
Is “it is not the case that both suites pass”, \(\neg (P \land Q)\), logically equivalent (Definition 1) to “neither suite passes”, \(\neg P \land \neg Q\)?
Solution 2.
| \(P\) | \(Q\) | \(P \land Q\) | \(\neg (P \land Q)\) | \(\neg P\) | \(\neg Q\) | \(\neg P \land \neg Q\) |
|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F |
| T | F | F | T | F | T | F |
| F | T | F | T | T | F | F |
| F | F | F | T | T | T | T |
No. The two columns differ in the second and third rows, where exactly one suite passes: then it is true that not both pass, but false that neither passes.
Definition 2 (Tautology) A tautology is a proposition that is true in every row of its truth table (Definition: Truth table).
Example 2 (A tautology) \(P \lor \neg P\) is a tautology (Definition 2):
| \(P\) | \(\neg P\) | \(P \lor \neg P\) |
|---|---|---|
| T | F | T |
| F | T | T |
Definition 3 (Contradiction) A contradiction is a proposition that is false in every row of its truth table (Definition: Truth table).
Example 3 (A contradiction) \(P \land \neg P\) is a contradiction (Definition 3):
| \(P\) | \(\neg P\) | \(P \land \neg P\) |
|---|---|---|
| T | F | F |
| F | T | F |
Remark 2 (Contradictions in proofs). A proof by contradiction is named for this kind of proposition: it assumes the negation of what it proves, and derives a contradiction (Definition 3), such as \(Q \land \neg Q\).
Theorem 1 (Equivalence is a tautological biconditional) For propositions \(A\) and \(B\), \(A \equiv B\) (Definition 1) exactly when \(A \Leftrightarrow B\) is a tautology (Definition 2).
Exercise 3 (Does “or” distribute over “and”?) In arithmetic, multiplication distributes over addition: \(a (b + c) = a b + a c\). Use a truth table to decide whether “or” distributes over “and”: is \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)?
Solution 3.
| \(A\) | \(B\) | \(C\) | \(B \land C\) | \(A \lor (B \land C)\) | \(A \lor B\) | \(A \lor C\) | \((A \lor B) \land (A \lor C)\) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | F |
| F | F | T | F | F | F | T | F |
| F | F | F | F | F | F | F | F |
Yes: the fifth and last columns match in every row. Addition does not distribute over multiplication in arithmetic: \(1 + 2 \cdot 3 = 7\), but \((1 + 2)(1 + 3) = 12\). But “or” distributes over “and”.
Theorem 2 (Distributive laws) For propositions \(A\), \(B\) and \(C\):
Example 5 (Distributing “and”) For an integer \(x\), “\(x\) is even, and \(x > 0\) or \(x < 0\)” is logically equivalent, by law 1 of Theorem 2, to “\(x\) is even and \(x > 0\), or \(x\) is even and \(x < 0\)”.
Remark 3 (Checking an equivalence in Racket). A truth table is a loop over every combination of truth values, so a program can check an equivalence. In Racket, for*/and runs its body for every combination of p and q, and returns #f as soon as the body returns #f, and #t if it never does:
This returns #t, as Exercise 1 found. Replacing the body with (equal? (not (and p q)) (and (not p) (not q))) returns #f, as Exercise 2 found.
Exercise 4 (When is the door locked?) A door opens when the badge is valid, the PIN is correct, and it is a weekday. Let \(B\) be “the badge is valid”, \(N\) be “the PIN is correct” and \(W\) be “it is a weekday”, so the door stays locked when \(\neg (B \land N \land W)\) is true.
Describe when the door stays locked with a sentence that puts “not” only in front of \(B\), \(N\) or \(W\), never in front of a compound proposition.
Solution 4. The door stays locked when the badge is not valid, the PIN is not correct, or it is not a weekday: \(\neg B \lor \neg N \lor \neg W\). \(B \land N \land W\) is false exactly when at least one of \(B\), \(N\) and \(W\) is false.
Theorem 3 (Double negation) For a proposition \(P\), \(\neg \neg P \equiv P\) (Definition 1).
Example 6 (Not unreadable) “It is not the case that the file is not readable” means “the file is readable” (Theorem 3).
Theorem 4 (Replacing a part by an equivalent part) If \(A \equiv B\) (Definition 1), then replacing \(A\) by \(B\) inside a larger proposition gives a proposition logically equivalent to the larger one. In particular, \(\neg A \equiv \neg B\).
Theorem 5 (De Morgan’s laws) For propositions \(P\) and \(Q\) (Wikipedia contributors 2026):
Example 8 (Neither coordinate positive) For real numbers \(x\) and \(y\), by law 2 of Theorem 5, “not (\(x > 0\) or \(y > 0\))” is logically equivalent to “\(x \le 0\) and \(y \le 0\)”.
Exercise 5 (A broken deployment rule) A team’s rule is “if the tests pass, then the build is deployed”. Let \(P\) be “the tests pass” and \(Q\) be “the build is deployed”. The rule is broken on the days when \(\neg (P \Rightarrow Q)\) is true.
Write \(\neg (P \Rightarrow Q)\) without \(\Rightarrow\), and in English.
Solution 5. The rule is broken on a day when the tests pass and the build is not deployed: \(P \land \neg Q\). On a day when the tests fail, the rule is not broken, whether or not the build is deployed.
“If the tests pass, then the build is not deployed”, \(P \Rightarrow \neg Q\), is not the negation: on a day when the tests fail, it is true, and so is the rule.
Theorem 6 (Negating a conditional) For propositions \(P\) and \(Q\), \(\neg (P \Rightarrow Q) \equiv P \land \neg Q\).
Example 9 (When a search claim fails) The negation of “if the list is sorted, then binary search finds the key” is “the list is sorted and binary search does not find the key” (Theorem 6).
Corollary 1 (A conditional without the arrow) For propositions \(P\) and \(Q\), \(P \Rightarrow Q \equiv \neg P \lor Q\).
Example 10 (A rule as an “or”) By Corollary 1, “if the tests pass, then the build is deployed” is logically equivalent to “the tests fail or the build is deployed”.
Exercise 6 (Not every test passes) Let \(T\) be the set of tests in a test suite, and let \(P(t)\) be “test \(t\) passes”. The report “every test passes” is \(\forall t \in T, P(t)\).
Write the negation of this report in English and in symbols, without putting \(\neg\) in front of a quantifier.
Solution 6. “Some test fails”: \(\exists t \in T, \neg P(t)\). “Every test passes” is false exactly when at least one test does not pass.
“Every test fails”, \(\forall t \in T, \neg P(t)\), is not the negation: when some tests pass and some fail, both it and “every test passes” are false.
Theorem 7 (Negating a quantifier) For a set \(S\) and a predicate \(P(x)\) (Definition: Predicate) whose domain (Definition: Domain (domain of discourse, universe of discourse)) is \(S\):
Example 11 (No natural square root of 2) By part 2 of Theorem 7, \(\neg (\exists n \in \mathbb{N}, n^2 = 2)\) has the same truth value as \(\forall n \in \mathbb{N}, n^2 \ne 2\).
Remark 4 (De Morgan’s laws for quantifiers). Theorem 7 is often written \(\neg \forall x, P(x) \equiv \exists x, \neg P(x)\) and \(\neg \exists x, P(x) \equiv \forall x, \neg P(x)\). These notes say “has the same truth value” instead, because \(P(x)\) is a predicate, not a proposition, so Definition 1, which compares truth tables, does not apply.
On a finite set \(S = \{a, b\}\), \(\forall x \in S, P(x)\) has the same truth value as \(P(a) \land P(b)\), and \(\exists x \in S, P(x)\) has the same truth value as \(P(a) \lor P(b)\), so Theorem 7 is De Morgan’s laws (Theorem 5) applied to \(P(a)\) and \(P(b)\).
Racket shows the same pattern on a list: (not (andmap even? (list 2 4 5))) and (ormap odd? (list 2 4 5)) both return #t.
Remark 5 (Pushing a negation inward). To negate a proposition built with \(\neg\), \(\land\), \(\lor\), \(\Rightarrow\) and quantifiers, move the \(\neg\) inward one step at a time:
Stop when every \(\neg\) sits in front of a proposition with no connective or quantifier inside it. The result is easier to read and to check than a \(\neg\) in front of the whole proposition.
Exercise 7 (Completing a palindrome) Let \(W\) be the set of words made of the letters a and b, including the empty word, and write \(s t\) for word \(s\) followed by word \(t\). A palindrome is a word that reads the same forwards and backwards, such as abba.
Write the negation of \[ \forall s \in W,\ \exists t \in W,\ s t \text{ is a palindrome} \] without putting \(\neg\) in front of a quantifier.
Solution 7. Apply Theorem 7 twice, from the outside in. First, the negation has the truth value of \[ \exists s \in W,\ \neg (\exists t \in W,\ s t \text{ is a palindrome}). \] For each word \(s\), Theorem 7 says that \(\neg (\exists t \in W,\ s t \text{ is a palindrome})\) has the truth value of \(\forall t \in W,\ s t \text{ is not a palindrome}\). These have the same truth value for every \(s\), so the \(\exists s\) propositions built from them do too (Definition: Existential quantifier), and the negation has the truth value of \[ \exists s \in W,\ \forall t \in W,\ s t \text{ is not a palindrome}. \] In English: some word cannot be made into a palindrome by adding letters at its end.
Exercise 8 (Which one is true?) Which is true: \(\forall s \in W,\ \exists t \in W,\ s t \text{ is a palindrome}\), from Exercise 7, or its negation?
Solution 8. The original is true, so its negation is false. For any word \(s\), let \(t\) be \(s\) written backwards; then \(s t\) reads the same backwards. For example, for \(s = \text{aab}\), \(t = \text{baa}\) and \(s t = \text{aabbaa}\).