\documentclass[10pt,letter]{exam}
\usepackage{color}
\usepackage{hyperref}
\begin{document}

\begin{coverpages}
\begin{center}\huge MATH 2200 - EXAM 1 SPRING 2017\\
SOLUTION
\end{center}

\begin{flushleft}\vspace{0.5in}
Thursday 9 February 2017 \\
Instructor: Tom Cuchta
\end{flushleft}

\textbf{Instructions:}
\begin{itemize}
	\item  Show all work, clearly and in order, if you want to get full
	credit. If you claim something is true \textbf{you must show work backing up your claim}. I reserve the right to take off points if I cannot see how you arrived at your answer (even if your final answer is correct).
	\item Justify your answers whenever possible to ensure full credit. 	
	\item  Circle or otherwise indicate your final answers.
	\item  Please keep your written answers brief; be clear and to the point.
	\item  Good luck!
\end{itemize}
\vspace*{10pt}

\noindent\underline{Tautological implications and equivalences} \\
\textbf{Commutative Law of $\vee$}: $P \vee Q \leftrightarrow Q \vee P$ \\
\textbf{Law of Equivalence for Implication and Disjunction}: $(\neg P \vee Q) \leftrightarrow (P \rightarrow Q)$ \\
\textbf{Law of Contraposition}: $(P \rightarrow Q) \leftrightarrow (\neg Q \rightarrow \neg P)$ \\
\textbf{Modus tollendo ponens}: $[(\neg P) \wedge (P \vee Q)] \rightarrow Q$ \\
\textbf{Modus tollendo tollens}: $[(\neg Q) \wedge (P \rightarrow Q)] \rightarrow \neg P$\\
\textbf{Law of Detachment}: $[P \wedge (P \rightarrow Q)] \rightarrow Q$ \\


\end{coverpages}

\begin{questions}
\question[9] Translate the following sentences into symbolic notation, with letters standing only for atomic sentences. Be sure to identify which sentences correspond to which letters you use. \\
\textbf{This problem resembles \texttt{\#}3(h) in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/hw1.php}{HW1}}.}
\begin{parts}
\part[3] ``The sum is positive or the sum is zero." \\
\textit{Solution:} Let $P$ be the sentence ``The sum is positive." and let $Q$ be the sentence ``The sum is zero". The given sentence, written symbolically, is $P \vee Q$.
\part[3] ``If $f$ is midpoint-convex and $f$ is continuous, then $f$ is convex." \\
\textit{Solution:} Let $P$ be the sentence ``$f$ is midpoint-convex." and let $Q$ be the sentence ``$f$ is convex". Then the given sentence, written symbolically, is $P \rightarrow Q$. 
\part[3] ``The graph $G$ is a tree if and only if $G$ is connected and $G$ does not contain a cycle." \\
\textit{Solution:} Let $P$ be the sentence ``The graph $G$ is a tree.", let $Q$ be the sentence ``$G$ does not contain a cycle.", and let $R$ be the sentence ``$G$ contains a cycle". The given sentence, written symbolically, is $P \leftrightarrow (Q \wedge \neg R)$. \\
(\textit{note: if you chose $R$ to instead be ``$G$ does not contain a cycle", then you would have gotten $P \leftrightarrow (Q \wedge R)$}, which is ok)
\end{parts}
\question[16] If $P$ and $Q$ are  true and $R$ is false, then are the following sentences true or false? \\
\textbf{This problem resembles \texttt{\#}4(a), \texttt{\#}5(d), \texttt{\#}6(e), and \texttt{\#}6(i) in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/hw1.php}{HW1}}.}
\begin{parts}
\part[4] $P \vee R$ \\
\textit{Solution:} True (because $P$ is true)
\part[4] $\neg (\neg R)$ \\
\textit{Solution:} False (because $\neg R$ is true, which is the case because $R$ is false)
\part[4] $R \rightarrow \neg P$ \\
\textit{Solution:} True (because ``$\mathrm{False} \rightarrow \mathrm{anything}$" is always true)
\part[4] $R \leftrightarrow [P \rightarrow (Q \wedge R)]$ \\
\textit{Solution:} True ($Q \wedge R$ is false, meaning $P \rightarrow (Q \wedge R)$ is false since $P$ is true. This means both $R$ and $P \rightarrow (Q \wedge R)$ are both false, making the biconditional true, since they match.)
\end{parts}

\question[12] Use a truth table to determine whether the given sentence is a tautology or not. \\
\textbf{This problem resembles \texttt{\#}10(c) and \texttt{\#}10(i) in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/hw2.php}{HW2}}.}
\begin{parts}
\part[6] $[P \wedge (\neg Q) ] \vee Q$ \\
\textit{Solution:} 
$$\begin{array}{|l|l|l|l|l|}
\hline
P & Q & \neg Q & P \wedge (\neg Q) & [P \wedge (\neg Q)] \vee Q \\
\hline
T & T & F & F & T\\
T & F & T & T & T\\
F & T & F & F & T\\
F & F & T & F & F \\ 
\hline
\end{array}$$
From the final column, we see that this is \textbf{not} a tautology.
\part[6] $[\neg P \wedge (P \vee Q)] \rightarrow Q$ \\
\textit{Solution:} 
$$\begin{array}{|l|l|l|l|l|l|}
\hline
P & Q & \neg P & P \vee Q & [\neg P \wedge (P \vee Q)] & [\neg P \wedge (P \vee Q)] \rightarrow Q \\
\hline
T & T & F & T & F & T\\
T & F & F & T & F & T\\
F & T & T & T & T & T\\
F & F & T & F & F & T\\
\hline
\end{array}$$
From the final column, we that this \textbf{is} a tautology.
\end{parts}
\newpage
\question[12] 
\textbf{This problem resembles \texttt{\#}16(c) in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/hw2.php}{HW2}}.}
\begin{parts} 
\part[6] Does the sentence $P \wedge (P \rightarrow Q)$ tautologically imply the sentence $Q$? If so, prove it using a truth table. If not, explain why not. \\
\textit{Solution:} Yes it does. To see it, we must show that $[P \wedge (P \rightarrow Q)]\rightarrow Q$ is a tautology.
$$\begin{array}{|l|l|l|l|l|l|}
\hline
P & Q & P \rightarrow Q & P \wedge (P \rightarrow Q) & [(P \rightarrow Q)] \rightarrow Q \\
\hline
T & T & T & T & T\\
T & F & F & F & T\\
F & T & T & F & T\\
F & F & T & F & T\\
\hline
\end{array}$$
\part[6] Does the sentence $\neg P \wedge (P \rightarrow Q)$ tautologically imply the sentence $P$? If so, prove it using a truth table. If not, explain why not.\\
\textit{Solution:} It does not. We show it via truth table: \\
$$\begin{array}{|l|l|l|l|l|l|}
\hline
P & Q & \neg P & P \rightarrow Q & \neg P \wedge (P \rightarrow Q) & [\neg P \wedge (P \rightarrow Q)] \rightarrow P \\
\hline
T & T & F & T & F & T\\
T & F & F & F & F & T\\
F & T & T & T & T & F\\
F & F & T & T & T & F\\
\hline
\end{array}$$
Since the last table shows that the implication $[\neg P \wedge (P \rightarrow Q)] \rightarrow P$ is \textbf{not} a tautology, we say that $\neg P \wedge (P \rightarrow Q)$ does \textbf{not} tautologically imply $P$. 
\end{parts}

\question[14] 
\textbf{This problem resembles \texttt{\#}17(b) and \texttt{\#}17(d) in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/hw2.php}{HW2}}.}
\begin{parts}
\part[7]Is the sentence $Q \vee \neg P$ tautologically equivalent to $Q \vee P$? If so, prove it using a truth table. If not, explain why not.\\
\textit{Solution:} It is not. We demonstrate via truth table:
$$\begin{array}{|l|l|l|l|l|l|l|l|}
\hline
P & Q & \neg P & Q \vee \neg P & Q \vee P & (Q \vee \neg P) \rightarrow (Q \vee P) & (Q \vee P) \rightarrow (Q \vee \neg P) \\
\hline
T & T & F & T & T & T & T \\
T & F & F & F & T & T & F \\
F & T & T & T & T & T & T \\
F & F & T & T & F & F & T \\
\hline
\end{array}$$
Since the last two columns do not exactly match, we see that they are not tautologically equivalent. \\
\textit{note: we could have also made another column for $(Q \vee P) \leftrightarrow (Q \vee \neg P)$ which would show that that sentence is not a tautology --- this also shows the two sentences are not tautologically equivalent.}
\part[7] Is the sentence $P$ tautologically equivalent to the sentence $\neg(\neg P)$? If so, prove it using a truth table. If not, explain why not.
\end{parts}

\question[9] Make a counterexample to show the following rule of inference is invalid: ``from $\neg Q$ and $P \rightarrow \neg Q$, we may conclude $P$." \\
\textbf{This problem resembles \texttt{\#}1 in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/MATH-2200-HW3(solution)-Spring-2017-FairmontState.pdf}{HW3}}.}\\
\textit{Solution:} We must pick truth values for $P$ and $Q$ that make the premises true and the conclusion false. So we let $Q$ be false (so that the premise $\neg Q$ is true) and we will let $P$ be false (so that the conclusion will be false). Note that doing this makes the other premise $P \rightarrow \neg Q$ to also be false. 

This means we have found a counterexample because our premises $\neg Q$ and $P \rightarrow \neg Q$ are true while simultaneously the conclusion $P$ is false (based on how we chose the truth values for $P$ and $Q$).
\newpage
\question[12] There \textbf{three} errors in the following formal deduction. Find them and explain why they are errors: \\
\textbf{This problem resembles \texttt{\#}2 in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/MATH-2200-HW3(solution)-Spring-2017-FairmontState.pdf}{HW3}}.}\\
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $P$ & Premise \\
$\{2\}$ & (2) $P \rightarrow \neg Q$ & Premise \\
$\{3\}$ & (3) $R \rightarrow Q$ & Premise \\
$\{3\}$ & (4) $\neg Q \rightarrow \neg R$ & 3 T (Law of Contraposition) \\
$\{1,2\}$ & (5) $\neg Q$ & 1,2 T (Modus tollendo ponens) \\
$\{1,2,3,4,5\}$ & (7) $\neg R$ & 4, 5 T (Law of Detachment)  \\
\hline
\end{tabular}\\
\textit{Solution:} \\
\textbf{First error}: Line $(5)$ claims that it follows from lines $1$ and $2$ using modus tollendo ponens. This is not true, it actually follows from the Law of Detachment. \\
\textbf{Second error:} The left columns of the last line of the deduction claims that this line depends on the premises $\{1,2,3,4,5\}$, but lines $4$ and $5$ are not premises, and so they should not be listed here. \\
\textbf{Third error:} The last line of the deduction is called $(7)$, but it should be $(6)$. \\
\question[16] Construct a formal deduction for the following arguments. Do so by applying the stated rule(s). \\
\textbf{This problem resembles \texttt{\#}4 and \texttt{\#}5 in {\color{blue}\href{http://tomcuchta.com/teach/classes/2017/MATH-2200-Spring-2017-FairmontState/homework/MATH-2200-HW3(solution)-Spring-2017-FairmontState.pdf}{HW3}}.}\\
\begin{parts}
\part[8] ``If $n$ is odd, then $i^n$ is complex. In actuality, $i^n$ is not complex. Therefore $n$ is not odd." \\
\textbf{Rules:} Use \textbf{Modus tollendo tollens}. \\
\textit{Solution:} Let $P$ be the sentence ``$n$ is odd", let $Q$ be the sentence ``$i^n$ is complex". We may write a formal deduction for this argument as follows: \\
\begin{tabular}{|lll|}
\hline
$\{1\}$ & (1) $P \rightarrow Q$ & Premise \\
$\{2\}$ & (2) $\neg Q$ & Premise \\
$\{1,2\}$ & (3) $\neg P$ & 1, 2 T Modus tollendo tollens \\
\hline
\end{tabular}
\part[8] ``If the axiom of choice holds, then nonmeasurable sets exist. If nonmeasurable sets exist, then the Banach-Tarski paradox is true. I will quit mathematics or the Banach-Tarski paradox is not true. The axiom of choice holds. Therefore I will quit mathematics."\\
\textbf{Rules:} Use the \textbf{Law of Detachment} to conclude ``the Banach-Tarski paradox is true" and then use \textbf{Commutative Law of $\vee$} to conclude ``the Banach-Tarski paradox is not true or I will quit mathematics." From here, use one more law (which?) to conclude ``If the Banach-Tarski paradox is true, then I will quit mathematics." After that, complete the deduction using the \textbf{Law of Detachment}. \\
\textit{Solution:} Let 
\begin{center}$P = $ ``The axiom of choice holds." \\
$Q = $ ``Nonmeasurable sets exist." \\
$R = $ ``The Banach-Tarski paradox is true." \\
$S = $ ``I will quit mathematics."
\end{center} Construct the formal deduction as follows: \\
\begin{tabular}{|l|l|l|}
\hline
$\{1\}$ & (1) $P\rightarrow Q$ & Premise \\
$\{2\}$ & (2) $Q \rightarrow R$ & Premise \\
$\{3\}$ & (3) $S \vee (\neg R)$ & Premise \\
$\{4\}$ & (4) $P$ & Premise \\
$\{1,4\}$ & (5) $Q$ & 1,4 T (Law of Detachment) \\
$\{1,2,4\}$ & (6) $R$ & 2,5 T (Law of Detachment) \\
$\{1,2,3,4\}$ & (7) $(\neg R) \vee S$ & 3 T (Commutative Law of $\vee$) \\
$\{1,2,3,4\}$ & (8) $R \rightarrow S$ & 7 T (Law of Equivalence for Implication and Disjunction) \\
$\{1,2,3,4\}$ & (9) $S$ & 6, 8 T (Law of Detachment) \\
\hline
\end{tabular}
\end{parts}
\end{questions}

\end{document}