\documentclass[12pt]{article}

\usepackage{homework,amssymb}

\setlength{\textwidth}{150mm}
\setlength{\textheight}{220mm}
% \setlength{\topmargin}{-0.2in}
\setlength{\topmargin}{0.3in}
\setlength{\oddsidemargin}{0.3in}

\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt} % 8 pt?

\pagestyle{empty}

\newcommand{\av}{\mbox{$\vec{a}$}}
\newcommand{\bv}{\mbox{$\vec{b}$}}
\newcommand{\cv}{\mbox{$\vec{c}$}}
\newcommand{\rv}{\mbox{$\vec{r}$}}


\begin{document}

\pagenumbering{arabic}


LOGIC AND COMPUTATION

\begin{tabbing}
   Midterm Exam
\hspace{115pt}
\= Name:
{\underline{\hspace{155pt}  }}
\\ \\
October 17, 2001
\end{tabbing}
\vspace{18pt}

Write your answers in the space provided, using the back of the page
if necessary. You may use additional scratch paper. Justify your
answers, and provide clear, readable explanations.

 
\vspace{36pt}


\begin{center}
\begin{tabular}{|c||c|c|} \hline 
 & & \\
{\bf   \hspace{4pt}   Problem    \hspace{4pt} } &
 {\bf    \hspace{4pt}  Points   \hspace{4pt}  }
 & {\bf  \hspace{4pt}    Score  \hspace{4pt}   }
\\ & & 
 \\ \hline\hline
 & & \\
1 & 12 & \\ \hline
 & & \\
2 & 14 & \\ \hline
 & & \\
3 & 6 & \\ \hline
 & & \\
4 & 12 & \\ \hline
 & & \\
5 & 14 & \\ \hline
 & & \\
{\bf Total} & {\bf 58} & \\ \hline
\end{tabular}
\end{center}
\vspace{18pt}

\begin{center}
{\bf GOOD LUCK}
\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

{\bf Problem 1.} Let $A$ be the set of natural numbers defined
inductively by the following clauses:
\begin{itemize}
\item $1 \in A$
\item If $n \in A$, then $2n \in A$
\item If $n \in A$, then $3n+1 \in A$
\end{itemize}

\vskip 10pt

{\bf Part a) (4 points)} Show that 28 is an element of $A$ by giving a
formation sequence.

\vskip 175pt

{\bf Part b) (4 points)} Show that 10 is not an element of $A$.

\newpage

{\bf Part c) (4 points)} Is $A$ freely generated? Justify your answer.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

{\bf Problem 2.} Remember that if $\ph$ and $\psi$ are any
propositional formulas and $p_i$ is a propositional variable, then
$\ph[\psi/p_i]$ is defined by recursion, as follows:
\begin{itemize}
\item If $\ph$ is a propositional variable $p_j$, then
\[
\ph[\psi/p_i] = \left\{
\begin{array}{ll}
  \psi & \mbox{if $i = j$} \\
  p_j & \mbox{otherwise}
\end{array}
\right.
\]
\item If $\ph$ is of the form $(\theta \mathop{\square} \eta)$, then
\[
\ph[\psi/p_i] = (\theta[\psi/p_i] \mathop{\square} \eta[\psi/p_i]).
\]
\item If $\ph$ is of the form $(\lnot \theta)$, then
\[
\ph[\psi/p_i] = (\lnot \theta[\psi/p_i]).
\]
\end{itemize}

\vskip 10pt

{\bf Part a) (6 points)} Show that if $\ph$ and $\psi$ are any two
formulas, and $v$ and $v'$ are truth assignments such that
\[
v'(p_j) = \left\{
\begin{array}{ll}
  \tval{\psi}_v & \mbox{if $i = j$} \\
  v(p_j) & \mbox{otherwise}
\end{array}
\right.
\]
then 
\[
\tval{\ph[\psi/p_i]}_v = \tval{\ph}_{v'}.
\]

\newpage
 
{\bf Part b) (4 points)} What does it mean for a propositional formula
$\ph$ to be \emph{valid}?

\vskip 250pt

{\bf Part c) (4 points)} Show (using parts a and b) that if $\ph$ is
valid then so is $\ph[\psi/p_i]$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

{\bf Problem 3. (6 points)} Put the following formula in conjunctive
normal form (an ``and'' or ``or'''s):
\[
\lnot ((\lnot p_0 \land p_1) \lor (p_2 \limplies p_3))
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

{\bf Problem 4.} Give natural deduction proofs of the following:

\vskip 10pt

{\bf Part a) (4 points)} $\lnot (\ph \land \lnot \ph)$

\vskip 250pt

{\bf Part b) (4 points)} $(\ph \limplies \psi) \limplies \lnot (\ph
\land \lnot \psi)$

\newpage

{\bf Part c) (4 points)} $\lnot (\ph \land \lnot \psi) \limplies (\ph
\limplies \psi)$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

{\bf Problem 5.} 

{\bf Part a) (4 points)} What does it mean to say that a set $\Gamma$
of propositional formulas is {\em maximally consistent}?

\vskip 150pt

{\bf Part b) (5 points)} Show that $\Gamma \cup \{ \ph \}$ is
inconsistent if and only if $\Gamma \proves \lnot \ph$.

\vskip 200pt

\newpage

{\bf Part c) (4 points)} Show that if $\Gamma$ is maximally consistent
and $\Gamma \proves \ph$, then $\ph$ is in $\Gamma$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{document}