GATE CS 2021 Set 2 Q15 — Propositional and First Order Logic

To determine the nature of the propositional logic assertion $S$, let us analyze its antecedent and consequent separately.

Let the assertion be $S: A \rightarrow C$, where:

• Antecedent ($A$): $(P \wedge Q) \rightarrow R$
• Consequent ($C$): $(P \wedge Q) \rightarrow (Q \rightarrow R)$

Step 1: Simplify the Consequent ($C$)

Using the implication equivalence $X \rightarrow Y \equiv \neg X \vee Y$, we can rewrite $C$ as:

Applying De Morgan's Law and rewriting the inner implication:

By associativity and idempotency of disjunction ($\neg Q \vee \neg Q \equiv \neg Q$):

Applying De Morgan's Law again to group $\neg P \vee \neg Q$:

Converting back to implication form:

Step 2: Compare Antecedent and Consequent

We observe that:

Thus, the antecedent of $S$ is logically equivalent to the consequent of $S$. This makes Option D correct.

Step 3: Analyze the Assertion $S$

Since $A \equiv C$, the assertion $S$ can be written as:

An implication where the hypothesis and conclusion are logically equivalent is always true (a tautology). Thus, $S$ is a tautology, making Option B correct.