GATE CSE 2011 | Question: 30

Question

Which one of the following options is CORRECT given three positive integers $x, y$ and $z$, and a predicate
$$P\left(x\right) = \neg \left(x=1\right)\wedge \forall y \left(\exists z\left(x=y*z\right) \Rightarrow \left(y=x\right) \vee \left(y=1\right) \right)$$

• A. $P(x)$ being true means that $x$ is a prime number
• B. $P(x)$ being true means that $x$ is a number other than $1$
• C. $P(x)$ is always true irrespective of the value of $x$
• D. $P(x)$ being true means that $x$ has exactly two factors other than $1$ and $x$

Comments

Option B :

P(x)=(¬(x=1)∧∀y(∃z (x=y∗z)⟹ ((y=x)∨(y=1)))

take x=4 bolded part true. And we are now making non bolded right part false. 4 = 2*2 means y=2 and z=2.  implication become false.

Option C :

same reason as Option B.

Option D :

P(x)=(¬(x=1)∧∀y(∃z (x=y∗z)⟹ ((y=x)∨(y=1)))

take x=6 bolded part true. And we are now making non bolded right part false. 6 = 2*3 means y=2 and z=3.  implication become false.

Option A:

P(x)=(¬(x=1)∧∀y(∃z (x=y∗z)⟹ ((y=x)∨(y=1)))

take x=7 bolded part true. And we are now making non bolded right part false. 7 = 1*7 or 7*1 and no other values can be possible because prime number.means y,z both =7 or 1 .  implication become true.

So eventually true.

---

@Deepak Poonia

Sir , Is B one way statement or both ways?

If one way then it should also be correct ryt!

Weak but correct.

---

how to write B & D in terms of FOL

Answer 1

Answer is (A).

$P\left(x\right)= (\neg \left(x=1\right)\wedge \forall y\left(\exists z\left(x=y*z\right) \implies (\left(y=x\right) \vee \left(y=1\right) \right))$

Statement:  $x$ is not equal to $1$ and if there exists some $z$ for all $y$ such that product of $y$ and $z$ is $x$, then $y$ is either the number itself or $1$. This is the definition of prime numbers.

Alternative approach:
The formula

$$\exists x \forall y \forall z[\times (y, z, x) \rightarrow ((y = 1) \vee (z = 1))]$$

expresses the statement "there exists a prime number" (the number $1$ also satisfies this statement).

Note here that $\times (y, z, x)$ is equivalent to $(x = y \times z)$.
but $¬(x=1)$ removes $1$ as satisfying given number in question's formula, so the option (A) is True.
ref@ https://en.wikibooks.org/wiki/Logic_for_Computer_Science/First-Order_Logic#Semantics
ref@ http://math.stackexchange.com/questions/1037795/what-is-the-meaning-of-this-predicate-statement

Comments

Yeah option D seems to be correct too. Please help.

---

@aniket3009 Option D says P(x) being true means that x has exactly two factors other than 1 and x.

consider prime number 7, Factors of 7 are 1 and 7. So how can it have factors other than 1 and 7.

So option D is wrong.

---

@debasree88 

P(x)=¬(x=1)∧∀y(∃z(x=y∗z)⇒(y=x)∨(y=1))

Let focus on second part :- B =  ∀y(∃z(x=y∗z)⇒(y=x)∨(y=1))

if x = prime (suppose 5)  B will be false if there exit atleast one y  for which ∃z(x=y∗z)⇒(y=x)∨(y=1) is false.

now check for y = 1,2,3,4,5,6 (or any Positive integer)

{ if y = 1 then Z will be  5 hence B become (T--->T) which results in True.}

{if y = 2 then Z does not exist hence B become (F--->F) which results in True.}

{if y = 3 then Z does not exist hence B become (F--->F) which results in True.}

{if y = 4 then Z does not exist hence B become (F--->F) which results in True.}

{if y = 5 then Z will be 1 hence B become (T-->T) which results in True.}

and so on

So by observing above scenario “ if x is prime then B is True for all value of y”.

if x = not Prime (suppose 4)  B will be false if there exit atleast one y  for which ∃z(x=y∗z)⇒(y=x)∨(y=1) is false.

now check for y = 1,2,3,4,5,6 (or any Positive integer)

{ if y = 1 then Z will be  4 hence B become (T--->T) which results in True.}

{ if y = 2 then Z will be  2 hence B become (T--->F) which results in False.}

 now without checking further we can say that B is False Hence P(x) is false for x = composite number.

Please correct me if I am wrong!

Answer 2

 So the predicate is evaluated as
    P(x) = (¬(x=1))∧(∀y(∃z(x=y*z)⇒((y=x)∨(y=1))))
P(x) being true means x ≠ 1 and
For all y if there exists a z such that x = y*z then
y must be x (i.e. z=1) or y must be 1 (i.e. z=x)

 It means that x have only two factors first is 1
and second is x itself.

This predicate defines the prime number.

Source: http://clweb.csa.iisc.ernet.in/rahulsharma/gate2011key.html

Answer 3

Let's consider here   P= R  AND S ( for simplification)

We know that   T AND T=T

                       F AND F=F

                       F AND T =F

To make P(x) = T ,  need to make both R and S , True.

R is true , i.e. NOT(x=1) is true , so ( x=1) is false

hence x is a number other than 1 . (option B)

Comments

@arjun sir, question has wrong braces paired. what is given in question is telling "first implies than and". if you want to convey the message you told, "higher priority of implies" than you should add parantheses in question same as in your comment

---

it is given that if p(x) is true, then... all the options.
why we are ignoring the fact that p(x) is true when LHS and RHS have combinations of (F T, and F F) also, and only considering (T T)?

---

Really nice Discussion on this Question.Thanks, everyone.

Answer 4

The predicate is evaluated as
    P(x) = (¬(x=1))∧(∀y(∃z(x=y*z)⇒((y=x)∨(y=1))))

 P(x) being true means x ≠ 1 and For all y if there exists z such that x = y*z then
 y must be x (i.e. z=1) or y must be 1 (i.e. z=x)
 
 It means that x have only two factors first is 1 
 and second is x itself.
 
This predicate defines the prime number.