\documentstyle[12pt,fullpage,doublespace]{article}


\setstretch{1.00}
\newcommand\os[1] {$\mit{#1}$}
%\newcommand\os[1]{#1}
 
\newcommand\imp\Rightarrow

\input{qobitree}
\pagestyle{empty}

\begin{document}

\begin{center}
\large 
%\vspace*{-1.5cm}
Harvey Mudd College\\
Computer Science \os{80}\\
Logic for Computer Science\\
Spring Semester \os{2002}\\[16pt]

Assignment \#2 -- Propositional Logic, Syntax and Semantics\\
\large
Due \os{11}:\os{00}am, Friday February \os{15}, \os{2002}
\end{center}

\vspace{0.25in}

\begin{enumerate}

\item In computing the complexity of algorithms, it is often necessary to compute the
potential size of a data set based on some parameter. 

\begin{enumerate}
\item Assuming that the set $P$ of proposisitional variables is a singleton set
(that is there is only a single propositional variable available), how many
well-formed formulas are there of lengths 1 through 10 (give the number of formulas
for each length separately). Remember to count parentheses as part of the string
length.

\item Given the same assumption as above, give a recursive definition of the formula
for $t(n)$, the number of well-formed formulas of length $n$.


\item (extra credit) Provide a closed-form (that is, non-recursive) definition for the
formula for $t(n)$.
\end{enumerate}

\item The proofs in this problem have as an immediate corollary that no proper
prefix of a well-formed propositional formula is itself a well-formed propositional
formula:

 Given a set of propositional letters, $P$, let
$\Sigma$ be the alphabet of the propositional language over $P$ as defined in class.
Define the function
$K:\Sigma\rightarrow{\cal Z}$ as follows:
\begin{itemize}
\item $K(\,${\tt(}$\;) = -2$, $K(\;${\tt)}$) = 2$
\item $K(\; p\; ) = 1$, for all $p\in P\cup \{\bot,\top\}$.
\item $K(\; \neg\; ) = 0$
\item $K(\; \land\; ) = K(\; \lor\; ) = K(\; \Rightarrow\; ) = K(\; \Leftarrow\; ) =
K(\; \equiv\; ) = -1$
\end{itemize}
Further define the function $K':\Sigma^*\rightarrow {\cal Z}$ as $K'(u_1\ldots u_n) =
K(u_1)+\cdots+K(u_n)$. 

\begin{enumerate}
\item Prove that for any $\Phi\in PROP$, $K'(\Phi) = 1$. \\
(Hint: Proceed by complete induction on the length of the formula $\Phi$.)
\item Prove that for any $w \in \Sigma^*$ such
that there is a $\Phi\in PROP$ such that
$w$ is a proper prefix of $\Phi$, $K'(w) \not= 1$. \\
(Hint: Though it may seem counter intuitive, it is easiest to 
proceed again by complete induction on the length of $\Phi$, ignoring the length of
$w$, and to prove a slightly stronger property, that $K'(w) < 1$.) 
\item Conclude that if $\Phi,\Psi\in PROP$, $\Phi$ then is not a proper prefix of
$\Psi$.
\end{enumerate}



\item For each of the following formulas, give the formation tree of the formula
and a truth-table proof that the formula is a valid:
\begin{enumerate}
\item $((a \equiv b) \imp ((a\imp c) \imp (b\imp c)))$
\item $(((a\imp c) \land (b\imp c)) \imp ((a\lor b)\imp c))$
\item $(((a\imp b)\imp a)\imp a)$
\end{enumerate}
(Note: While I think you can probably make sense of why the first two formulas are
valid by thinking about the meaning of the operators, that is probably not true of
the third. That formula, which is called Pierce's Law, seems to contradict our
notion of the meaning of implication. In fact, it is not a valid formula of
intuitionistic logic, in which implication behaves much more according to our
expectations.)


\item Prove the following theorem from the lectures:

\newcommand\thm[1] {{\bf Theorem {\rm (#1)}:}}

 \thm{2.5.12}  Given formulas $\Psi,\Xi\in PROP$ and an arbitrary  set of formulas $U
=
\{\Phi_1, \ldots, \Phi_n\} \subseteq PROP$, if $U\models \Psi$ then $U\cup\{\Xi\}
\models
\Psi$.

\item Prove the following equivalences by appeal to the equivalences given in class
(and in Figure 2.9 of the text). That is, give a series of rewritings of the
formulas on the left and right until they arrive at the same point. (Or just go
from left to right, if that seems more appropriate).

\begin{enumerate}
\item $(((\neg((\neg a) \lor (\neg b))) \imp c) \leftrightarrow (a\imp((\neg b)\lor
c)))$
\item $(((a\imp b)\imp a)\imp a)\leftrightarrow\top$
\end{enumerate}

\item Prove that the set $\{\uparrow\}$ (NAND) is logically complete by giving
formulas equivalent to each of the following that use only this one operator:

\begin{enumerate}
\item $(\neg a)$
\item $(a\land b)$
\item $(a\lor b)$
\item $(a\imp b)$
\item $(a \equiv b)$
\end{enumerate}

%\item Give a Hilbert System proof that $\{b,(a\imp(a\imp c)),(b\imp a)\}\vdash c$.

\end{enumerate}

\end{document}
