Skip to content
GATETECH
Official PYQ · 2002Q1.8Propositional and First Order LogicMCQ1 mark

GATE CS 2002 Q1.8 — Propositional and First Order Logic

Explain with AI

"If XX then YY unless ZZ" is represented by which of the following formulas in propositional logic? ("¬\neg" is negation, "∧\land" is conjunction, and "→\rightarrow" is implication)

Choose one option
View worked solution

Answer: A

To translate the statement "If XX then YY unless ZZ" into propositional logic, we can break it down as follows:

  1. The phrase "unless ZZ" means "if not ZZ" (¬Z\neg Z).
  2. Thus, the statement can be rephrased as: "If XX is true, then (if ZZ is not true, then YY is true)".

This directly translates to the logical formula:

X→(¬Z→Y)X \rightarrow (\neg Z \rightarrow Y)

Using the implication identity A→B≡¬A∨BA \rightarrow B \equiv \neg A \lor B, we can simplify this expression:

¬Z→Y≡¬(¬Z)∨Y≡Z∨Y\begin{aligned} \neg Z \rightarrow Y &\equiv \neg(\neg Z) \lor Y \\ &\equiv Z \lor Y \end{aligned}

Substituting this back into the main formula:

X→(Z∨Y)≡¬X∨Z∨Y\begin{aligned} X \rightarrow (Z \lor Y) &\equiv \neg X \lor Z \lor Y \end{aligned}

Now, let us simplify Option A, (X∧¬Z)→Y(X \land \neg Z) \rightarrow Y:

(X∧¬Z)→Y≡¬(X∧¬Z)∨Y≡(¬X∨¬(¬Z))∨Y(by De Morgan’s Law)≡¬X∨Z∨Y\begin{aligned} (X \land \neg Z) \rightarrow Y &\equiv \neg(X \land \neg Z) \lor Y \\ &\equiv (\neg X \lor \neg(\neg Z)) \lor Y \quad \text{(by De Morgan's Law)} \\ &\equiv \neg X \lor Z \lor Y \end{aligned}

Since both expressions simplify to the exact same truth-functional form, Option A is the correct representation.

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

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