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

Easy step by step Explanation given Predicate

https://gateoverflow.in/2132/gate-cse-2011-question-30?show=537676#a537676

option D

“There exist two distinct proper divisors y1,y2​ such that every proper divisor equals one of them”:

∃y1∃y2  (y1≠y2∧y1≠1∧y1≠x∧y2≠1∧y2≠x ∧ ∀y((∃z  x=yz∧y∉{1,x})⇔(y=y1∨y=y2))).

 

---

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

Let's just understand the definition : 

¬(x=1) means x ≠ 1  and

∃z(x=y∗z) tells that y divides x i.e y/x = z

Now,

∀y( ∃z(x=y∗z) ⇒ (y=x) ∨ (y=1) means 

if "y divides x " then "y" must the number itself (i.e "x") or it must be equal to "1"

we can observe that x has only two factors i.e 1 and x(itself) and It is clearly the definition of prime number 

so,x is a prime number

Hence,option A is correct answer

---

For anyone who's confused why option C is not the answer.

Look at the brackets on the RHS of AND (^)  operator, everything is in the scope of "For all Y".

Now for say x = 2: 

  y = 2, z=1 makes implication: T -> T = T
  y = 1, z = 2 also makes implication T
  y = 3, makes (x= y* z) F, which makes implication LHS false, F -> T = T
So, P is true when x is prime.

Now for x= 4:

  y = 2, z =2, makes implication T -> F = F, which makes RHS of AND operator F and P(x) becomes F.
So, x can't be composite number.
 

ºPeople that are thinkting that $$\forall y(\exists z(x=y\ast z)\; is\; always\; F,\; because\; for\; x\; =\; 2\; and\; y\; =\; 3,\; no\; z\; exists,\; but\; again\; look\; at\; the\; brackets.\; This\; only\; makes\; the\; LHS\; of\; implication\; F,\; which\; makes\; the\; whole\; RHS\; of\; AND\; True.$$

 

 

 

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

chaala baga explain chesav anna thanks

---

@pavansan

Hi bro,

Me too from A.P.I want to ask you some doubts regarding gate.Can you give your linkedin id?

---

@sonapraneeth    truly that Stack Exchange explanation was gold, Thanks for sharing it

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

lets break this in simple terms

first x cant be 1

now for all y given (

if there is some z such that x=y*z then y=1 or y= x)

now take x=4, then for all y(

take y=1, then some z is 4 i.e 4=1*4 so T->T T

take y=4, then some z is 1 i.e. 4=4*1 so T->T T

take y=2,then some z is 2 i.e.4=2*2 so T->F F as y != 2 or x(4) so it is not true for all y hence x= 4 is eliminated in fact all composite will be false and only prime no will be true for all y because for e.g 7=1*7 or 7=7*1 both cases satisfy this for all y and other than 1 and 7 you cant find any other factors .

so x represents all prime no and 1 is not prime as it is already removed at start.

Comments

well explained

 

---

super explaination

 

Answer 4

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 5

Option A is correct 

Condition 1: $\neg(x = 1)$

. It simply states that "$x$ is not equal to 1".

Since our domain is positive integers, this means $x$ must be $2, 3, 4$, or higher.

Condition 2: $\forall y (\exists z (x = y * z) \Rightarrow (y = x) \lor (y = 1))$

Let's break down this implication ($\Rightarrow$):

The "If" part : $\exists z (x = y * z)$

This says, "there exists a positive integer $z$ such that multiplying $y$ by $z$ gives $x$."

 this is the exact definition of divisibility. It means "$y$ is a factor of $x$" (or $y$ divides $x$).

The "Then" part : $(y = x) \lor (y = 1)$

This means "$y$ is equal to $x$, OR $y$ is equal to 1."

Putting Condition 2 together:

"For any positive integer $y$, IF $y$ is a factor of $x$, THEN $y$ must be either $x$ itself or 1."

                                                           $||$

"$x$ is a number greater than 1, AND its only possible factors are 1 and itself."

Mathematically, this is the precise, textbook definition of a prime number.

 

Comments

NIce Explanation :)

Answer 6

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.