GATE CS 2014 Set 1 Q.63 (CS Q.53): Propositional and First-Order Logic

Which one of the following propositional logic formulas is TRUE when exactly two of $p$ , $q$ , and $r$ are TRUE?

$(p \leftrightarrow q) \land r \lor (p \land q \land \sim r)$

$(\sim(p \leftrightarrow q) \land r) \lor (p \land q \land \sim r)$

$(p \to q) \land r \lor (p \land q \land \sim r)$

$(\sim(p \leftrightarrow q) \land r) \land (p \land q \land \sim r)$

Official answer and solution

Solution

Construct the truth condition for 'exactly two of p, q, and r are true' and verify against the logical formula.

There are 3 truth assignments where exactly two of $\{p, q, r\}$ are TRUE:

Consider the formula in Option B:

(\sim(p \leftrightarrow q) \land r) \lor (p \land q \land \sim r)

Let us analyze both terms:

The term $(p \land q \land \sim r)$ is TRUE if and only if $p = T, q = T, r = F$ (Case 1).
The term $(\sim(p \leftrightarrow q) \land r)$ requires $r = T$ and $\sim(p \leftrightarrow q) = T$ .
The condition $\sim(p \leftrightarrow q)$ is equivalent to $p \neq q$ (one is true, one is false).
Along with $r = T$ , this holds if and only if:
$(p = T, q = F, r = T)$ or $(p = F, q = T, r = T)$ (Cases 2 and 3).

The disjunction of the two terms is therefore TRUE in exactly Cases 1, 2, and 3, and FALSE in all other five truth assignments.

Thus, formula B is TRUE when exactly two of $p, q, r$ are TRUE.

Final answer

Common trap

Selecting option A where $(p \leftrightarrow q) \land r$ is satisfied when $p=q=r=T$ , meaning all three are true rather than exactly two.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.