\documentclass[11pt]{article}

\usepackage{hw}

\begin{document}

\dotitle{3}{Thursday, September 21}

\begin{enumerate}

\item Do problems 1 and 2 on page 14 of van Dalen.

%\item Do problems 6 and 7 on page 14 of van Dalen.
 
%\item 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{itemize}
%\item $\bot$ is a prenex formula
%\item any variable $p_i$ is a prenex formula
%\item if $\varphi$ is a prenex formula, so is $\neg\varphi$
%\item if $\varphi$ and $\psi$ are prenex formulas, so is $\wedge
%\varphi \psi$
%\item if $\varphi$ and $\psi$ are prenex formulas, so is $\vee
%\varphi \psi$
%\item if $\varphi$ and $\psi$ are prenex formulas, so is $\rightarrow
%\varphi \psi$
%	\end{itemize}

%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{enumerate}

%\item Convert $\wedge \neg\rightarrow\wedge p_1 p_2 p_3 \wedge p_4 p_5$
%  to a regular propositional formula.

%\item Convert $((p_1 \wedge p_2) \rightarrow p_3) \vee (\neg p_3
%  \rightarrow p_1)$ to a prenex formula.

%\item 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 Define a function recursively that maps prenex propositional formulas to
%regular ones.

%\item Define a function that maps prenex propositional formulas to the rank of the corresponding regular formula.

%\end{enumerate}



%\item Do problem 4 on page 14 of van Dalen. In other words, show that if $\varphi$ 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$, $\varphi =
%  \theta_i$. Be precise: use the definitions of $PROP$, formation
%  sequences, and subformulas.

\item A {\em binary truth function} is any function of the form:
\[
  f : \{0,1\}\times \{0,1\}\longrightarrow \{0,1\}
\]
Note that a binary truth function is defined uniquely by its truth
table.
\begin{enumerate}
\item How many different binary truth functions are there? How many
  don't depend on any of their arguments? How many depend only on one
  of their two arguments?
\item We've seen several binary truth functions that depend on both
  arguments, namely those corresponding to the connectives $\wedge$,
  $\vee$, $\to$.  Define $\oplus$ (exclusive or), $|$ (nand, the
  sheffer stroke), and $\downarrow$ (nor), where $p | q$ is ``not both
  $p$ and $q$'', and $p \downarrow q$ is ``neither $p$ nor $q$''.
  Give the definitions by truth tables.
\end{enumerate}

\item In van Dalen, do problem 1a on page 20; problems 2, 3, and 6 on
  page 21; and problem 1 on page 27.
 
\item
\begin{enumerate}
\item Let $x\equiv y$ be an equivalence relation on a set $X$. For any
  element $x\in X$, let $[x]$ denote its equivalence class, defined by
\[
[x] = \{ a \in X \; | \; a \equiv x \}.
\]
Show that for any $a, b\in X$, one has $a \equiv b$ iff $[a] = [b]$.

\item Conclude from problems 2a and 2b on page 21 of van Dalen that
  the equivalence classes of propositional formulas are partially
  ordered.
\end{enumerate}

\item \addstar Consider equivalence modulo 5 on the natural
  numbers: $m \equiv n$ iff $m - n = 5z$ for some integer $z$.
  \begin{itemize}
  \item Define addition $\oplus$ on equivalence classes by:
\[
[m] \oplus [n] = [m+n].
\]
Show that this operation is well defined: if $m \equiv m'$
and $n \equiv n'$ then $m + n \equiv m' + n'$.

\item Try to define exponentiation $\uparrow$ on equivalence classes
  by:
\[
[m] \uparrow [n] = [m^n].
\]
Show that exponentiation is {\em not} well-defined.
\end{itemize}


\end{enumerate}


\end{document}