\documentclass{exam}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tikz}
\usetikzlibrary{arrows}
\usepackage{pgfplots}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{tabularx,ragged2e}
\usepackage{hyperref}
\usepackage{color}
\usepackage{enumerate}
\usepackage{tabularx,ragged2e}
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{
            \node[shape=circle,draw,inner sep=2pt] (char) {#1};}}

\newcommand{\dd}{\mathrm{d}}
\renewcommand*{\arraystretch}{2}
\cfoot{}
\begin{document}

\begin{coverpages}
\begin{center}{\huge MATH 2510 - EXAM 1 FALL 2019 \\
\vspace*{0.4in}
%\large Name: \makebox[3in]{\hrulefill}\\
SOLUTION
}
\end{center}

\begin{flushleft}\vspace{0.5in}
Thursday, 14 February 2019 \\
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}
\end{coverpages}

\begin{questions}
\question[19] Consider the sets $X=\{1,4,b\}$ and $Y=\{b,c,5\}$. 
\begin{parts}
\part[4] List the elements in $\{1,4,b\} \cap \{b,c,5\}$. \\
\textit{Solution}: $\{1,4,b\} \cap \{b,c,5\}=\{b\}$
\part[5] List the elements in $\{a,b\} \times \{c,d\}$. \\
\textit{Solution}: $\{a,b\} \times \{c,d\}=\{(a,c),(a,d),(b,c),(b,d)\}$
\part[5] Consider the relation $R=\{(1,b), (4,c), (b,b)\}$. Is the relation $R$ a function? \\
\textit{Solution}: Yes, no first coordinate is repeated.
\part[5] Consider the relation $S=\{(1,b), (1,c), (1,5)\}$. Is the relation $S$ a function?  \\
\textit{Solution}: No, the first coordinate ``$1$" is repeated twice.
\end{parts}

\question[21] Is the statement a tautology, a contradiction, or neither? Use a truth table to justify your conclusion.
\begin{parts}
\part[7] $P \wedge \neg(P \vee \neg P)$ \\
\textit{Solution}: \\
\[ \begin{array}{l|l|l|l|l|l|l|l}
P & \neg P & P \vee \neg P & \neg (P \vee \neg P) & P \wedge \neg (P \vee \neg P) \\
\hline 
T & F & T & F & F \\
F & T & T & F & F
\end{array} \]
Since the last column is all F's, the statement is a contradiction.
\part[7] $P \rightarrow (P \wedge P)$ \\
\textit{Solution}: \\
\[ \begin{array}{l|l|l|l|l|l|l|l}
P & P \wedge P & P \rightarrow (P \wedge P) \\
\hline
T & T & T \\
F & F & T
\end{array} \] 
Since the last column is all T's, the statement is a tautology.
\part[7] $(P \rightarrow P) \wedge P$ \\
\textit{Solution}: \\
\[ \begin{array}{l|l|l|l|l|l|l|l|l|l}
P & P \rightarrow P & (P \rightarrow P) \wedge P \\
\hline 
T & T & T \\
F & T & F
\end{array} \]
Since the last column is neither all F's nor all T's, it is neither a contradiction nor a tautology.
\end{parts}
\newpage 
\question[9] Use a truth table to show that $\neg (P \vee Q)$ is propositionally equivalent to $\neg P \wedge \neg Q$. \\
\textit{Solution}: \\
\[ \begin{array}{l|l|l|l|l|l|l|l|l|l|l|l|l}
P & Q & P \vee Q & \neg (P \vee Q) & \neg P & \neg Q & \neg P \wedge \neg Q & \neg (P \vee Q) \leftrightarrow \neg P \wedge \neg Q\\
\hline 
T & T & T & F & F & F & F & T \\ 
T & F & T & F & F & T & F & T \\
F & T & T & F & T & F &F & T \\
F & F & F & T & T & T & T & T 
\end{array} \]
Since the last column is all T's, we say that $\neg (P \vee Q)$ is propositionally equivalent to $\neg P \wedge \neg Q$. 

\question[9] Use a truth table to show that $\neg Q \rightarrow \neg P$ is a propositional consequence of $P \rightarrow Q$. \\
\textit{Solution}: \\
\[ \begin{array}{l|l|l|l|l|l|l|l|l|l|l|l}
P & Q & P \rightarrow Q & \neg P & \neg Q & \neg Q \rightarrow \neg P & (P \rightarrow Q) \rightarrow (\neg Q \rightarrow \neg P) \\
\hline
T & T & T & F & F & T & T \\
T & F & F & F & T & F & T \\
F & T & T & T & F & T & T \\
F & F & T & T & T & T & T 
\end{array}\]
Since the last column is all T's, we say that $\neg Q \rightarrow \neg P$ is a propositional consequence of $P \rightarrow Q$.

\question[18] Express the sentence using quantifiers and appropriate predicates.
\begin{parts}
\part[6] All dinosaurs are reptiles. \\
\textit{Solution}: $\forall x (Dx \rightarrow Rx)$ 
\part[6] No irrational number is a prime number. \\
\textit{Solution}: $\forall x(Ix \rightarrow \neg Px)$
\part[6] Some operators are compact. \\
\textit{Solution}: $\exists x(Ox \wedge Cx)$
\end{parts}
\newpage 
\question[24] Write the proof.
\begin{parts}
\part[12] Prove $Q$ from the premises $Q \vee R$, $R \rightarrow \neg P$, and $P$. \\
\textit{Solution}: \\
\[ \begin{array}{lll}
1 & (1) Q \vee R & \text{Premise} \\
2 & (2) R \rightarrow \neg P & \text{Premmise} \\
3 & (3) P & \text{Premise} \\
2 & (4) \neg \neg P \rightarrow \neg R & \text{contrapositive of (2)} \\
3 & (5) \neg \neg P & \text{double negation of (3)} \\
2,3 & (6) \neg R & \rightarrow\text{-elimination on (4), (5)} \\
1,2,3 & (7) Q & \text{m.t.p. on (1) and (6)} 
\end{array}\]

\part[12] Prove $P \rightarrow S$ from the premises $P \rightarrow Q$, $Q \rightarrow R$, and $S \vee \neg R$. \\
\textit{Solution}: \\
\[ \begin{array}{lll}
1 & (1) P \rightarrow Q & \text{Premise} \\
2 & (2) Q \rightarrow R & \text{Premise} \\
3 & (3) S \vee \neg R & \text{Premise} \\
3 & (4) \neg R \vee S & \vee\text{-commutativity on (3)} \\
3 & (5) R \rightarrow S & \text{equivalence of disjunction and implication on (4)} \\
1,2 & (6) P \rightarrow R & \text{syllogism on (1) and (2)} \\
1,2,3 & (7) P \rightarrow S & \text{syllogism on (5) and (6)}
\end{array} \]
\end{parts}
\end{questions}

\newpage 


\begin{tabular}{|l|l|l|}
\hline 
From... & Consequence & Name \\
\hline
$P$ & $\neg \neg P$ & double negation \\
$\neg \neg P$ & $P$ & double negation \\
$F, G$ & $F \wedge G$ & $\wedge$-introduction \\
$F$ & $F \vee G$ & $\vee$-introduction \\
$F \wedge G$ & $G \wedge F$ & $\wedge$-commutativity \\ 
$F \vee G$ & $G \vee F$ & $\vee$-commutativity \\
$F \wedge G$ & $F$ & $\wedge$-elimination \\
$F, F\rightarrow G$ & $G$ & $\rightarrow$-elimination \\
$F \vee G$ & $\neg ( \neg F \wedge \neg G)$ & DeMorgan \\
$\neg (\neg F \wedge \neg G)$ & $F \vee G$ & DeMorgan \\
$F \wedge G$ & $\neg (\neg F \vee \neg G)$ & DeMorgan \\
$\neg (\neg F \vee \neg G)$ & $F \wedge G$ & DeMorgan \\
$F \leftrightarrow G$ & $(F \rightarrow G) \wedge (G \rightarrow F)$ & Biconditional \\
$(F \rightarrow G) \wedge (G \rightarrow F)$ & $F \leftrightarrow G$ & Biconditional \\
$P \rightarrow Q$ & $\neg Q \rightarrow \neg P$ & contraposition \\
$\neg P, P \vee Q$ & $Q$ & modus tollendo ponens (m.t.p.) \\
$P \rightarrow Q$, $Q \rightarrow R$ & $P \rightarrow R$ & syllogism \\
$P \rightarrow Q$ & $\neg P \vee Q$ & equivalence of disjunction and implication \\
$\neg P \vee Q$ & $P \rightarrow Q$ & equivalence of disjunction and implication \\
$(P \vee R) \wedge (P \vee \neg R)$ & $P$ & proof by cases \\
\hline
\end{tabular}

\noindent \textbf{Rule of conditional proof}: if $G$ is a consequence of $P_1, \ldots, P_n$ and an additional premise $F$, then $F \rightarrow G$ is a consequence of $P_1, \ldots, P_n$

\noindent \textbf{Proof by contradiction}: if the contradiction $G \wedge \neg G$ is a consequence of premises $P_1, \ldots, P_n$ and an additional premise $F$, then $\neg F$ is a consequence of the premises $P_1, \ldots, P_n$

\noindent \textbf{Replacing double negations inside of a formula}: If $\neg \neg P$ appears as a subformula of a formula $F$, then the formula $G$, where $G$ is the same as $F$ except that $\neg \neg P$ is replaced with $P$, may be concluded.

\noindent \textbf{Substitution of propositionally equivalent statement}: If a statement $Q$ is propositionally equivalent to a statement $P$, then any instance of $Q$ inside any statement may be replaced with $P$.
\end{document}
