\Question{Propositional Logic Language}
For each of the following sentences, use the notation introduced in class to convert the sentence into propositional logic. Then write the statement's negation in propositional logic.
\begin{Parts}
\Part (5 Points) The cube of a negative integer is negative.
\nosolspace{1cm}
\Part (5 Points) There are no integer solutions to the equation $x^2 - y^2 = 10.$
\nosolspace{1cm}
\Part (5 Points) There is one and only one real solution to the equation $x^3 + x + 1 = 0$.
\nosolspace{1cm}
\Part (5 Points) For any two distinct real numbers, we can find a rational number in between them.
\nosolspace{1cm}
\end{Parts}
\Question{Miscellaneous Logic}
\begin{Parts}
\Part
Let the statement, $(\forall x \in \mathbb{R})(\exists y \in \mathbb{R}) \ G(x,y)$, be
true for predicate $G(x,y)$.
For each of the following statements, decide if the statement is certainly true, certainly false, or possibly true, and justify your solution. (If possibly true, provide a specific example where the statement is false and a specific example where the statement is true.)
\begin{enumerate}[(i)]
\item (2 Points)
$G(3,4)$
\item (2 Points)
$(\forall x \in \mathbb{R})$ $G(x,3)$
\item (2 Points)
$\exists y$ $G(3,y)$
\item (2 Points)
$\forall y$ $\neg G(3,y)$
\item (2 Points)
$\exists x$ $G(x,4)$
\end{enumerate}
% \Part True or False? \\
% $\forall x \exists y (P(x,y) \land \neg Q(x,y)) \equiv \neg \exists x \forall y (P(x,y) \implies Q(x,y))$
% \Part True or False? \\
% $\exists x ((\forall y P(x,y)) \land (\forall z Q(x,z))) \equiv (\exists x \forall y P(x,y)) \land (\exists x \forall z Q(x,z))$
\Part (5 Point)
Give an expression using terms involving $\lor,\land$ and $\neg$ which is true if and only if
exactly one of $X,Y$, and $Z$ is true.
% (Just to remind you: $(X \land Y \land Z)$ means
% all three of $X$,$Y$,$Z$ are true, $(X \lor Y \lor Z)$ means at least one of $X$,$Y$
% and $Z$ is true.)
\end{Parts}
\Question{Logical Equivalence?}
Decide whether each of the following is true or false and justify your answer:
\begin{Parts}
\Part (5 Points) $\forall x \; \bigl( P(x) \wedge Q(x) \bigr)~\equiv~\forall x \; P(x) \wedge \forall x \; Q(x)$
\nosolspace{3cm}
\Part (5 Points) $\forall x \; \bigl( P(x) \vee Q(x) \bigr)~\equiv~\forall x \; P(x) \vee \forall x \; Q(x)$
\nosolspace{3cm}
\Part (5 Points) $\exists x \; \bigl( P(x) \vee Q(x) \bigr)~\equiv~\exists x \; P(x) \vee \exists x \; Q(x)$
\nosolspace{3cm}
\Part (5 Points) $\exists x \; \bigl( P(x) \wedge Q(x) \bigr)~\equiv~\exists x \; P(x) \wedge \exists x \; Q(x)$
\end{Parts}
\nosolspace{4cm}
\Question{Fermat's Contradiction}
(5 Points) Prove that $2^{1/n}$ is not rational for any integer $n\geq3$. (\textit{Hint}: Use Fermat's Last Theorem. It states that there exists no positive integers $a,b,c$ s.t. $a^n + b^n = c^n$ for $n \geq 3$.)
\nosolspace{1in}
\Question{Prove or Disprove}
Prove or disprove each of the following statements. For each proof, state which of the proof types (as discussed in Note~2) you used.
\begin{Parts}
\Part (4 Points)
For all natural numbers $n$, if $n$ is odd then $n^2+3n$ is even.
\Part (4 Points)
For all real numbers $a,b$, if $a+b \ge 20$ then $a\ge 17$ or $b\ge 3$.
\Part (4 Points)
For all real numbers $r$, if $r$ is irrational then $r+1$ is irrational.
\Part (4 Points)
For all natural numbers $n$, $10n^3>n!$.
\Part (4 Points)
For all natural numbers $a$ where $a^5$ is odd, then
$a$ is odd.
\end{Parts}
\Question{Divisibility Induction}
Prove the following statements using induction.
\begin{Parts}
\Part (5 Points) For all $n \in \mathbb{N}$ with $n \geq 1$, the number $n^3-n$ is divisible by 3.
\Part (5 Points) For all $n \in \mathbb{N}$ with $n \geq 1$, the number $5^n - 4n - 1$ is divisible by 16.
% \item (5 Points) Prove by induction that, for all natural numbers $n\geq1$, the number $k^9-2k^4+k^2$ is divisible by 9.
\Part (5 Points) You need to send in an envelope with $n$ cents of postage on it. However, you only have 3 cent and 7 cent postage stamps. You do not want to go over $n$ cents of postage. Prove that you can make exactly $n$ cents of postage with 3 cent and 7 cent stamps as long as $n \geq 12$.
\end{Parts}
\Question{A Coin Game}
(10 Points) Your "friend" Stanley Ford suggests you play the following game with him. You each start with a single stack of $n$ coins. On each of your turns, you select one of your stacks of coins (that has at least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into a stack of 3 coins and a stack of 2 coins, your score would be $3 \cdot 2 = 6$). You continue taking turns until all your stacks have only one coin in them. Stan then plays the same game with his stack of $n$ coins, and whoever ends up with the largest total score over all their turns wins.
Prove that no matter how you choose to split the stacks, your total score will always be $\frac{n(n - 1)}{2}$. (This means that you and Stan will end up with the same score no matter what happens, so the game is rather pointless.)
\Question{Leaves in a Tree}
A {\em leaf} in a tree is a vertex with degree $1$.
\begin{Parts}
\Part
(10 Points) Consider a tree with $n \ge 3$ vertices. What is the largest possible number of leaves the tree could have? Prove that this maximum $m$ is possible to achieve, and further that there cannot exist a tree with more than $m$ leaves.
\nosolspace{0.5in}
\Part
(10 Points) Prove that every tree on $n \ge 2$ vertices must have at least two leaves.
\nosolspace{0.5in}
%\Part
%Let $k$ be the maximum degree of a tree (The maximum degree of a graph is defined as the largest degree of any vertex in that graph). Prove that the tree contains at least $k$ leaves.
%\nosolspace{0.5in}
\end{Parts}