Question 2 of 12

Question 2 (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 $\neg p\to(p\land\neg q)$ over $p,q$. (b) The statement $\forall x\ x^2\ge 2x-1$, universe $=\mathbb{R}$. (c) Two candidate predicate-logic sentences built from 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) complete the square on $x^2-2x+1$; (c) test the claimed equivalence with a concrete predicate pair over a small domain.

1. (a) Truth table for $\neg p\to(p\land\neg q)$. Evaluate $\neg p$, then $p\land\neg q$, then the conditional, row by row: $$\begin{array}{cc|c|c|c}p&q&\neg p&p\land\neg q&\neg p\to(p\land\neg q)\\\hline T&T&F&F&T\\T&F&F&T&T\\F&T&T&F&F\\F&F&T&F&F\end{array}$$ Whenever $\neg p$ is false ($p=T$) the conditional is vacuously true regardless of $q$; whenever $p=F$, the consequent $p\land\neg q$ is forced false, so the conditional is false. $\boxed{\text{True exactly when }p=T\text{ (both rows of }q\text{); False when }p=F}$
2. (b) Truth value of $\forall x\ x^2\ge 2x-1$ over $\mathbb{R}$. Rearrange: $x^2-2x+1=(x-1)^2\ge 0$ for every real $x$ (a square is never negative), with equality only at $x=1$. So $x^2\ge 2x-1$ holds for every real $x$: $$x^2-(2x-1) = (x-1)^2 \ge 0 \ \ \forall x\in\mathbb{R}$$ $\boxed{\text{TRUE}}$
3. (c) Are $\forall x(P(x)\to Q(x))$ and $\forall x\,P(x)\to\forall x\,Q(x)$ equivalent? Take 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, since $x=2$ is even ($P(2)$ true) but not odd ($Q(2)$ false), so the conditional fails at $x=2$. Meanwhile $\forall x\,P(x)$ is already false (not every integer is even), which makes $\forall x\,P(x)\to\forall x\,Q(x)$ vacuously TRUE. The two sides disagree for the same predicates: $$\boxed{\forall x(P(x)\to Q(x))\ \not\equiv\ \forall x\,P(x)\to\forall x\,Q(x)}$$ (The one-way implication $\forall x(P(x)\to Q(x))\Rightarrow(\forall xP(x)\to\forall xQ(x))$ is valid; only the converse fails.)