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

S_1 is a tautology but S_2 is not a tautology.

Both S_1 and S_2 are tautologies.

S_1 is a tautology but S_2 is not a tautology.

S_1 is not a tautology but S_2 is a tautology.

Neither S_1 nor S_2 is a tautology.

GATE CSE 2021 Set 1 Q17: Which of two implications involving p and q are tautologies

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?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: B (official GATE 2021 final answer key)

Concept used: Simplify: $\neg p \wedge (p \vee q) \equiv \neg p \wedge q$ (disjunctive syllogism).

First step: With $\neg p \wedge q$ in place, check $S_2$ at $p = q = \text{true}$ .

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key