\documentclass[11pt]{article}

\usepackage{homework}

\begin{document}

\dotitle{5}{Wednesday, September 26}

\begin{list1}
  
\item Finish reading section 1.3, and start reading section 1.4 in van
  Dalen.

\item A {\em binary truth function} is a function $f(x,y)$
that takes values of $x$ and $y$ in the set $\{0, 1\}$ to a value in
the set $\{0,1\}$. Note that a binary truth function is defined
uniquely by its truth table.
\begin{list2}
\item How many different binary truth functions are there?
\item Two binary truth functions don't depend on any of their arguments:
the constant 0 function and the constant 1 function. How many
binary truth functions depend only on one of their two arguments?
\item We've already seen a number of binary truth functions that
depend on both arguments, namely those corresponding to the
connectives $\land$, $\lor$, $\limplies$, $\liff$, $\oplus$ (exclusive
or), $|$ (nand, or the sheffer stroke), and $\downarrow$ (nor). (The
last three are defined by $p \oplus q \equiv \lnot (p \liff q)$, $p |
q \equiv \lnot (p \land q)$, $p \downarrow q \equiv \lnot (p \lor
q)$.) 

\medskip

What are the remaining ones? You can define them in words, in
terms of the other connectives, or with truth tables.
\end{list2}

\item \addstar Show that if $k$ is a natural number and $\varphi_1,
\ldots, \varphi_k$ are propositional formulas, then $\tval{\varphi_1
  \land \ldots \land \varphi_k}_v = 1$ if and only if
$\tval{\varphi_i}_v = 1$ for each $i$ from 1 to $k$. Remember that,
for example, $\varphi_1 \land \varphi_2 \land \varphi_3$ is an
abbreviation for $((\varphi_1 \land \varphi_2) \land \varphi_3)$. Do
this carefully, using only the definition of $\tval{\cdot}_v$.

\item \addstar Show that if $\varphi_1, \ldots, \varphi_k$ and $\psi$ 
are in PROP, then the following is true: 
\[
\mbox{$\{\varphi, \ldots, \varphi_k\} \models \psi$ if and only if
  $\models \varphi_1 \land \ldots \land \varphi_k \limplies \psi$.}
\]
Once again, do this carefully, using the definition of semantic
entailment.

\item Show that if $\{ \ph \} \models \psi$ and $\{ \psi \}
  \models \theta$ then $\{ \ph \} \models \theta$.

\item \addstar Do problem 1a on page 20 of van Dalen.

\item Do problems 2, 3, 5, and 6 on page 21 of van Dalen.
 
\item Do problem 1 on page 27.
 
% \item \addstar Do the first two parts of problem 1 on page 27. For the
% second, show that the formula is equivalent to $\top$. This requires
%  some work, and some supplementary lemmas may be useful;
%  for example, you might want to show that for every $\theta$ and
%  $\eta$, $\lnot (\theta \limplies \eta) \approx \theta \land \lnot
%  \eta$.

\item \addstar Use ``algebraic means'' (as in the notes and on page 23
  of the textbook) to do problem 2 on page 28 of van Dalen.

\item Use ``algebraic means'' to show that the following are
  all tautologies:
\begin{list2}
\item $((\ph \land \lnot \psi) \lor \psi) \liff (\ph \lor \psi)$
\item $(\ph \limplies \lnot \ph) \limplies \lnot \ph$
\item $(\ph \limplies \psi) \liff (\lnot \psi \limplies \lnot \ph)$
\item $\ph \limplies (\psi \limplies \ph \land \psi)$
\end{list2}

\item \addstar Let $\equiv$ be any equivalence relation on a set 
$X$. For any element $a$ in $X$, let $[a]$ denote the equivalence
class of $a$, defined by  
\[
[a] = \{ b \in X \; | \; b \equiv a \}.
\]
Show that for any elements $a$ and $b$ of $X$, $a \equiv b$ if and
only if $[a] = [b]$. (Remember that two sets said to be are equal if and
only if they have exactly the same elements.)

\item \addstar Now let $\equiv$ denote equivalence modulo 5 on the
  natural numbers. In other words, $a \equiv b$ holds iff $a-b$ is a
  multiple of 5, that is, iff there is an integer $c$ such that $a
  - b = 5c$. 
\begin{list2}
\item Define the operation of addition $\oplus$ on equivalence
classes by
\[
[a] \oplus [b] = [a+b].
\]
Show that this operation is well defined, that is, if $a \equiv a'$
and $b \equiv b'$ then $a + b \equiv a' + b'$.
\item Define exponentiation $\uparrow$ on equivalence classes by
\[
[a] \uparrow [b] = [a^b].
\]
Show that exponentiation is {\em not} well-defined.
\end{list2}

\item \addcirc In the problem above, show that multiplication on
equivalence classes, defined by $[a] \otimes [b] = [a \times b]$, is
well-defined.

\end{list1}

\end{document}