The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+27 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$
asked in Mathematical Logic by Veteran (96.2k points)
edited by | 3.2k views



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???

please anyone suggest

4 Answers

+34 votes
Best answer

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.
[email protected]
[email protected]

answered by Active (4.2k points)
edited by
ANS should be C right

LHS is always false .

eg: just take x=4 , y =6

there is no integer positive z exist to write x= y * z

y(z(x=yz) says for all y thier exist a z..

x is not independent since statement true for prime no. 

if statemnt true for all x no. then c is correct. 

let just take x =3 as it is prime

take y =7 , then which value of z satisfies x=y*z.

please correct me if i am wrong

A-> B says if  A is true then B is also true.

U said left side is false then how u comment about  RHS.

Defination says . iF x= Y*Z then Y=x or Z=1. then only true otherwise false.

now u take x =3 then either u take z=1 or y= 3 then only true otherwise false.

if LHS false always means , p(x) is always true irrespective of value of x


F->F = T  

F->T = T

that is what i mean.
Keep in mind ur not prove it is tautology or not but YOUR  FINDIND WAT IS STATEMN T IS SAYING.. HOPE U GOT IT.'

@parmod, for a instance like:  take x = 6, y = 2 and z = 3 then p(x) is not true
@parmod If x=1 then ~x gets false and F^anything gets false but the c part is saying P(x) is true so c is wrong answer
why option  D is incorrect here.?
+13 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.


answered by Loyal (9.3k points)
+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)
answered by Active (2.6k points)

=> (implies)has lower precedence than 


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


(x=1) what is the negation of this  ¬(x=1)= ¬x1 or  x 1.

x is not equal to 1
A and B both should be the answers right?

My bad, understood answer is A only
is 1 is prime number ?
Some count and some won't. depends upon person to person or book to book
P(x) = If x != 1 and x can be expressed in the multiple of two numbers y and z then

1. y = x and z = 1 or

2. y = 1 and z = x

=> x is the number which can not be expressed in the multiples of any other number except 1 and itself i.e. Prime Number hence option A.

NOTE: Also don't be confused with option B as when x = 1, left side is false and right side true which in turn whole preposition TRUE.
@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.
0 votes


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.

answered by Junior (745 points)

Related questions

+28 votes
7 answers
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,548 questions
54,174 answers
71,128 users