The GATE Grind

GATE 2019 CS – Question 45

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

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$?

  1. S1 and S2
  2. S1 and S3
  3. S2 and S3
  4. S1, S2 and S3

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

All Discrete Mathematics: Propositional and First Order Logic questions →