Which one of the following options is CORRECT given three positive integers x, y, and z, and a predicate P(x) = ~(x = 1) ^ (forall y)(forall z)((x = y * z) -> (y = 1 v z = 1)) 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

GATE 2011 · Discrete Mathematics · First Order Logic · medium

Answer: A. P(x) being true means that x is a prime number

1. Parse the conjunction: P(x) = [x != 1] AND [for all y,z: if x=y*z then y=1 or z=1]. First clause: x is greater than 1 (positive integers only, so x >= 2). Second clause: x cannot be factored into two numbers both > 1.
2. Match to definition of prime: P(x) is true iff x >= 2 (x != 1 in positive integers) AND every factorization of x is trivial (one factor is 1). This is precisely the definition of a prime number. Check: P(6) is false because 6=2*3 with neither factor 1. P(7) is true because 7=1*7 is the only factorization.