The GATE Grind

GATE 2023 CS – Question 26

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 1 mark · Multiple select

Geetha has a conjecture about integers, which is of the form $\forall x\,[P(x) \implies \exists y\, Q(x,y)]$, where P is a statement about integers, and Q is a statement about pairs of integers. Which of the following (one or more) option(s) would imply Geetha's conjecture?

  1. $\exists x\,[P(x) \wedge \forall y\, Q(x,y)]$
  2. $\forall x\,\forall y\, Q(x,y)$
  3. $\exists y\,\forall x\,[P(x) \implies Q(x,y)]$
  4. $\exists x\,[P(x) \wedge \exists y\, Q(x,y)]$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $\forall x\,\forall y\, Q(x,y)$; (C) $\exists y\,\forall x\,[P(x) \implies Q(x,y)]$

Explanation

(B) gives Q for every pair, so the conjecture holds. In (C) one fixed y works for every x, which gives the required ∃y for each x. (A) and (D) assert things about only some x.