GATE 2019 CS – Question 45
Consider the first order predicate formula $\varphi$:
$$\forall x\left[(\forall z\ z|x\Rightarrow((z=x)\vee(z=1)))\Rightarrow\exists w\,(w>x)\wedge(\forall z\ z|w\Rightarrow((w=z)\vee(z=1)))\right]$$
Here '$a|b$' denotes that '$a$ divides $b$', where $a$ and $b$ are integers. Consider the following sets:
S1. $\{1,2,3,\dots,100\}$
S2. Set of all positive integers
S3. Set of all integers
Which of the above sets satisfy $\varphi$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) S2 and S3
Explanation
Over S1={1,...,100}, x=97 satisfies the antecedent but there is no larger admissible prime in S1, so the formula fails. Over the positive integers S2, arbitrarily large primes make it true.
With quantifiers over all integers S3, negative divisors change the literal formula. In particular x=-1 has only divisors -1 and 1, so its antecedent is true. A witness w>-1 would be nonnegative; every nonzero such w has negative divisors violating the stated condition, and w=0 also fails. Thus S3 fails under literal integer divisibility.
The appended historical key selects **C (S2 and S3)**, treating the divisors as positive. That scoring answer is preserved, while the literal all-integer interpretation gives only S2, absent from the options.
More Discrete Mathematics: Propositional and First Order Logic questions
- GATE 2018 CS Q38
- GATE 2015 CS (CS1) Q19
- GATE 2016 CS (CS1) Q11
- GATE 2017 CS (CS1) Q11
- GATE 2017 CS (CS1) Q12
- GATE 2017 CS (CS1) Q39
All Discrete Mathematics: Propositional and First Order Logic questions →