GATE CSE 2019 | Question: 35

Question

Consider the first order predicate formula $\varphi$:

$\forall x [ ( \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)))]$

Here $a \mid b$ denotes that  $ ’a \text { divides } b’ $ , where  $a$ and $b$ are integers. Consider the following sets:

• $S_1: \{1, 2, 3, \dots , 100\}$
• $S_2:$ Set of all positive integers
• $S_3:$ Set of all integers

Which of the above sets satisfy $\varphi$?

• A. $S_1$ and $S_2$
• B. $S_1$ and $S_3$
• C. $S_2$ and $S_3$
• D. $S_1, S_2$ and $S_3$

Comments

Prime numbers exists only for positive integers, because if we have included -ve numbers then -1 would have divided all number which violates the definition of prime numbers.

In above example let P=(∀zz∣x⇒((z=x)∨(z=1))  and Q =∃w(w>x)∧(∀zz∣w⇒((w=z)∨(z=1))) if P itself false fo -ve integers then no need to check for Q in above example for -ve integers P is itself false; So, P=false then P→ Q is always true.

So, from above explanation S3 must be valid option

S2 is is any way true since x and w are prime numbers and for positive integers prime number exists

S1 should be false. because for every prime number x there exist another prime number where x<y , so finite set option is wrong.

So answer → (C) S2 and S3 are true

---

So to check you have to check if for given Domain it is always true or not.

So you can broadly see this is of type (A→ B) → C  and for it to be true you should analyze what cases for A,B,C exists for which it can be true for example:

A           B          C

F          T/F        T

T            T          T

T            F         T/F

you should take each domain given and then check for A,B,C by cases as shown above if it is true then that domain is valid. I think you can check it in like 1 min or so, yeah done

---

visualization to understand what question asking

Answer 1

$\text{The definition of z and w is clearly saying that both w and x are prime numbers as they are divisible by themselves or 1.}$

∀x { ∃w | w<x }

$\text{w,x are Prime numbers}$

$\text{This means for each element in set if that element is prime number, you will definately see its brother who is also prime but he is bigger than him.}$

 

Hence  A1 is false as for 97, next big prime is out of the range.

A2 is true.

Also A3 is true as It reduces to A2 only in terms of solving

 

 

 

Answer 2

The answer for the question is all the three statements are true..left hand side of the statement is always false interms making the statement as True.

Comments

@Digvijay Pandey could you please check it