GateAI
Propositional and First-Order Logic

GATE CSE 2021 Set 2 · Q15

MSQ1 markEasy

Time

Choose the correct choice(s) regarding the following propositional logic assertion SS: S:((P∧Q)→R)→((P∧Q)→(Q→R))S : ((P \wedge Q) \rightarrow R) \rightarrow ((P \wedge Q) \rightarrow (Q \rightarrow R))

Select all that applyOne or more correct

Pick every correct option

Solution

Step-by-step verified solution

Official answer: B) S is a tautology.; D) The antecedent of S is logically equivalent to the consequent of S.

Propositional and First-Order Logic

Let us analyze the given assertion S:A→BS: A \rightarrow B, where:

  • Antecedent: A=(P∧Q)→RA = (P \wedge Q) \rightarrow R

  • Consequent: B=(P∧Q)→(Q→R)B = (P \wedge Q) \rightarrow (Q \rightarrow R)

Using propositional equivalence rules, we can simplify the consequent BB:

B≡(P∧Q)→(Q→R)≡eg(P∧Q)∨(egQ∨R)≡(egP∨egQ)∨egQ∨R≡egP∨egQ∨R≡eg(P∧Q)∨R≡(P∧Q)→R\begin{aligned} B &\equiv (P \wedge Q) \rightarrow (Q \rightarrow R) \\ &\equiv eg(P \wedge Q) \vee ( eg Q \vee R) \\ &\equiv ( eg P \vee eg Q) \vee eg Q \vee R \\ &\equiv eg P \vee eg Q \vee R \\ &\equiv eg(P \wedge Q) \vee R \\ &\equiv (P \wedge Q) \rightarrow R \end{aligned}

Thus, the antecedent AA and consequent BB are logically equivalent (A≡BA \equiv B). This makes (D) correct.

Now, substituting B≡AB \equiv A into the formula SS:

S≡A→A≡egA∨A≡TrueS \equiv A \rightarrow A \equiv eg A \vee A \equiv \text{True}

Therefore, SS evaluates to true for all truth assignments, which means SS is a tautology. This makes (B) correct.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Propositional and First-Order Logic previous year question is Q15 of the GATE CSE 2021 Set 2 paper. Find more GATE CSE PYQs on Propositional and First-Order Logic in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Propositional and First-Order Logic PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Propositional and First-Order Logic in GATE CSE

Propositional and First-Order Logic has 18 GATE CSE PYQs across 16 papers from 2011 to 2026. 2 of them are 1-mark MSQs like this one, and it is the only one in GATE CSE 2021 Set 2.

How GATE tests Propositional and First-Order Logic

More from GATE CSE 2021 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 2 · Q15 · MSQ

Choose the correct choice(s) regarding the following propositional logic assertion S: S : ((P Q) → R) → ((P Q) → (Q → R))

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.