Midterm Exam
Discrete Mathematics · 6 problems · solutions hidden, click to reveal
Flashcards
Problems
(a) Construct a truth table for \((p \to q) \land (r \to \neg q)\).
(b) Is it equivalent to \(\neg(p \land r)\)? Justify.
(b) Is it equivalent to \(\neg(p \land r)\)? Justify.
Show solution
Answer: Not equivalent.
They differ at \(p=F, q=T, r=T\): there \((p\to q)\land(r\to\neg q) = T \land F = F\), but \(\neg(p\land r) = \neg(F\land T) = \neg F = T\). Since they disagree on one row, they are not equivalent.
Three logicians are asked "Does everyone want a beer?" A says "I don't know," then B says "I don't know," then C says "No, not everyone wants a beer." Determine who wants a beer.
Show solution
Answer: A and B want a beer; C does not.
If A didn't want a beer, A could answer "no" - but A said "I don't know," so A wants a beer. Same reasoning gives B wants a beer. C still answers "no" after hearing A and B, so C must not want a beer. Thus A and B want a beer, C does not.
Let \(P \equiv \forall x\,\exists y\,(x = y^2)\).
(a) Negate \(P\) with no negation symbols.
(b) Give an infinite domain making \(P\) true (justify).
(c) Give an infinite domain making \(P\) false (justify).
(a) Negate \(P\) with no negation symbols.
(b) Give an infinite domain making \(P\) true (justify).
(c) Give an infinite domain making \(P\) false (justify).
Show solution
(a) \(\neg P \equiv \exists x\,\forall y\,(x \neq y^2)\).
(b) Positive reals: for any \(x>0\), let \(y=\sqrt{x}\) (also a positive real); then \(x=y^2\). So \(P\) is true.
(c) Naturals: \(x=2\) has no natural \(y\) with \(y^2=2\) (only \(\pm\sqrt2\)), so \(P\) is false.
(b) Positive reals: for any \(x>0\), let \(y=\sqrt{x}\) (also a positive real); then \(x=y^2\). So \(P\) is true.
(c) Naturals: \(x=2\) has no natural \(y\) with \(y^2=2\) (only \(\pm\sqrt2\)), so \(P\) is false.
Let \(F(x,y)\) mean "\(x\) can fool \(y\)." Express:
(a) Everyone can fool Turbo. (b) Everybody can fool somebody. (c) Everyone can be fooled by somebody. (d) There is exactly one person whom everybody can fool.
(a) Everyone can fool Turbo. (b) Everybody can fool somebody. (c) Everyone can be fooled by somebody. (d) There is exactly one person whom everybody can fool.
Show solution
(a) \(\forall x\,F(x,\text{Turbo})\).
(b) \(\forall x\,\exists y\,F(x,y)\).
(c) \(\forall x\,\exists y\,F(y,x)\).
(d) \(\exists x\big(\forall y\,F(y,x) \land \forall z\,(\forall y\,F(y,z) \to z = x)\big)\).
(b) \(\forall x\,\exists y\,F(x,y)\).
(c) \(\forall x\,\exists y\,F(y,x)\).
(d) \(\exists x\big(\forall y\,F(y,x) \land \forall z\,(\forall y\,F(y,z) \to z = x)\big)\).
(a) Define what it means for an integer \(n\) to be even.
(b) Prove that if \(n\) is even, there is an integer \(a\) with \(n = (a-2) + (a+4)\).
(c) Prove that \(a\) is unique (state first what uniqueness means).
(b) Prove that if \(n\) is even, there is an integer \(a\) with \(n = (a-2) + (a+4)\).
(c) Prove that \(a\) is unique (state first what uniqueness means).
Show solution
(a) \(n\) is even if \(n = 2m\) for some integer \(m\).
(b) If \(n = 2m\), let \(a = m - 1\). Then \((a-2)+(a+4) = 2a + 2 = 2(m-1) + 2 = 2m = n\).
(c) Uniqueness: for all \(a, b\), if \(n=(a-2)+(a+4)\) and \(n=(b-2)+(b+4)\) then \(a=b\). Indeed \((a-2)+(a+4) = (b-2)+(b+4) \Rightarrow 2a+2 = 2b+2 \Rightarrow a = b\).
(b) If \(n = 2m\), let \(a = m - 1\). Then \((a-2)+(a+4) = 2a + 2 = 2(m-1) + 2 = 2m = n\).
(c) Uniqueness: for all \(a, b\), if \(n=(a-2)+(a+4)\) and \(n=(b-2)+(b+4)\) then \(a=b\). Indeed \((a-2)+(a+4) = (b-2)+(b+4) \Rightarrow 2a+2 = 2b+2 \Rightarrow a = b\).
Prove that \(3 \mid n^3 + 2n\) for every natural number \(n\).
Show solution
Let \(P(n): 3 \mid n^3 + 2n\). Base: \(1^3 + 2(1) = 3\), divisible by 3. Step: assume \(k^3 + 2k = 3m\). Then
\((k+1)^3 + 2(k+1) = (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1) = 3(m + k^2 + k + 1),\)
divisible by 3. By induction, \(3 \mid n^3 + 2n\) for all natural \(n\).
\((k+1)^3 + 2(k+1) = (k^3 + 2k) + 3k^2 + 3k + 3 = 3m + 3(k^2 + k + 1) = 3(m + k^2 + k + 1),\)
divisible by 3. By induction, \(3 \mid n^3 + 2n\) for all natural \(n\).