GATE CS 2008 Q31 — Propositional and First Order Logic

To find which logical expressions are equivalent, let us simplify each of them using the laws of propositional logic:

Expression I:
$P \lor \neg Q$ (already in simplified form)

Expression II:
Using De Morgan's Law:
$\neg(\neg P \land Q) \equiv \neg(\neg P) \lor \neg Q \equiv P \lor \neg Q$

Expression III:
$(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)$
First, simplify the first two terms using the distributive law:
$(P \land Q) \lor (P \land \neg Q) \equiv P \land (Q \lor \neg Q) \equiv P \land \text{True} \equiv P$
Now, substitute this back into the expression:
$P \lor (\neg P \land \neg Q)$
Applying the distributive law again:
$(P \lor \neg P) \land (P \lor \neg Q) \equiv \text{True} \land (P \lor \neg Q) \equiv P \lor \neg Q$

Expression IV:
$(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land Q)$
Simplify the first two terms as before:
$(P \land Q) \lor (P \land \neg Q) \equiv P$
Substitute back:
$P \lor (\neg P \land Q)$
Applying the distributive law:
$(P \lor \neg P) \land (P \lor Q) \equiv \text{True} \land (P \lor Q) \equiv P \lor Q$

Comparing the simplified forms:

• Expression I $\equiv P \lor \neg Q$
• Expression II $\equiv P \lor \neg Q$
• Expression III $\equiv P \lor \neg Q$
• Expression IV $\equiv P \lor Q$