\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{graphicx}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.4in}
\setlength{\textwidth}{7in}

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}
\newcommand{\divides}{\,\Big|\,}
\newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.15in}{\hfill}}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}

\newcommand{\force}{{$\mbox{\;}$}}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2in}{\bf Math 2110-101} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill September $16^{\mathrm{th}}$, 2020}

\vspace{0.2in}

\noindent {\large\bf Name:} \underline{\hskip 3.0 truein} \hfill {\bf Be sure to show your work!}

\vspace{0.2in}

\noindent {\bf\large 1. (25 points)} ``Fun'' with Truth Tables!
\begin{enumerate}[(a)]

   \item Fill out an abbreviated truth table for the following statement: $(a \vee \neg a) \to (b \wedge \neg b)$. Circle your concluding truth values and the correct answer:

   \force \hfill This statement is a {\large\bf \quad Contingency \quad / \quad Contradiction \quad / \quad Tautology}.   
   
   
\vfill

   \item Show that $\neg a \vee \neg b$ and $\neg (a \wedge b)$ are logically equivalent.

\vfill


   \item Consider the following statement: $\neg a, a \to b \vdash \neg b$. Circle the correct answers.
   
   \vspace{0.1in} 
   
   \hspace*{-0.3in} 
   {\large\bf \quad IS \quad / \quad IS NOT \quad} a theorem of $L$ by the {\large\bf \quad Soundness \quad / \quad Completeness \quad} theorem.
   
   \vfill


\end{enumerate}

\newpage
\noindent {\bf\large 2. (25 points)} System L

\begin{enumerate}[(a)]
\item I have provided a proof of Lemma L6 below -- except the justifications are missing.\\ \force \hfill Fill in the justifications and please {\bf be specific!}

\fbox{\bf Lemma L6} \quad $A \to (B \to C), B \vdash_L A \to C$

\begin{enumerate}[1:]
\item $A \to (B \to C)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $B$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $A \to B$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $(A \to (B \to C)) \to ((A \to B) \to (A \to C))$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $(A \to B) \to (A \to C)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $A \to C$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\end{enumerate}

\item Prove Lemma L10: $\vdash_L (\neg B \to \neg A) \to (A \to B)$. \hfill [You may use the deduction theorem if you wish.]

\vspace{0.05in}

\noindent {\it Hint/Suggestion:} Axiom 3 should be helpful.

\vfill

\end{enumerate}

\newpage
\noindent {\bf\large 3. (25 points)} Models, Variables, Free for\dots
   
   \begin{enumerate}[(a)]
   
   \item Consider the formula: \quad $\forall x\, (A(f(\underline{a},x),z) \to \exists y\, (B(y) \wedge C(x,y,z)))$.
   
   \vspace{0.15in}
   
   \begin{enumerate}[i.]
   \item Underline the scope of each quantifier in the above formula.
   \item {\bf Circle} all of the {\bf bound variables} in the above formula.
   \item Circle the correct answers and fill in the blanks below:   
   \end{enumerate}
   
   The formula above {\large\bf \quad IS \quad / \quad IS NOT \quad} a sentence since \quad \underline{\hspace{2.5in}}.

\vspace{0.2in}

   The term $t=g(y,\underline{a})$  {\large\bf \quad IS \quad / \quad IS NOT \quad}  free for $z$ in the formula above.

\vspace{0.2in}

   \item Consider the formula: \quad $(\forall x\,A(x,\underline{c})) \to (\exists y\, B(y))$.
   
            Translate the above formula into {\it plain English} when our model consists of the universe of all people,\\ \force \hfill $A(x,y) :=$ ``$x$ loves $y$'', $B(x) :=$ ``$x$ likes the Middle'', and $\underline{c} :=$ ``Raymond''.

\vfill


   \item Consider the formula: $(\forall x\,A(x)) \vee (\exists z\, B(f(z),\underline{c}))$.

            My model uses the universe of natural numbers $\mathbb{N} = \{0,1,2,\dots\}$ and defines $B(x,y):=$ ``$x<y$''.  Finish specifying my model in such a way that we prove the above statement is not logically valid. 
            
\vfill 

\vfill 

   \end{enumerate}


\newpage
\noindent {\bf\large 4. (25 points)} System K

\begin{enumerate}[(a)]

\item I have provided a proof of Lemma K17 below -- except the justifications are missing.\\ \force \hfill Fill in the justifications.

% version 102 use L8

\fbox{\bf Lemma K17} \quad $\forall x\, \neg A(x) \vdash_K \neg \exists x\, A(x)$

\begin{enumerate}[1:]
\item $\forall x\, \neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\forall x\, \neg A(x) \to \neg\neg \forall x\,\neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\neg\neg \forall x\,\neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\neg \exists x\, A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\end{enumerate}

\item Prove Lemma K22: $\vdash_K \exists x\, \forall y\, A(x,y) \to \forall y\, \exists x\, A(x,y)$.

\vfill

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent
\parbox{2in}{\bf Math 2110-102} 
\hfill {\Large \bf Test \#1} \hfill
\parbox{2in}{\bf \hfill September $17^{\mathrm{th}}$, 2020}

\vspace{0.2in}

\noindent {\large\bf Name:} \underline{\hskip 3.0 truein} \hfill {\bf Be sure to show your work!}

\vspace{0.2in}

\noindent {\bf\large 1. (25 points)} ``Fun'' with Truth Tables!
\begin{enumerate}[(a)]

   \item Fill out an abbreviated truth table for the following statement: $(a \vee \neg b) \to (b \wedge \neg a)$. Circle your concluding truth values and the correct answer:

   \force \hfill This statement is a {\large\bf \quad Contingency \quad / \quad Contradiction \quad / \quad Tautology}.   
   
   
\vfill

   \item Show that $\neg a \wedge \neg b$ and $\neg (a \vee b)$ are logically equivalent.

\vfill


   \item Consider the following statement: $\neg b, a \to b \vdash \neg a$. Circle the correct answers.
   
   \vspace{0.1in} 
   
   \hspace*{-0.3in} 
   {\large\bf \quad IS \quad / \quad IS NOT \quad} a theorem of $L$ by the {\large\bf \quad Soundness \quad / \quad Completeness \quad} theorem.
   
   \vfill


\end{enumerate}

\newpage
\noindent {\bf\large 2. (25 points)} System L

\begin{enumerate}[(a)]
\item I have provided a proof of Lemma L8 below -- except the justifications are missing.\\ \force \hfill Fill in the justifications and please {\bf be specific!}

\fbox{\bf Lemma L8} \quad $A \to B, B \to C \vdash_L A \to C$

\begin{enumerate}[1:]
\item $A \to B$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $B \to C$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $A \to (B \to C)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $(A \to (B \to C)) \to ((A \to B) \to (A \to C))$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $(A \to B) \to (A \to C)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $A \to C$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\end{enumerate}

\item Prove Lemma L10: $\vdash_L (\neg B \to \neg A) \to (A \to B)$. \hfill [You may use the deduction theorem if you wish.]

\vspace{0.05in}

\noindent {\it Hint/Suggestion:} Axiom 3 should be helpful.

\vfill

\end{enumerate}

\newpage
\noindent {\bf\large 3. (25 points)} Models, Variables, Free for\dots
   
   \begin{enumerate}[(a)]
   
   \item Consider the formula: \quad $\exists x\, (A(f(z),x) \to \forall y\, (B(x,y) \wedge C(\underline{a},y,w)))$.
   
   \vspace{0.15in}
   
   \begin{enumerate}[i.]
   \item Underline the scope of each quantifier in the above formula.
   \item {\bf Circle} all of the {\bf bound variables} in the above formula.
   \item Circle the correct answers and fill in the blanks below:   
   \end{enumerate}
   
   The formula above {\large\bf \quad IS \quad / \quad IS NOT \quad} a sentence since \quad \underline{\hspace{2.5in}}.

\vspace{0.2in}

   The term $t=g(y,\underline{a})$  {\large\bf \quad IS \quad / \quad IS NOT \quad}  free for $z$ in the formula above.

\vspace{0.2in}

   \item Consider the formula: \quad $(\exists x\,A(x,\underline{c})) \to (\forall y\, B(y))$.
   
            Translate the above formula into {\it plain English} when our model consists of the universe of all people,\\ \force \hfill $A(x,y) :=$ ``$x$ rescues $y$'', $B(x) :=$ ``$x$ will cheer'', and $\underline{c} :=$ ``Princess Fiona''.

\vfill


   \item Consider the formula: $(\forall x\,A(x,\underline{c})) \vee (\exists z\, B(f(z)))$.

            My model uses the universe of natural numbers $\mathbb{N} = \{0,1,2,\dots\}$ and defines $A(x,y):=$ ``$x \geq y$''.  Finish specifying my model in such a way that we prove the above statement is not logically valid. 
            
\vfill 

\vfill 

   \end{enumerate}


\newpage
\noindent {\bf\large 4. (25 points)} System K

\begin{enumerate}[(a)]

\item I have provided a proof of Lemma K17 below -- except the justifications are missing.\\ \force \hfill Fill in the justifications.

% version 102 use L8

\fbox{\bf Lemma K17} \quad $\forall x\, \neg A(x) \vdash_K \neg \exists x\, A(x)$

\begin{enumerate}[1:]
\item $\forall x\, \neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\forall x\, \neg A(x) \to \neg\neg \forall x\,\neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\neg\neg \forall x\,\neg A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\item $\neg \exists x\, A(x)$ \hfill \underline{\hspace*{3in}}

\vspace{0.2in}

\end{enumerate}

\item Prove Lemma K22: $\vdash_K \exists x\, \forall y\, A(x,y) \to \forall y\, \exists x\, A(x,y)$.

\vfill

\end{enumerate}


\end{document} 
   
