The GATE Grind

GATE 2017 CS – Question 12

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

Consider the first-order logic sentence $F: \forall x(\exists y R(x, y))$. Assuming non-empty logical domains, which of the sentences below are implied by $F$?

I. $\exists y(\exists x R(x, y))$

II. $\exists y(\forall x R(x, y))$

III. $\forall y(\exists x R(x, y))$

IV. $\neg \exists x(\forall y \neg R(x, y))$

  1. IV only
  2. I and IV only
  3. II only
  4. II and III only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) I and IV only

Explanation

If every $x$ has some $y$ with $R(x, y)$, then some pair exists, so I follows (the domain is non-empty). IV says "there is no $x$ for which every $y$ fails", which is the same as $\forall x \exists y R(x, y)$, so IV follows. II needs one $y$ that works for all $x$, and III needs every $y$ to be related to some $x$, and neither is implied.