\documentclass[11pt]{article}

\usepackage{homework}

\begin{document}

\dotitle{4}{Wednesday, September 19}

\begin{list1}
  
\item Read section 1.4 of the Enderton handout, which discusses unique
  readability for propositional formulas. Start reading section 1.3
  of van Dalen.
  
\item Consider the following inductive definition of the set
  of all ``AB-strings'': 
\begin{myitemize}
\item $\emptyset$, the empty string, is an ab-string
\item if $s$ is an AB-string, so is $f_1(s)$
\item if $s$ is an AB-string, so is $f_2(s)$.
\end{myitemize}
In the ``correct'' interpretation, the underlying set $U$ is a set of
strings, and $f_1$ and $f_2$ are functions that prepend the letters
``A'' and ``B'' respectively. However, if instead we take $U'$ to be
the set of strings of stars (e.g.\ ``*****''), let $f_1$ be a function
that prepends one star, and let $f_2$ be the function that prepends
two stars, then the smallest subset of $U'$ the contains $\emptyset$
and is closed under $f_1$ and $f_2$ is {\em not} generated freely.

Come up with better functions $f_1$ and $f_2$, so that they still act
on the underlying set $U'$, but make the resulting set of
``ab-strings'' freely generated.

\item \addstar Recall the definition of ``arithmetic expressions'' I
  gave in class:
\begin{myitemize}
\item any string of digits that doesn't start with ``0'' is an
arithmetic expression
\item if $s$ and $t$ are arithmetic expressions, so is ``$(s+t)$'' (more
precisely, ``(''$\concat s\concat$``+''$\concat t\concat$``)'')
\item if $s$ and $t$ are arithmetic expressions, so is ``$(s \times
t)$''. 
\end{myitemize}
Let $\fn{length}(s)$ denote the length of $s$, and let $\fn{val}(s)$
denote the evaluation function I defined in class. Prove by
induction that for every expression $s$, the inequality $val(s) \leq
10^{length(s)}$ holds.

\item \addcirc What would happen to the previous theorem if we 
were to add exponentiation, $a\uparrow b$?

\item \addstar The set of propositional formulas in prenex form is
defined inductively, as follows (the underlying set consists of
strings of variables and logical symbols):
\begin{myitemize}
\item $\bot$ is a prenex formula
\item any variable $p_i$ is a prenex formula
\item if $\varphi$ is a prenex formula, so is $\lnot \varphi$
\item if $\varphi$ and $\psi$ are prenex formulas, so is $\land
\varphi \psi$
\item if $\varphi$ and $\psi$ are prenex formulas, so is $\lor
\varphi \psi$
\item if $\varphi$ and $\psi$ are prenex formulas, so is $\limplies
\varphi \psi$
\end{myitemize}
Intuitively, this is just another notation for propositonal formulas
in which the connectives come {\em in front} of the arguments, instead
of {\em in between} them. For example, one writes $\land p_1 p_2$
instead of $(p_1 \land p_2)$. Notice, however, that in this
representation no parentheses are used.
\begin{list2}
\item Convert $\lor \lnot \limplies \land p_1 p_2 p_3 \land p_4 p_5$
  to a regular propositional formula.
\item Convert $((p_1 \land p_2) \limplies p_3) \lor (\lnot p_3
  \limplies p_1)$ to a prenex formula.
% \item Convert $\land \limplies p_1 \lnot p_2 \lor p_3 p_4$ to a
% regular propositional formula.
% \item Convert $((p_1 \lor p_2) \limplies ((\lnot p_3) \lor p_4))$ to
% a prenex formula.
\item Define a function recursively that maps prenex propositional formulas to
regular ones (you can assume that the set of prenex formulas is freely
generated).
\item Define a function recursively that maps regular propositional
formulas to prenex ones.
\end{list2}

\item Do problems 1 and 2 on page 14 of van Dalen.
  
\item \addstar Do problem 3 on page 14. In other words, show that if
  $\ph$ is a subformula of $\psi$, and $\psi$ is a subformula of
  $\theta$, then $\ph$ is a subformula of $\theta$. (Hint: say that a
  subset $A$ of $\na{PROP}$ is ``closed under subformulas'' if
  whenever a formula $\ph$ is in $A$, every subformula of $\ph$ is
  also in $A$. Show by induction formulas $\theta$, that the set of
  subformulas of $\theta$ is closed under subformulas.)
  
\item Do problem 4 on page 14. In other words, show that if $\ph$ is a
  subformula of $\psi$ and $\theta_0,\theta_1,\ldots,\theta_k$ is a
  formation sequence for $\psi$, then for some $i \leq k$, $\ph =
  \theta_i$. Be precise: use the definitions of $PROP$, formation
  sequences, and subformulas presented in class.

\item \addcirc Do problem 5 on page 15.

\item Do problems 6 and 7 on pages 14--15 of van Dalen.

\item \addstar Do problem 9 on page 15 of van Dalen.

\item \addcirc Do problem 11 on page 15.

\item \addcirc Definition 2.3.1 says that $C$ is freely generated (as
  a subset of $U$), if, {\em when restricted to $C$}, each $f_i$ is
  injective and the ranges of the $f_i$'s are disjoint from each other
  and from $B$. Certainly, if the functions $f_i$ have these properties
  on $U$, they also have it on $C$; but give an example where the
  functions do {\em not} have these properties on $U$, but $C$ is
  still freely generated.
  
\item \addcirc Generalize the recursion theorem (2.3.2) so that in
  defining $F(s)$ one can use all elements of $C$ that are ``shorter''
  than $s$ (for a given ``length'' function).

\item \addcirc Prove unique readability for prenex formulas, i.e.\
that the set of prenex formulas is freely generated. This amounts to
showing that there is only one way to ``parse'' a given formula.

\item \addcirc In the programming language of your choice, define a
data structure to represent propositional formulas as trees. (That is,
a propositional formula is either a variable, or an operation with
pointers to its arguments). Write a parser for propositional formulas,
that is, a program that takes a string as input and turns it into a
parse tree. The routine should print ``ok'' if successful, or
``error'' if the string is not a formula.

Now write routines that convert a formula to prenex form; that take an
assignment of truth values to the variables as input and determine
whether or not the resulting formula is true; and that determine
whether there is {\em any} assignment that makes the formula true.


\end{list1}


\end{document}