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

S1 is a subset of S2 & S3.

If S1 doesn't satisfy the given relation, S2 & S3 would also not satisfy.

 

If we closely observe the options, we can eliminate 2 options (B & C).

[Hint : S1 is subset of S2, which in turn is subset of S3].

Answer should be either A or D.

I took risk (as the probability of getting it right was 0.5) & marked it as A.

Answer 2

Consider $(\forall z\ z|x \rightarrow((z=x) \vee (z=1)))=P$ , and
$\exists w\ (w>x)\wedge (\forall z\ z|w \rightarrow ((w=z)\vee (z=1))) =Q$.

The question becomes $\forall x[P\rightarrow Q]$.

Consider $x=3,z=5 \ and\ w=10$. Consider Q first:
w > z = TRUE
(5|10 = TRUE $\rightarrow$ (5=10)$\vee$(z=1) = FALSE), and we know that $TRUE\rightarrow FALSE=FALSE$ therefore Q becomes FALSE.

Consider P next:
(5|3 = FALSE $\rightarrow$ (5=3)$\vee$(5=1) = FALSE), and $FALSE\rightarrow FALSE = TRUE$ therefore P becomes TRUE.

$\varphi=[TRUE\rightarrow FALSE]=FALSE$ So S1 will be false.
Looking at options, Option C automatically becomes right answer.

Answer 3

 

$∀x[(∀zz∣x⇒((z=x)∨(z=1)))→∃w(w>x)∧(∀zz∣w⇒((w=z)∨(z=1)))]$

For all x [ (If for all z, z divides x then either z=x or z=1) → (There exists a w, such that w is greater than x and (for all z, if z divides w then either w=z or z=1)

For all x [(x is a prime number) → (w is a prime number and w>x)]

 

In S1, 7 is a prime number. 881 > 7, and 881 is also a prime number. But 881 does not belong to S1.

S2 is true, because prime numbers can't be negative.

S3 is true.

 

Option C

Answer 4

$\forall x [ ( \forall z \: z \mid x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))]$

The above expression can be written as $\forall x [ \underbrace {( \forall z \{\: z \mid x \Rightarrow (( z=x) \vee (z=1))\})}_{Part-1} \rightarrow \underbrace{\exists w ( w > x) \wedge (\forall z\{\: z \mid w \Rightarrow ((w=z) \vee (z=1))\})}_{Part-2}]$

Now, part 1 says that for every x (we have assumed the domain to be set of positive integers) the value inside the curly Part 1 curly braces should be true for all values of z then only the expression part-1 will return true.

Now let z divides x, The possible combinations of z which divides x is:

• only z=1 divides x no other integer divides x then x value is 1 and part 1 expression is true(LHS is true and also RHS is true for z=1 for other values LHS false means the whole sentence for that value of z will be true and the expression part -1 will be true).
• when z=1 and z=x divide x then x is a prime number(similar analysis as the above point can be done and we will get the whole part-1 as true).
• when for a particular x, z can have more than 2 values. For example x = 4, z=1,2,4 . when z=2 we can observe that "z|x" becomes true but the RHS becomes false so part-1 becomes false.

Now for part 2 if the first part is true then only we need to check the second part 

• for z=1 only the expression says that for w>x means there exists a value such that it is >x and for all  z w has 1 or itself as divisors(same analysis as part 1). so when z=1 only w can 2,3 ... etc
• for z=1 and z=x part 2 for this combination says that there is a prime number which is greater than the number x($\forall x$ means that we should have (smaller,larger) pair for every prime number. so only infinite set can satisfy this condition) .

Now for S1 the set is finite(97 prime number does not have a prime greater that itself in the set). so for S1 the expression is not satisfiable.

For S2 set is infinite and every set of prime have (smaller,larger) pair  so satisfiable

For S3 also it is satisfiable.

so option (C) is correct