A security system unlocks only when both a key AND a fingerprint are provided. A technician says: 'If the door fails to open, then the key must be wrong AND the fingerprint must be wrong.' According to De Morgan's first law, what is the correct negation?
AThe key is wrong AND the fingerprint is wrong (technician is correct)
BThe key is wrong OR the fingerprint is wrong (the failure of a conjunction is a disjunction of failures)
CNeither the key nor the fingerprint is required
DThe key is wrong OR the fingerprint is correct
De Morgan's first law: ¬(p ∧ q) ≡ ¬p ∨ ¬q. The door fails when it is NOT the case that both conditions hold — meaning at least one condition fails. The technician's error is keeping AND after negation; De Morgan's says the connective must flip to OR.
Question 2 Multiple Choice
Which of the following correctly applies De Morgan's Laws to simplify ¬(A ∨ B ∨ C)?
A¬A ∨ ¬B ∨ ¬C
B¬A ∧ ¬B ∨ ¬C
C¬A ∧ ¬B ∧ ¬C
D¬(A ∧ B ∧ C)
By iterated application of De Morgan's second law (¬(p ∨ q) ≡ ¬p ∧ ¬q), negating a disjunction of any length produces a conjunction of all the negated components. Each OR flips to AND, and each variable gets negated. Mixing ∨ and ∧ in the result (option B) would be incorrect.
Question 3 True / False
¬(p ∧ q) is logically equivalent to ¬p ∧ ¬q — negation distributes over AND while leaving the connective unchanged.
TTrue
FFalse
Answer: False
This is the most common De Morgan's error. Negation does not pass through a connective unchanged: ¬(p ∧ q) ≡ ¬p ∨ ¬q. The connective flips from AND to OR. Verify with p = T, q = F: ¬(T ∧ F) = ¬F = T, but ¬T ∧ ¬F = F ∧ T = F. The two expressions differ.
Question 4 True / False
De Morgan's Laws apply to set theory as well as propositional logic: the complement of an intersection equals the union of the complements, and the complement of a union equals the intersection of the complements.
TTrue
FFalse
Answer: True
The set-theoretic versions (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ and (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ follow directly from the logical laws by treating 'x ∈ A' as a proposition. This correspondence (∧ ↔ ∩, ∨ ↔ ∪, ¬ ↔ complement) is one of the deepest structural parallels in mathematics.
Question 5 Short Answer
Explain why ¬(p ∧ q) cannot equal ¬p ∧ ¬q, using specific truth values for p and q to show where the two expressions produce different results.
Think about your answer, then reveal below.
Model answer: Let p = T, q = F. Then ¬(p ∧ q) = ¬(T ∧ F) = ¬F = T, but ¬p ∧ ¬q = F ∧ T = F. The expressions disagree, so they are not equivalent.
When p is true and q is false, the conjunction p ∧ q is false, so its negation is true. But negating each component and conjoining gives F ∧ T = F. This single counterexample refutes the claimed equivalence. The correct form, ¬p ∨ ¬q = F ∨ T = T, matches the left side — confirming De Morgan's actual law.