Project ForgeSign up free
Discrete Mathematics
Propositional Logic
GATE 2008
Hard

P and Q are two propositions. Which of the following logical expressions are equivalent?

I. P∨¬Q II. ¬(¬P∧Q) III. (P∧Q)∨(P∧¬Q)∨(¬P∧¬Q) IV. (P∧Q)∨(P∧¬Q)∨(¬P∧Q)

  • AOnly I and II
  • Only I, II and III
  • COnly I, II and IV
  • DAll of I, II, III and IV

Explanation

I (P∨¬Q) is true except when (P,Q)=(F,T). II, by De Morgan, ¬(¬P∧Q)=P∨¬Q, identical to I. III covers (T,T),(T,F),(F,F) — true except (F,T), same as I. IV covers (T,T),(T,F),(F,T) — true except (F,F), which is a DIFFERENT truth table from I. So I, II, III are equivalent; IV is not.

Source: GATE CS 2008 (2008)

This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.

Start revising free