Question

Let \(p\) and \(q\) be two propositions. Consider the following two formulae in propositional logic.
\[ S_1 : (\neg p \wedge (p \vee q)) \rightarrow q \] \[ S_2 : q \rightarrow (\neg p \wedge (p \vee q)) \] Which one of the following choices is correct?

• A. Both \(S_1\) and \(S_2\) are tautologies.
• B. \(S_1\) is a tautology but \(S_2\) is not a tautology.
• C. \(S_1\) is not a tautology but \(S_2\) is a tautology.
• D. Neither \(S_1\) nor \(S_2\) is a tautology.

Hint:

An implication is a tautology if it is true for all possible truth values of its variables.

Answer 1

The Correct Option is B

Step 1: Simplify \(S_1\).
Consider the antecedent of \(S_1\):
\[ \neg p \wedge (p \vee q) \] Using distributive law: \[ (\neg p \wedge p) \vee (\neg p \wedge q) \] Since \(\neg p \wedge p\) is always false, this simplifies to: \[ \neg p \wedge q \] Thus, \[ S_1 : (\neg p \wedge q) \rightarrow q \] This implication is always true, because whenever \(\neg p \wedge q\) is true, \(q\) is necessarily true. Hence, \(S_1\) is a tautology.

Step 2: Analyze \(S_2\).
\[ S_2 : q \rightarrow (\neg p \wedge (p \vee q)) \] Take a counterexample: let \(q = \text{true}\) and \(p = \text{true}\).
Then: \[ \neg p = \text{false}, (p \vee q) = \text{true} \] So: \[ \neg p \wedge (p \vee q) = \text{false} \] Thus, \(q \rightarrow \text{false}\) becomes false. Hence, \(S_2\) is not a tautology.

Step 3: Conclusion.
\(S_1\) is a tautology, but \(S_2\) is not a tautology.

Final Answer: (B)