For positive integers x,y,z, define P(x)=(x=1) y[( z(x=yz))((y=x)(y=1))]. Which is correct?

P(x) means x has exactly two factors other than one and x

GATE 2011 CS (CS1) – Question 40

Engineering Mathematics · Discrete Mathematics: Propositional and First Order Logic · 2 marks · Multiple choice

For positive integers x,y,z, define $P(x)=\neg(x=1)\land\forall y[(\exists z(x=yz))\Rightarrow((y=x)\lor(y=1))]$. Which is correct?

P(x) means x is prime
P(x) means x differs from one
P(x) is always true
P(x) means x has exactly two factors other than one and x

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) P(x) means x is prime

Explanation

The existential product condition identifies y as a positive divisor of x. The implication requires every such divisor to be either one or x, and the first clause excludes x=1. This is precisely primality, A. The quantifier restricts possible divisors rather than asserting all integers divide x.

More Discrete Mathematics: Propositional and First Order Logic questions

GATE 2010 CS (CS1) Q40 – Let F(x,y,t) mean that x can fool y at time t. What does x\, y\, t\, F(x,y,t) express?
GATE 2015 CS (CS2) Q11 – S1: If a candidate is known to be corrupt, he will not be elected. S2: If a candidate is…
GATE 2015 CS (CS2) Q63 – Which first-order formula is logically valid?
GATE 2015 CS (CS3) Q26 – A room contains truth-tellers and liars. An unknown person tosses a fair coin unseen and…
GATE 2021 CS (CS2) Q25 – For S:((P Q) R)((P Q)(Q R)), choose the correct statements.
GATE 2026 CS (CS2) Q11 – For two different persons x and y, the predicate M(x,y) denotes that x knows y. Consider…

All Discrete Mathematics: Propositional and First Order Logic questions →