\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}


80-310/610:\\
LOGIC AND COMPUTATION

\begin{tabbing}
   Midterm Exam
\hspace{115pt}
\= Name:
{\underline{\hspace{155pt}  }}
\\ \\
October 19, 2006
\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.

You may refer to one sheet of notes.

 
\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 & 15 & \\ \hline
 & & \\
2 & 20 & \\ \hline
 & & \\
3 & 10 & \\ \hline
 & & \\
4 & 10 & \\ \hline
 & & \\
5 & 25 & \\ \hline
 & & \\
6 & 20 & \\ \hline
 & & \\
{\bf Total} & {\bf 100} & \\ \hline
\end{tabular}
\end{center}
\vspace{18pt}

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

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

\newpage

{\bf Problem 1.} Let $A$ be the subset 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) (5 points)} Show that 28 is an element of $A$ by giving a
construction sequence.

\vskip 175pt

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

\newpage

{\bf Part c) (5 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) (5 points)} Show that if $\ph$ and $\psi$ are any two
formulas, and $v$ and $v'$ are truth value 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) (5 points)} What does it mean for a propositional formula
$\ph$ to be \emph{valid}?

\vskip 250pt

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

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

\newpage

{\bf Problem 3. (10 points)} Use algebraic means to put the following formula into conjunctive normal form:% (an ``and'' of ``or'''s):
\[
\lnot ((\lnot p_0 \land p_1) \lor (p_2 \limplies p_3))
\]

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

\newpage

{\bf Problem 4.} Use truth tables or a semantic argument to show the following.

{\bf Part a) (5 points)}\ $(p\land r)\limplies(q\limplies (p\lor r))$ is a tautology.


\vskip 350pt

{\bf Part b) (5 points)}\ It is not the case that $p\lor q\models p\land q$


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

\newpage

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

\vskip 10pt

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

\vskip 250pt

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

\newpage

{\bf Part c) (10 points)} $(\lnot \ph \lor \psi) \limplies (\ph
\limplies \psi)$

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

\newpage

{\bf Problem 6.}  

{\bf Part a) (5 points) State the Soundness and Completeness Theorems (and say which is which).
 
 
\vskip 100pt


%{\bf Part a) (5 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) (5 points)} Show that if $\Gamma$ is maximally consistent
%and $\Gamma \proves \ph$, then $\ph$ is in $\Gamma$.

{\bf Part b) (5 points)} Show that the following set of sentences is consistent:
\[
\{ p\vee q, \neg p \to r, \neg q\}
\]


\vskip 200pt

{\bf Part c) (10 points)}
Suppose that for formulas $\varphi$ and $\psi$ no truth valuation $v$ makes both of them true.   Show that then $\varphi\vdash \neg\psi$.

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


\end{document}