Question 1 of 12

Question 1 (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.

Given. (a) The compound proposition $p \leftrightarrow (\neg p \land q)$ over Boolean variables $p,q$. (b) The quantified statement $\exists n\,(n+1\gt n^2)$ with universe $\mathbb{Z}$. (c) Two candidate predicate-logic sentences built from the same one-place predicates $P,Q$.

Find. (a) The full truth table. (b) True or false, with justification. (c) Whether the two sentences are logically equivalent, with a proof or counterexample.

Approach. (a) enumerate all four rows of $p,q$; (b) exhibit a witness integer (or show none exists); (c) test the claimed equivalence with a concrete predicate pair over a small domain.

1. (a) Truth table. Evaluate $\neg p \land q$ then $p \leftrightarrow (\neg p\land q)$ row by row: $$\begin{array}{cc|c|c}p&q&\neg p\land q&p\leftrightarrow(\neg p\land q)\\\hline T&T&F&F\\T&F&F&F\\F&T&T&F\\F&F&F&T\end{array}$$ The compound proposition is true only when $p$ and $q$ are both false. $\boxed{\text{True only in the row } p=F,\,q=F}$
2. (b) Truth value of $\exists n\,(n+1\gt n^2)$. Test small integers: $n=0$ gives $1\gt 0$ (true); $n=1$ gives $2\gt 1$ (true); for $|n|\ge 2$ the quadratic term dominates and $n+1\le n^2$. A single witness suffices to make the existential true, so: $$\exists n\,(n+1\gt n^2)\ \text{is}\ \boxed{\text{TRUE}}\ (\text{witnessed by }n=0\text{ or }n=1).$$
3. (c) Are the two sentences equivalent? Take the domain $\mathbb{Z}$ with $P(x)$: "$x$ is even" and $Q(x)$: "$x$ is odd". Then $\forall x(P(x)\to Q(x))$ is false (e.g. $x=2$ is even, so $P(2)$ true, but $Q(2)$ false, so the conditional fails at $x=2$). Meanwhile $\forall x\,P(x)$ is already false (not every integer is even), so the conditional $\forall x\,P(x)\to\forall x\,Q(x)$ is vacuously TRUE. The left side is false and the right side is true for the same predicates, so: $$\boxed{\forall x(P(x)\to Q(x)) \ \not\equiv\ \forall x\,P(x)\to\forall x\,Q(x)}$$ In general $\forall x(P(x)\to Q(x))\Rightarrow(\forall xP(x)\to\forall xQ(x))$ is a valid one-way implication, but the converse fails, as this counterexample shows.