Which of the following correctly states one of De Morgan's laws?
A¬(A ∧ B) ≡ (¬A ∧ ¬B)
B¬(A ∨ B) ≡ (¬A ∨ ¬B)
C¬(A ∧ B) ≡ (¬A ∨ ¬B)
D¬(A → B) ≡ (A → ¬B)
De Morgan's law for conjunction states: ¬(A ∧ B) ≡ (¬A ∨ ¬B). Negating a conjunction distributes the negation to each component and flips 'and' to 'or.' The symmetric law is ¬(A ∨ B) ≡ (¬A ∧ ¬B) — negating a disjunction distributes and flips 'or' to 'and.' The critical pattern: the connective always flips. Options A and B distribute the negation correctly but fail to flip the connective — a common error. Option D is unrelated to De Morgan's laws.
Question 2 Multiple Choice
A student wants to show ¬(P → Q) is equivalent to (P ∧ ¬Q). Applying the conditional equivalence A → B ≡ ¬A ∨ B followed by De Morgan's law, what is the correct derivation?
A¬(P → Q) ≡ ¬(¬P ∧ Q) ≡ (P ∨ ¬Q) by distributing negation and applying De Morgan
B¬(P → Q) ≡ ¬(¬P ∨ Q) ≡ (P ∧ ¬Q) by conditional equivalence then De Morgan then double negation
C¬(P → Q) ≡ (¬P → ¬Q) by negating both the antecedent and consequent
D¬(P → Q) ≡ (¬P ∧ ¬Q) by applying De Morgan directly to the implication
Step 1: Apply conditional equivalence: P → Q ≡ ¬P ∨ Q, so ¬(P → Q) ≡ ¬(¬P ∨ Q). Step 2: Apply De Morgan's law to ¬(¬P ∨ Q): distribute negation and flip ∨ to ∧, giving (¬¬P ∧ ¬Q). Step 3: Apply double negation: ¬¬P ≡ P. Result: P ∧ ¬Q — 'P is true and Q is false,' which is exactly when an implication fails. Option A makes an error in the first step. Option C applies a different (invalid) transformation. Option D skips the conditional equivalence step entirely.
Question 3 True / False
If φ ≡ ψ, then replacing any occurrence of φ inside a larger compound formula with ψ preserves the larger formula's truth value under every interpretation.
TTrue
FFalse
Answer: True
True. This is the substitution theorem, and it follows directly from what logical equivalence means. Since φ and ψ produce identical truth values under every possible variable assignment, any formula built using φ as a component must produce the same output whether φ or ψ appears there — the surrounding formula 'sees' the same truth value from the subformula. This licenses algebraic manipulation of logic: just as you can substitute equals for equals in arithmetic, you can substitute logically equivalent formulas in logic.
Question 4 True / False
A → B and B → A are logically equivalent because they are both conditionals built from the same two variables.
TTrue
FFalse
Answer: False
False. Sharing the same variables is not sufficient for logical equivalence — the truth tables must match on *every* row. When A = T and B = F: A → B is false (true antecedent, false consequent), but B → A is true (false antecedent makes the conditional vacuously true). The truth tables differ, so they are not equivalent. A → B (equivalent to ¬A ∨ B) and its converse B → A (equivalent to ¬B ∨ A) are distinct logical claims. Confusing a conditional with its converse is a fundamental logical error.
Question 5 Short Answer
Explain in your own words what it means for two propositional formulas to be logically equivalent, and why the substitution theorem follows directly from this definition.
Think about your answer, then reveal below.
Model answer: Two formulas φ and ψ are logically equivalent (φ ≡ ψ) when they produce identical truth values under every possible assignment of true or false to their propositional variables — their truth tables are row-by-row identical. The substitution theorem says: if φ ≡ ψ, you can replace any occurrence of φ inside any larger formula with ψ without changing the larger formula's truth value under any interpretation. This follows directly from the definition: since φ and ψ behave identically in every context (same output for every input), substituting one for the other in any compound formula cannot change how the compound formula evaluates.
Logical equivalence partitions all formulas into classes of synonymous expressions that are interchangeable in any logical context. The substitution theorem is what gives this partition its practical utility: it licenses step-by-step algebraic manipulation of formulas. Just as knowing 2 + 2 = 4 lets you replace '2 + 2' with '4' anywhere in an arithmetic expression, knowing φ ≡ ψ lets you replace φ with ψ anywhere in a logical formula — enabling simplification, conversion to normal forms, and formal proof construction.