edited by
13,107 views
55 votes
55 votes

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$
edited by

6 Answers

Best answer
63 votes
63 votes

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

edited by
18 votes
18 votes

 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

4 votes
4 votes
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)
1 votes
1 votes
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.
Answer:

Related questions

70 votes
70 votes
5 answers
2
Kathleen asked Sep 12, 2014
13,842 views
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown autom...
18 votes
18 votes
2 answers
4