Let 𝑥 and 𝑦 be two propositions. Which of the following statements is a…
2024
Let 𝑥 and 𝑦 be two propositions. Which of the following statements is a tautology /are tautologies?
- A.
(¬𝑥 ∧ 𝑦 ) ⟹ (𝑦 ⟹ 𝑥)
- B.
(𝑥 ∧ ¬𝑦 ) ⟹ (¬𝑥 ⟹ 𝑦)
- C.
(¬𝑥 ∧ 𝑦 ) ⟹ (¬𝑥 ⟹ 𝑦)
- D.
(𝑥 ∧ ¬𝑦 ) ⟹ (𝑦 ⟹ 𝑥)
Attempted by 112 students.
Show answer & explanation
Correct answer: B, C, D
Correct tautologies:
(x ∧ ¬y) ⇒ (¬x ⇒ y): tautology.
Reason: The antecedent x ∧ ¬y is true only when x = true and y = false. In that case ¬x is false, so (¬x ⇒ y) is true (false implies false is true). In all other assignments the antecedent is false and the implication is vacuously true.
(¬x ∧ y) ⇒ (¬x ⇒ y): tautology.
Reason: If ¬x ∧ y holds then ¬x is true and y is true, so (¬x ⇒ y) is true. If ¬x ∧ y does not hold the implication is vacuously true.
(x ∧ ¬y) ⇒ (y ⇒ x): tautology.
Reason: When x ∧ ¬y holds we have y = false, so (y ⇒ x) is true (false implies anything is true). Otherwise the antecedent is false and the implication is vacuously true.
Non-tautology:
(¬x ∧ y) ⇒ (y ⇒ x): not a tautology.
Counterexample: take x = false and y = true. Then (¬x ∧ y) is true but (y ⇒ x) is false, so the implication is false. Therefore the formula is not always true.
Summary: The formulas (x ∧ ¬y) ⇒ (¬x ⇒ y), (¬x ∧ y) ⇒ (¬x ⇒ y), and (x ∧ ¬y) ⇒ (y ⇒ x) are tautologies. The formula (¬x ∧ y) ⇒ (y ⇒ x) is not a tautology.