Project ForgeDiscrete Mathematics
Predicate Logic
GATE 2009
Medium
Which of the following well-formed formulae are equivalent? I. ¬∀x(P(x)) II. ¬∃x(P(x)) III. ¬∃x(¬P(x)) IV. ∃x(¬P(x))
- AI and III
- I and IV
- CII and III
- DII and IV
Explanation
By quantifier negation rules: I, ¬∀x(P(x)), equals ∃x(¬P(x)), which is exactly IV — so I≡IV. II, ¬∃x(P(x)), equals ∀x(¬P(x)), while III, ¬∃x(¬P(x)), equals ∀x(P(x)) (double negation) — these are different (II≡IV's complement-ish form, not III). So the equivalent pair is I and IV.
Source: GATE CS 2009 (2009)
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.