\documentclass[11pt]{article}

\usepackage{homework,amssymb}

\begin{document}

\dotitle{8}{Wednesday, October 24}

\bigskip

\begin{list1}

\item Study for the in-class exam on Wednesday, October 17.  In
  particular:
\begin{list2}
\item Make sure you are comfortable with the definitions and the
statements of theorems given in the book and in lectures, as well as
proofs I have gone over in class.
\item Review past homework assignments and ``unstarred'' homework
problems.
\end{list2}
The exam will cover material discussed in class through Monday,
October 15. This homework assignment is due the following Wednesday,
but some of the material that it covers will be on the exam, so you
may want to do some or all of the starred problems before then.

\item Read through Section 2.4 in Chapter 2 of van Dalen.

\item Say that a set of formulas $\Gamma$ is finitely satisfiable if
every finite subset of $\Gamma$ is satisfiable. Note that the
compactness theorem states
\begin{quote}
For every set of formulas $\Gamma$, if $\Gamma$ is finitely
satisfiable then $\Gamma$ is satisfiable.
\end{quote}
Prove (directly) that if $\Gamma$ is a finitely satisfiable set of
formulas and $\varphi$ is any formula, then either $\Gamma \cup
\varphi$ or $\Gamma \cup \{ \lnot \varphi \}$ is finitely satisfiable.

\item Do problems 8 and 9 on page 48.

\item Do problem 11 on page 48.
  
\item \addcirc Prove the compactness theorem directly, in a manner
similar to the way we proved the completeness theorem in class. (Hint:
start with a finitely satisfiable set $\Gamma$, and extend it to a
maximally finitely satisfiable set $\Gamma'$.)

\item \addcirc Do problems 2 and 3 on page 54.

\item Using the new proof rules, do problem 5 on page 55 of van
  Dalen. The backwards direction is tricky. Note that $\lnot (\ph \lor
  \psi)$ implies $\lnot \ph$, which in turn implies $\ph \limplies
  \psi$.

\item \addstar Do problem 7 on page 55.

\item \addcirc Using the proof of Theorem 1.3.8 in van Dalen, describe
  an algorithm that converts any formula $\ph$ to formulas
  $\ph^{\lor}$ and $\ph^{\land}$, in  disjunctive and conjunctive
  normal form, respectively.

\item \addstar 
\begin{list2}
\item Say that a formula $\varphi$ is {\em satisfiable} if there is a
  truth assignment $v$ such that $v$ satisfies $\ph$ (in other words,
  $v \models \ph$, or $\tval{\varphi}_v = 1$). $\ph$ is {\em
    unsatisfiable} if it is not satisfiable. Show that for any formula
  $\varphi$, $\varphi$ is unsatisfiable if and only if $\lnot \varphi$
  is valid.

\item Now suppose $\ph$ is of the form
\[
\ph_1 \lor \ph_2 \lor \ldots \lor \ph_k
\]
in disjunctive normal form, so that each formula $\ph_i$ is a
conjunction of atomic formulas and their negations. Show that $\ph$ is
satisfiable if and only if one of the conjunctions $\ph_i$ does not
contain an atomic formula $p_j$ together with its negation $\lnot
p_j$.

\item Use this, together with the previous problem, to give an
  algorithm to determine whether or not a formula $\ph$ is valid.
\end{list2}

\item \addcirc This problem outlines a more constructive approach to
  the following special case of the completeness theorem: if $\models
  \ph$, then $\proves \ph$.
\begin{list2}
\item Modify the algorithm of problem 5 so that given $\ph$, it
  outputs not only a formula $\ph^{\land}$, but also a proof of $\ph
  \liff \ph^{\land}$.
\item Show that if $\ph^{\land}$ is valid, it is easy to prove. (The
  previous problem is relevant.)
\end{list2}

\item \addcirc If $\varphi$ is any formula, show that
\[
length(\varphi^{\lor}) \leq 2^{length(\varphi)+3}.
\]
(Use the definition of $\varphi^{\lor}$ implicit in Theorem 1.3.9 on
page 26.)

\item \addcirc
\begin{list2}
\item Assuming $\varphi$ has length $n$, what is the worst-case
running time of the algorithm in part (c) of the problem 6?
\item Another way to determine if a formula $\varphi$ is a tautology
is to compute its value on every truth assignment (the ``truth table''
method). What is the worst-case running time of this algorithm?
\item Come up with a polynomial-time algorithm for determining if a
propositional formula $\varphi$ is a tautology or not, or prove that
no such algorithm exists. (Note: a successful solution to this problem
amounts to settling the famous open question, $P = NP?$.)
\end{list2}

\item Do problem 1 on page 60.
  
\item \addstar Consider a first-order language, with relation
symbols $<$ and $=$. The intended interpretation is the natural
numbers, with ``less-than'' and ``equality.'' Formalize the following
statements:
\begin{list2}
\item ``$x$ is less than or equal to $y$''
\item ``0 is the smallest number''
\item ``there is a smallest number''
\item ``there is no largest number''
\item ``every number has an immediate successor'' (in other words, for
every number, there is another one that is the ``next largest'')
\end{list2}

\item \addstar Do problem 4 on page 68. For each one, just indicate
  whether the term is ``free'' or ``not free,'' and carry out the
  substitution either way.

\end{list1}

\end{document}