Question 1 of 12: Logic — Propositions, Compound Propositions and Quantifiers
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Examination, 04-BS-16 Discrete Mathematics, May 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, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.
Approach. Part (a) is a direct translation exercise ("sufficient" and "only if" both encode a one-directional implication); part (b) is settled by exhaustive truth-table evaluation over the two possible truth values of $p$; part (c) requires evaluating each quantified statement over $\mathbb{R}$ and pushing the negation inward with $\lnot\forall x\,\phi \equiv \exists x\,\lnot\phi$ and $\lnot\exists x\,\phi\equiv\forall x\,\lnot\phi$.
(a) Translate "sufficient" and "only if." "$X$ is sufficient for $Y$" means $X$ alone guarantees $Y$, i.e. $\boxed{\text{If } X \text{ then } Y}$ ($X\rightarrow Y$). "$Y$ only if $X$" means $Y$ can be true only when $X$ is true, i.e. $\boxed{\text{If } Y \text{ then } X}$ ($Y\rightarrow X$).
(b) Build the truth table for $((q\wedge p)\rightarrow p)\wedge(p\rightarrow(q\wedge p))$ with $q=T$ fixed.
$p$
$q$
$q\wedge p$
$(q\wedge p)\rightarrow p$
$p\rightarrow(q\wedge p)$
Conjunction
T
T
T
T
T
T
F
T
F
T
T
T
Column 4 is always true because a conjunction always implies either of its conjuncts ($(q\wedge p)\rightarrow p$ is a tautology). Column 5 is true when $p=T$ (then $q\wedge p=q=T$, so $T\rightarrow T$) and vacuously true when $p=F$. Both conjuncts are true in every row, so the whole expression is $\boxed{\textbf{always true}}$ — it is a tautology given $q$ true, regardless of $p$'s status.
(c) Evaluate $\forall x\,\forall y\,P(x,y)$. This reads "every real $x$ is $\le$ every real $y$," which is false (e.g. $x=1,y=0$ gives $1\le 0$, false). Status: $\boxed{\textbf{False}}$.
Negation: $\lnot\forall x\,\forall y\,(x\le y) \equiv \exists x\,\lnot\forall y\,(x\le y)\equiv \exists x\,\exists y\,\lnot(x\le y)\equiv \boxed{\exists x\,\exists y\,(x>y)}$ — no negation symbol remains.
Evaluate $\exists x\,\exists y\,P(x,y)$. This reads "some real $x$ is $\le$ some real $y$," which is true (e.g. $x=0,y=1$). Status: $\boxed{\textbf{True}}$.
Negation: $\lnot\exists x\,\exists y\,(x\le y)\equiv\forall x\,\lnot\exists y\,(x\le y)\equiv\forall x\,\forall y\,\lnot(x\le y)\equiv \boxed{\forall x\,\forall y\,(x>y)}$.
