Let p and q be two propositions. Consider the following two formulae in…
2021
Let p and q be two propositions. Consider the following two formulae in propositional logic.
\(S1: (\neg p \land (p \lor q)) \to q \)
\(S2: q \to (\neg p \land (p \lor q))\)
Which one of the following choices is correct?
- A.
Both S1 and S2 are tautologies.
- B.
S1 is a tautology but S2 is not a tautology
- C.
S1 is not a tautology but S2 is a tautology
- D.
Neither S1 nor S2 is a tautology
Attempted by 117 students.
Show answer & explanation
Correct answer: B
Key insight: simplify the antecedent of the first formula and find a counterexample for the second.
Step 1: Simplify the antecedent of S1.
¬p ∧ (p ∨ q) ≡ (¬p ∧ p) ∨ (¬p ∧ q) ≡ false ∨ (¬p ∧ q) ≡ ¬p ∧ q.
Step 2: Conclude S1 is a tautology.
S1 becomes (¬p ∧ q) → q. If the antecedent is true then q is true, so the implication holds; if q is false the antecedent is false, so the implication is still true. Hence S1 is always true.
Step 3: Show S2 is not a tautology by a counterexample.
Take p = true and q = true. Then the antecedent q is true but the consequent ¬p ∧ (p ∨ q) is false, so the implication q → (¬p ∧ (p ∨ q)) is false in this case.
Conclusion: S1 is a tautology, while S2 is not; therefore the correct choice is the statement that S1 is a tautology but S2 is not.
A video solution is available for this question — log in and enroll to watch it.