Skip to content
GATETECH
Official PYQ · 2009Q26Propositional and First Order LogicMCQ1 mark

GATE CS 2009 Q26 — Propositional and First Order Logic

Explain with AI

Consider the following well-formed formulae:

  1. ¬∀x(P(x))\neg \forall x(P(x))
  2. ¬∃x(P(x))\neg \exists x(P(x))
  3. ¬∃x(¬P(x))\neg \exists x(\neg P(x))
  4. ∃x(¬P(x))\exists x(\neg P(x))


Which of the above are equivalent?

Choose one option
View worked solution

Answer: B

To find which of the given well-formed formulae are equivalent, we can apply the standard quantifier negation rules (De Morgan's laws for quantifiers):

  1. ¬∀x ϕ(x)≡∃x ¬ϕ(x)\neg \forall x \, \phi(x) \equiv \exists x \, \neg \phi(x)
  2. ¬∃x ϕ(x)≡∀x ¬ϕ(x)\neg \exists x \, \phi(x) \equiv \forall x \, \neg \phi(x)

Let us simplify each of the given formulae:

  • I. ¬∀x(P(x))≡∃x(¬P(x))\neg \forall x(P(x)) \equiv \exists x(\neg P(x))
  • II. ¬∃x(P(x))≡∀x(¬P(x))\neg \exists x(P(x)) \equiv \forall x(\neg P(x))
  • III. ¬∃x(¬P(x))≡∀x(¬¬P(x))≡∀x(P(x))\neg \exists x(\neg P(x)) \equiv \forall x(\neg \neg P(x)) \equiv \forall x(P(x))
  • IV. ∃x(¬P(x))\exists x(\neg P(x))

Comparing the simplified forms, we can see that formula I and formula IV are identical:

I≡IV≡∃x(¬P(x))\text{I} \equiv \text{IV} \equiv \exists x(\neg P(x))

Thus, I and IV are equivalent.

Correct Option: B

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

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