GATE 2023 CS – Question 26
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?
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.
More Discrete Mathematics: Propositional and First Order Logic questions
- GATE 2021 CS (CS1) Q17
- GATE 2020 CS Q49
- GATE 2019 CS Q45
- GATE 2018 CS Q38
- GATE 2015 CS (CS1) Q19
- GATE 2016 CS (CS1) Q11
All Discrete Mathematics: Propositional and First Order Logic questions →