The GATE Grind

GATE 2026 DA – Question 48

Artificial Intelligence · Logic: propositional and predicate · 2 marks · Multiple select

Let $P(x)$ be a predicate.

Which of the following statements is/are NOT valid in first-order logic?

  1. $\forall x\ P(x) \Rightarrow \exists x\ P(x)$
  2. $\exists x\ P(x) \Rightarrow \forall x\ P(x)$
  3. $\exists x\ P(x) \Leftrightarrow \forall x\ P(x)$
  4. $\forall x\ P(x) \Rightarrow \exists x\ \neg P(x)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\exists x\ P(x) \Rightarrow \forall x\ P(x)$; (C) $\exists x\ P(x) \Leftrightarrow \forall x\ P(x)$; (D) $\forall x\ P(x) \Rightarrow \exists x\ \neg P(x)$

Explanation

A is valid, since a domain is never empty in first-order logic and what holds for all of it holds for at least one element. In B some element may have the property while another does not, so $\exists x\ P(x)$ can be true and $\forall x\ P(x)$ false, which makes B not valid. C is the implication of B with the reverse, so it is not valid either. In D, if $P$ holds for every element then no element has $\neg P$, so the conclusion is false while the premise is true and D is not valid.