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 conditional $\neg(\neg p\lor q)\to p$ over Boolean variables $p,q$. (b) A conditional whose antecedent is the algebraic statement $x=x+5$. (c) The universally-quantified statement $\forall x\ x^2\ge 2x-1$. (d) The logical form $(p\lor\neg q)\land(\neg p\lor\neg q)$.

Find. (a) A proof the form is a tautology. (b) The truth value, with justification. (c) The negation of the statement, simplified. (d) The simplest equivalent proposition.

Approach. (a) build the 4-row truth table (or push $\neg(\neg p\lor q)$ through De Morgan first); (b) test whether the antecedent can ever be true; (c) push $\neg$ through the quantifier and flip the inequality; (d) distribute $\land$ over $\lor$ to isolate the common literal.

1. (a) Prove $\neg(\neg p\lor q)\to p$ is a tautology. By De Morgan, $\neg(\neg p\lor q)\equiv p\land\neg q$. The proposition becomes $(p\land\neg q)\to p$. A conditional whose antecedent is a conjunction that already contains the consequent as a conjunct is always true, since the antecedent $p\land\neg q$ can only be true when $p$ itself is true — so whenever the antecedent is true, the consequent $p$ is automatically true too: $$\neg(\neg p\lor q)\to p\ \equiv\ (p\land\neg q)\to p\ \equiv\ \neg(p\land\neg q)\lor p\ \equiv\ (\neg p\lor q)\lor p\ \equiv\ T$$ (the last step holds because $\neg p\lor p\equiv T$, and a disjunction containing $T$ is $T$). All four rows of $p,q$ give True. $\boxed{\neg(\neg p\lor q)\to p\text{ is a tautology}}$
2. (b) Truth value of "If $x=x+5$ then $2x=2x-3$". The antecedent $x=x+5$ simplifies to $0=5$ by subtracting $x$ from both sides — a statement that is false for every real $x$ (no solution exists). A conditional with a false antecedent is TRUE regardless of the consequent (vacuous truth); it does not matter that $2x=2x-3$ (which simplifies to $0=-3$) is also always false. $\boxed{\text{TRUE (vacuously, since }x=x+5\text{ has no solution)}}$
3. (c) Negation of $\forall x\ x^2\ge 2x-1$. Push the negation through the universal quantifier (turning it existential) and negate the inequality ($\ge$ negates to $\lt$, not $\le$): $$\neg\big(\forall x\ x^2\ge 2x-1\big)\ \equiv\ \exists x\ \neg(x^2\ge 2x-1)\ \equiv\ \exists x\ (x^2\lt 2x-1)$$ $\boxed{\exists x\,(x^2\lt 2x-1)}$ — note this negation is itself false, since $x^2-(2x-1)=(x-1)^2\ge 0$ always, confirming the original universal statement was true.
4. (d) Simplify $(p\lor\neg q)\land(\neg p\lor\neg q)$. Factor out the common literal $\neg q$ using the distributive law $(\ldots\lor\neg q)\land(\ldots\lor\neg q)\equiv(\ldots\land\ldots)\lor\neg q$: $$(p\lor\neg q)\land(\neg p\lor\neg q)\ \equiv\ (p\land\neg p)\lor\neg q\ \equiv\ F\lor\neg q\ \equiv\ \neg q$$ $\boxed{\neg q}$