Questions: Logical Equivalence in Propositional Logic

Question 1

Is P → Q logically equivalent to Q → P?

• A. Yes — implications are symmetric, just like equality
• B. No — P → Q can be true while Q → P is false; consider P = 'it rained' and Q = 'the ground is wet'
• C. Yes — if P implies Q, then Q must imply P by the definition of logical consequence
• D. Only if both P and Q are tautologies

Answer: (B)

P → Q and Q → P are NOT equivalent — Q → P is the converse of P → Q, and converses are not logically equivalent to the original in general. Consider P = T, Q = F: P → Q is false, but Q → P is true. Or by truth table: when P is false and Q is true, P → Q is true but Q → P is false. The confusion between an implication and its converse is one of the most common logical errors. P → Q is equivalent instead to its contrapositive: ¬Q → ¬P.

Question 2

You want to verify that ¬(P ∧ Q) ≡ (¬P ∨ ¬Q) (De Morgan's first law). What is the correct procedure?

• A. Prove that both ¬(P ∧ Q) and (¬P ∨ ¬Q) are tautologies individually
• B. Find at least one truth assignment that makes both formulas true simultaneously
• C. Construct a joint truth table and verify that the two formula columns match in every row
• D. Show that ¬(P ∧ Q) → (¬P ∨ ¬Q) holds under all assignments

Answer: (C)

Logical equivalence means identical truth values under EVERY truth assignment — the two formula columns in a joint truth table must match in all rows. Option A is wrong because individual tautologies are not needed (neither formula is a tautology). Option B is insufficient — one matching row doesn't establish equivalence across all assignments. Option D checks only one direction of implication; equivalence requires both φ → ψ AND ψ → φ. Only the full truth table comparison is decisive.

Question 3

If two formulas are logically equivalent, you can substitute one for the other within any larger formula without changing the truth value of the whole.

• T. True
• F. False

Answer: True

This substitution property is precisely what makes logical equivalence useful. Because φ ≡ ψ means they agree on every truth assignment, replacing one with the other in any context preserves truth values throughout. For example, since P → Q ≡ ¬P ∨ Q, you can always rewrite implications as disjunctions. This substitution principle underlies all formula simplification and the conversion to normal forms like CNF and DNF.

Question 4

If φ → ψ holds for nearly every truth assignment (φ logically implies ψ), then φ and ψ are logically equivalent.

• T. True
• F. False

Answer: False

Implication (φ → ψ) is one-directional: in every assignment where φ is true, ψ is also true — but ψ can be true even when φ is false. Equivalence (φ ≡ ψ) requires both φ → ψ AND ψ → φ. Example: P → (P ∨ Q) holds for all assignments (P logically implies P ∨ Q), but they are not equivalent — when P is false and Q is true, P ∨ Q is true while P is false. Equivalence is mutual implication; one-way implication is strictly weaker.

Question 5

What is the difference between logical equivalence (φ ≡ ψ) and material implication (φ → ψ)? Give a concrete example showing that implication does not guarantee equivalence.

Model answer: Logical equivalence φ ≡ ψ means φ and ψ have identical truth values under every truth assignment — they always agree. Material implication φ → ψ means: whenever φ is true, ψ is also true — but ψ can be true when φ is false. Example: P → (P ∨ Q) holds for all assignments (it's a tautology), so P logically implies P ∨ Q. But they are not equivalent: when P = false and Q = true, P ∨ Q = true while P = false — different truth values, so no equivalence.

The distinction matters enormously in proofs and formal reasoning. Equivalence licenses bidirectional substitution; implication licenses only one-directional inference. In mathematics, proving A ↔ B (equivalence) requires two separate proofs: A → B and B → A. Proving just one direction gives you implication, not equivalence. Many student errors in logic proofs come from treating a one-way proof as establishing equivalence.