Skip to content
GATETECH
Official PYQ · 2014Set 1 · Q53Propositional and First Order LogicMCQ1 mark

GATE CS 2014 Set 1 Q53 — Propositional and First Order Logic

Explain with AI

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

Choose one option
View worked solution

Answer: B

To find the correct propositional logic formula, let us represent the condition "exactly two of p,q,p, q, and rr are TRUE" using truth values.

The assignments of (p,q,r)(p, q, r) that satisfy this condition are:

  1. p=0,q=1,r=1  ⟹  ∼p∧q∧rp = 0, q = 1, r = 1 \implies \sim p \wedge q \wedge r
  2. p=1,q=0,r=1  ⟹  p∧∼q∧rp = 1, q = 0, r = 1 \implies p \wedge \sim q \wedge r
  3. p=1,q=1,r=0  ⟹  p∧q∧∼rp = 1, q = 1, r = 0 \implies p \wedge q \wedge \sim r

Taking the disjunction (OR) of these three cases gives the required formula:

Formula=(∼p∧q∧r)∨(p∧∼q∧r)∨(p∧q∧∼r)\text{Formula} = (\sim p \wedge q \wedge r) \vee (p \wedge \sim q \wedge r) \vee (p \wedge q \wedge \sim r)

We can simplify the first two terms by factoring out rr:

(∼p∧q∧r)∨(p∧∼q∧r)≡[(∼p∧q)∨(p∧∼q)]∧r(\sim p \wedge q \wedge r) \vee (p \wedge \sim q \wedge r) \equiv [(\sim p \wedge q) \vee (p \wedge \sim q)] \wedge r

Recall that (∼p∧q)∨(p∧∼q)(\sim p \wedge q) \vee (p \wedge \sim q) represents the Exclusive-OR (XOR) operation, p⊕qp \oplus q, which is the negation of the bi-conditional (XNOR) operation, ∼(p↔q)\sim(p \leftrightarrow q):

p⊕q≡∼(p↔q)p \oplus q \equiv \sim(p \leftrightarrow q)

Substituting this back into our simplified expression:

Formula=(∼(p↔q)∧r)∨(p∧q∧∼r)\text{Formula} = (\sim(p \leftrightarrow q) \wedge r) \vee (p \wedge q \wedge \sim r)

This matches Option B.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Propositional and First Order Logic questions