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

.......

4 Answers

+32 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] 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

answered by Active (4.2k points)
edited by
0
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
+3

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. 

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

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.

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

because

F->F = T  

F->T = T

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

IF SOMEONE ASKING yOU PROVE THIS IS TAUTOLOGY THEN UR CORRECT.
0
@parmod, for a instance like:  take x = 6, y = 2 and z = 3 then p(x) is not true
0
@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
0
why option  D is incorrect here.?
+11 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

answered by Loyal (8.7k 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)
+1

=> (implies)has lower precedence than 

+1


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

0

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

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

My bad, understood answer is A only
0
is 1 is prime number ?
–1
Some count and some won't. depends upon person to person or book to book
+1
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.
0
@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
0
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)?
0
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 (747 points)
Answer:

Related questions

+24 votes
7 answers
6


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

43,942 questions
49,497 answers
162,337 comments
65,748 users