\documentclass[12pt]{article}

\usepackage{homework,amssymb,eufrak}

\addtolength{\voffset}{0.5in}
\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}
   Final Exam
\hspace{115pt}
\= Name:
{\underline{\hspace{155pt}  }}
\\ \\
December 14, 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 & 10 & \\ \hline
 & & \\
2 & 15 & \\ \hline
 & & \\
3 & 15 & \\ \hline
 & & \\
4 & 12 & \\ \hline
 & & \\
5 & 15 & \\ \hline
 & & \\
6 & 15 & \\ \hline
 & & \\
{\bf Total} & {\bf 70} & \\ \hline
\end{tabular}
\end{center}
\vspace{18pt}

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

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

\newpage

{\bf Problem 1. (10 points)} 

Let $L$ be a language with two unary predicates, $A$ and $B$. Consider
the equivalence
\[
\fa x (A(x) \lor B(x)) \liff \fa x A(x) \lor \fa x B(x).
\]

\vskip 10pt

{\bf Part a) (5 points) } Show that one direction is valid, using
semantic notions only. In particular, your answer should make it clear
that you know what ``valid'' means!

\vskip 300pt

{\bf Part b) (5 points) } Show that the other direction is not valid.

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

\newpage

{\bf Problem 2. (5 points)} 

Find a prenex sentence (i.e.~one where all the quantifiers occur up
front) equivalent to 
\[
\lnot (\ex x A(x) \limplies \fa y B(y)).
\]

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

\newpage

{\bf Problem 3. (15 points)} Give natural deduction proofs of the
following validities.

\vskip 10pt

{\bf Part a) (5 points)} $\lnot \ex x \ph(x) \limplies \fa x \lnot
\ph(x)$

\vskip 300 pt 

{\bf Part b) (5 points)} $\lnot \fa x \ph(x) \limplies \ex x \lnot
\ph(x)$

\newpage

{\bf Part c) (5 points)} $(\ex x \ph \limplies \psi) \limplies \fa x
(\ph \limplies \psi)$, where $x$ is not free in $\psi$.

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

\newpage

{\bf Problem 4. (12 points)} Give a high-level sketch of a proof of
the completeness theorem for first-order logic \emph{without}
equality. You should indicate the major steps, and state the most important
definitions and lemmas precisely; but you do not need to indicate how
to prove them.

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

\newpage

{\bf Problem 5. (15 points)} 

\vskip 10pt

{\bf Part a) (5 points)} Show that $0$ (that is, the unary predicate,
``is zero'') is definable in the structure $\la \mathbb R, + \ra$.

\vskip 250pt

{\bf Part b) (5 points)} Show that $<$ is \emph{not} definable in the
structure $\la \mathbb R, + \ra$

\newpage

{\bf Part c) (5 points)} Show that $<$ \emph{is} definable in the
structure $\la \mathbb R, +, \times \ra$.


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

\newpage

{\bf Problem 6. (15 points)} The language of a successor operation has
a single unary function, $S$. Consider structures $\mdl A = \la A,
S^{\mdl A} \ra$ satisfying the following axiom, asserting that $S$ is
injective:
\[
\fa {x,y} (S(x) = S(y) \limplies x = y).
\]
Call these ``successor structures.'' In such a structure, a
\emph{cycle} is a sequence of elements $a_0,\ldots,a_k$ such that for
each $i < k$, $S(a_i) = a_{i+1}$, and such that $S(a_k) = a_0$.

\vskip 10pt

{\bf Part a) (5 points)} Show that the class of successor structures
with no cycles is definable with an infinite set of first-order
sentences.

\vskip 250pt

{\bf Part b) (5 points)} Show that the class of successor structures
with at least one cycle is \emph{not} definable in first-order logic.

\newpage

\ \\

\vskip 200pt

{\bf Part c) (5 points)} Conclude from b) that the class of successor
structures with no cycles is not definable by a finite set of
sentences.


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


\end{document}