04-BS-16 · December 2013

Question 1 of 12: Logic — Quantified Statements and Predicates

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 1: Logic — Quantified Statements and Predicates (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Approach. Part (a) reads each quantified formula left-to-right, translating the logical connectives into ordinary English; part (b) is the reverse process — build the formula from the English statement using the four given predicates plus $M$ for the product.

(a-i) $\exists x(P(x)\land E(x))$. "There exists an integer $x$" that is BOTH prime AND even: $\boxed{\text{There is an even prime number}}$ (true — witnessed by $x=2$).
(a-ii) $\forall x\forall y(P(x)\land P(y)\land L(x,y)\to\neg E(y))$. For every pair of integers $x,y$: if $x$ and $y$ are both prime and $x
(a-iii) $\forall x\exists y(L(x,y)\land P(y))$. For every integer $x$ there exists an integer $y$ such that $x
(b-a) "The product of two primes is not prime." For all integers $x,y,z$: if $x,y$ are prime and their product is $z$, then $z$ is not prime: $$\boxed{\forall x\,\forall y\,\forall z\big(P(x)\land P(y)\land M(x,y,z)\to\neg P(z)\big)}$$
(b-b) "Every positive integer has a prime factor." For every positive integer $x$, there exists a prime $y$ and an integer $z$ such that $y\cdot z=x$ (i.e. $M(y,z,x)$): $$\boxed{\forall x\big(x>0\to\exists y\,\exists z\,(P(y)\land M(y,z,x))\big)}$$

Final results — Question 1
Part	Result
(a-i)	There is an even prime number
(a-ii)	For any two primes with $x<y$, $y$ is not even
(a-iii)	Every integer has a larger prime
(b-a)	$\forall x\forall y\forall z(P(x)\land P(y)\land M(x,y,z)\to\neg P(z))$
(b-b)	$\forall x(x>0\to\exists y\exists z(P(y)\land M(y,z,x)))$

Topic: Translating between quantified predicate logic and English.

Key relations: $\forall x\exists y\,\phi$ reads "for every $x$ there is some $y$ (possibly depending on $x$) with $\phi$"; $\exists x\,\phi$ needs only one witness; $\forall x(\alpha\to\beta)$ is the standard shape for "every $\alpha$ is a $\beta$."

Why this works: The order of quantifiers matters — in (a-iii) $y$ is chosen AFTER $x$, so it can depend on $x$ (a different larger prime for each $x$), which is exactly the correct reading of "no largest prime." Building (b) requires introducing exactly the predicates given ($M$ for multiplication) rather than inventing new symbols.

Common pitfall: Swapping $\forall x\exists y$ for $\exists y\forall x$ changes the meaning entirely (one fixed $y$ that is bigger than every $x$ — impossible); forgetting the $x>0$ guard in (b-b) since $P$ is defined over all integers, not just positive ones.

Source: Rosen, Discrete Mathematics and Its Applications, §1.4-1.5 (predicates and quantifiers, nested quantifiers).

← Paper overview Next: Question 2 →