\documentclass[10pt,addpoints]{exam}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{pgfplots}
\usepackage{tikz}
\usepackage{mathtools}
\pagestyle{head}
\usepackage{mathrsfs}

\newcommand\bigangle[2][]{% 
    \draw[->,domain=0:#2,variable=\t,samples=200,>=latex,#1]
      plot ({0.4*(0.3*\t+#2)*cos(\t)/(#2)},
           {0.4*(0.3*\t+#2)*sin(\t)/(#2)})
        ;}
        
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

%\headrule
%\header{MATH 11}{Exam 1}{Fall 2016}
\begin{document}
\begin{coverpages}
\begin{center}\huge MATH 2510 - EXAM 1 - SPRING 2018\\
SOLUTION
\end{center}
\begin{flushleft}\vspace{0.5in}
8 February 2018 \\
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 algebraically 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}
\end{coverpages}

\begin{questions}
\question[15] Let $X=\{1, 2\}$, $Y=\{4, 6 \}$, and $Z=\{ 1, 9 \}$.
\begin{parts}
\part[3] Compute $X \times Y$. \\
\textit{Solution}: $X \times Y = \{(1,4), (1,6), (2,4), (2,6) \}$
\part[3] Compute $Z \times Y$. \\
\textit{Solution}: $Z \times Y = \{(1,4), (1,6), (9,4), (9,6) \}$
\part[3] Using your answers from above, what is $(X \times Y) \cup (Z \times Y)$?  \\
\textit{Solution}: $(X \times Y) \cup (Z \times Y) = \{(1,4), (1,6), (2,4), (2,6), (9,4), (9,6) \}$
\part[3] Using your answers from above, what is $(X \times Y) \cap (Z \times Y)$?  \\
\textit{Solution}: $(X \times Y) \cap (Z \times Y) = \{(1,4), (1,6) \}$
\part[3] Using your answer from above, is $(X \times Y)$ a function? \\
\textit{Solution}: No -- it contains the points $(1,4)$ and $(1,6)$ and therefore fails the ``vertical line test". 
\end{parts}

\question[16] Formula or not? If not, circle the problem(s). Find all errors for full credit.
\begin{parts}
\part[4] $P \leftrightarrow (P \vee Q \rightarrow \neg P)$ \\
\textit{Solution}: Formula 
\part[4] $(P$\circled{$\neg$}$\wedge Q) \rightarrow \neg ( P$\circled{$\neg$}$Q)$ \\
\textit{Solution}: Not a formula
\part[4] \circled{$\leftrightarrow$}$P \rightarrow Q$  \\
\textit{Solution}: Not a formula
\part[4] $P \leftrightarrow (P \vee Q \rightarrow \neg (\neg P))$ \\
\textit{Solution}: Formula
\end{parts}

\question[7] Find a truth table for the formula $P \leftrightarrow (P \vee \neg Q)$. \\
\textit{Solution}: Calculate \\
\begin{tabular}{|l|l|l|l|l|}
\hline
$P$ & $Q$ & $\neg Q$ & $P \vee \neg Q$ & $P \leftrightarrow (P \vee \neg Q)$ \\
\hline 
1&1&0&1&1 \\
1&0&1&1&1 \\
0&1&0&0&1 \\
0&0&1&1&0 \\
\hline
\end{tabular}

\question[7] Is $(P \rightarrow Q) \equiv (\neg P \rightarrow \neg Q)$? Check it by making an appropriate truth table. \\
\textit{Solution}: We know that to show a formula $G$ is a consequence of a formula $F$, i.e. $F \equiv G$, it is sufficient to show that $F \leftrightarrow G$ is a tautology. If it is not a tautology, then they are not equivalent. Compute \\
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
$P$&$Q$&$P \rightarrow Q$&$\neg P$&$\neg Q$&$\neg P \rightarrow \neg Q$&$(P \rightarrow Q) \leftrightarrow (\neg P \rightarrow \neg Q)$ \\
\hline
1&1&1&0&0&1&1 \\
1&0&0&0&1&1&0 \\
0&1&1&1&0&0&0 \\
0&0&1&1&1&1&1 \\
\hline
\end{tabular}\\
From this, we see that $(P \rightarrow Q) \not\equiv (\neg P \rightarrow \neg Q)$.
\vfill

\newpage 
\question[12] Satisfiable or unsatisfiable?
\begin{parts}
\part[6] $P \rightarrow (Q \rightarrow \neg P)$ \\
\textit{Solution}: To check if it is satisfiable or not, it is sufficient to construct a truth table for the formula and observe if there is a ``$1$" in its column. Compute \\
\begin{tabular}{|l|l|l|l|l|}
\hline
$P$ & $Q$ & $\neg P$ & $Q \rightarrow \neg P$ & $P \rightarrow (Q \rightarrow \neg P)$ \\
\hline
1&1&0&0&0 \\
1&0&0&1&1 \\
0&1&1&1&1 \\
0&0&1&1&1 \\
\hline
\end{tabular} \\
From this, we see that $P \rightarrow (Q \rightarrow \neg P)$ is satisfiable.

\part[6] $(P \leftrightarrow Q) \leftrightarrow (\neg P \leftrightarrow Q)$ \\
\textit{Solution}: To check if it is satisfiable or not, it is sufficient to construct a truth table for the formula and observe if there is a ``$1$" in its column. Compute \\
\begin{tabular}{|l|l|l|l|l|l|}
\hline
$P$ & $Q$ & $\neg P$ & $P \leftrightarrow Q$ & $\neg P \leftrightarrow Q$ & $(P \leftrightarrow Q) \leftrightarrow (\neg P \leftrightarrow Q)$ \\
\hline
1&1&0&1&0&0 \\
1&0&0&0&1&0 \\
0&1&1&0&1&0 \\
0&0&1&1&0&0 \\
\hline
\end{tabular} \\
From this, we see that $(P \leftrightarrow Q) \leftrightarrow (\neg P \leftrightarrow Q)$ is unsatisfiable.
\end{parts}

\question[18]
\begin{parts}
\part[6] Consider the assignment $\mathcal{A}(P)=1$ and $\mathcal{A}(Q)=0$. Does $\mathcal{A} \vDash P \vee Q$? \\
\textit{Solution}: Yes -- this is because the ``or" of a true thing (that is, $P$) and a false thing (that is, $Q$) is true.
\part[6] Is the following correct to write?: $\vDash P \wedge \neg P$. Why or why not? \\
\textit{Solution}: No. This is because $P \wedge \neg P$ is a contradiction. To see that, compute \\
\begin{tabular}{|l|l|l|}
\hline 
$P$ & $\neg P$ & $P \wedge \neg P$ \\
\hline
1&0&0 \\
0&1&0 \\
\hline
\end{tabular}
\part[6] Use a truth table to show that $P \wedge Q \vDash P$. \\
\textit{Solution}: It is sufficient to show that $P \wedge Q \rightarrow P$ is a tautology, i.e. in a truth table, that formula consists of a column of ``$1$"s. Compute \\
\begin{tabular}{|l|l|l|l|}
\hline
$P$ & $Q$ & $P \wedge Q$ & $P \wedge Q \rightarrow P$ \\
\hline
1&1&1&1 \\
1&0&0&1 \\
0&1&0&1 \\
0&0&0&1 \\
\hline
\end{tabular} \\
From this we observe that $P \wedge Q \rightarrow P$ is a tautology, and hence $P \wedge Q \vDash P$. 
\end{parts}

\question[25]
\begin{parts}
\part[12] Let $\mathcal{F}=\{P,Q \vee \neg P\}$ and show that $\mathcal{F} \vdash Q$ by writing a formal proof. \\
\textit{Solution}: Write the proof! \\
\begin{tabular}{ll}
\underline{Statement} & \underline{Justification} \\
1. $\mathcal{F} \vdash P$ & Assumption \\
2. $\mathcal{F} \vdash Q \vee \neg P$ & Assumption \\
3. $\mathcal{F} \vdash \neg P \vee Q$ & $\vee$-symmetry on line 2 \\
4. $\mathcal{F} \vdash P \rightarrow Q$ & $\rightarrow$-definition on line 3 \\
5. $\mathcal{F} \vdash Q$ & $\rightarrow$-elimination on lines 1 and 4
\end{tabular}
\newpage 
\part[13] Let $\mathcal{F}=\{P \leftrightarrow Q, \neg \neg P \rightarrow H, Q\}$ and show that $\mathcal{F} \vdash H$ by writing a formal proof. \\
\textit{Solution}: Write the proof! \\
\begin{tabular}{ll}
\underline{Statement} & \underline{Justification} \\
1. $\mathcal{F} \vdash P \leftrightarrow Q$ & Assumption \\
2. $\mathcal{F} \vdash Q \rightarrow P$ & $\leftrightarrow$-definition on line 1 \\
3. $\mathcal{F} \vdash Q$ & Assumption \\
4. $\mathcal{F} \vdash P$ & $\rightarrow$-elimination on lines 2 and 3 \\
5. $\mathcal{F} \vdash \neg \neg P$ & Double negation on line 4 \\
6. $\mathcal{F} \vdash \neg \neg P \rightarrow H$ & Assumption \\ 
7. $\mathcal{F} \vdash H$ & $\rightarrow$-elimination on lines 5 and 6
\end{tabular}

\vfill \vfill \vfill
\end{parts}

\end{questions}

\newpage

\includegraphics[scale=0.7]{derivations.png}

\end{document}