The GATE Grind

GATE 2021 CS – Question 17

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple choice

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?

  1. Both $S_1$ and $S_2$ are tautologies.
  2. $S_1$ is a tautology but $S_2$ is not a tautology.
  3. $S_1$ is not a tautology but $S_2$ is a tautology.
  4. Neither $S_1$ nor $S_2$ is a tautology.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $S_1$ is a tautology but $S_2$ is not a tautology.

Explanation

$\neg p \wedge (p\vee q) \equiv \neg p \wedge q$, which implies $q$, so $S_1$ is a tautology. $S_2$ fails when $p=q=1$.