9,806 views

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

1. $P(x)$ being true means that $x$ is a prime number
2. $P(x)$ being true means that $x$ is a number other than $1$
3. $P(x)$ is always true irrespective of the value of $x$
4. $P(x)$ being true means that $x$ has exactly two factors other than $1$ and $x$

what is the domain of y here? Is it belongs to set of the factors of a given number x or y belongs to natural number.

For 1st one irrespective of x is prime or composite, antecedent of implication is always true.Then we've to check for consequence part whether that will be T or F.

For 2nd one if y belongs to N then antecedent is always false which implies that the total implication will always be true without checking consequence part.

I think y belongs to set of factors of any given x, otherwise option B can be true???

nice ques

Option B :

P(x)=(¬(x=1)∧∀y(∃z (x=yz)⟹ ((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=yz)⟹ ((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=yz)⟹ ((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.

$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.
[email protected] https://en.wikibooks.org/wiki/Logic_for_Computer_Science/First-Order_Logic#Semantics
[email protected] http://math.stackexchange.com/questions/1037795/what-is-the-meaning-of-this-predicate-statement

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.

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!

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.

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)

@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.

P(x)=¬(x=1)∧∀y(∃z(x=y∗z)⇒(y=x)∨(y=1))   here a simple way to solve it is  according to options  A. P(x) being true means that x is a prime number.  put here x=1 in LHS which is TRUE so negation of this will be FALSE and false logical and with anything will be false so LHS of implication() is false and we know that if LHS of implication is false then we don't care about RHS because F⇒  ANYTHING WILL give TRUE.  so

A is right option.