\documentclass[11pt]{article}

\usepackage{homework}

\begin{document}

\dotitle{6}{Wednesday, October 3}

\begin{list1}
  
\item Read Section 1.4 in van Dalen, and start reading Section 1.5.
  
\item \addstar Use our semantic definitions to prove or find a
  counterexample to each of the following:
\begin{list2}
\item For every set of formulas $\Gamma$, every formula $\ph$, and
  every formula $\psi$, if $\Gamma \models \varphi \land \psi$, then
  $\Gamma \models \varphi$ and $\Gamma \models \psi$.
\item For every set of formulas $\Gamma$, every formula $\ph$, and
  every formula $\psi$, if $\Gamma \models \varphi \lor \psi$, then
  $\Gamma \models \varphi$ or $\Gamma \models \psi$.
\end{list2}

\item \addstar Do problems 4 and 5 on page 28 of van Dalen. In other
  words, if $\ph \; | \; \psi$, read ``$\ph$ nand $\psi$,'' means that
  $\ph$ and $\psi$ are not both true, and $\ph \; \downarrow \; \psi$,
  read ``$\ph$ nor $\psi$,'' means that neither $\ph$ nor $\psi$ is
  true, show that $\{ | \}$ and $\{ \downarrow \}$ are complete sets of
  connectives.
  
\item Do problem 6 on page 28. In other words, show that these are the
  only two binary connectives that have this property. 

% \item Show that the connective $|$, where $\varphi \; | \; \psi$ is
%  defined to mean that $\varphi$ and $\psi$ are not both true, forms a
%  complete connective set. (See problem 4 on page 28.)
%
% \item Do problems 5 and 6 on page 28. In other words, show that
%  ``nand'' and ``nor'' are the only two complete binary connectives.
  
\item Show that $\{ \limplies, \bot \}$ is a complete set of
  connectives.

\item \addstar 
\begin{list2}
\item Show that $\{ \limplies, \lor, \land \}$ is not a complete
  set of connectives. (Hint: show that any formula involving only
  these connectives is true when all the variables are true.)
\item Conclude that $\{ \limplies, \lor, \land, \liff, \top \}$ is not
  a complete set of connectives. (Hint: define the last two in terms
  of the others.)
\end{list2}

\item
\begin{list2}
\item Show that $\{ \bot, \liff \}$ is not a complete set of
  connectives. (Hint: show that any formula involving only these
  connectives and the variables $p_0$ and $p_1$ is equivalent to one
  of the following: $\bot$, $\top$, $p_0$, $p_1$, $\lnot p_0$, $\lnot
  p_1$, $p_0 \liff p_1$, or $p_0 \oplus p_1$.)
\item Conclude that $\{ \bot, \top, \lnot, \liff, \oplus \}$ is not
  complete. (Hint: see the previous problem.)
\end{list2}

\item \addcirc How many ternary (3-ary) complete connectives are there?

\item \addcirc Do problem 7 on page 28.

\item \addstar Do problem 8 on page 28. (Hint: it might help to read
  problem 7.)

\item Make up a truth table for a ternary connective, and then
  find a formula that represents it.

\item Do problems 9 and 10 on page 28.
  
\item Using the property $\varphi \lor (\psi \land \theta) \approx
  (\varphi \lor \psi) \land (\varphi \lor \theta)$, and the dual
  statement with $\land$ and $\lor$ switched, put
\[
(p_1 \land p_2) \lor (q_1 \land q_2) \lor (r_1 \land r_2)
\]
in conjunctive normal form. (Hint: try it with $(p_1 \land p_2) 
\lor (q_1 \land q_2)$ first.)

% \item \addstar Do parts (c) and (e) of problem 1 on page 39. Remember
%  that $\ph \liff \psi$ is an abbreviation for $(\ph \limplies \psi)
%  \land (\psi \limplies \ph)$, so to prove this it is sufficient to
%  prove each direction separately.

\item \addstar Do problem 1 on page 39 of van Dalen. Remember that we
  are taking $\ph \liff \psi$ to abbreviate $(\ph \limplies \psi)
  \land (\psi \limplies \ph)$.
  
  Note that a parenthesis is missing at the end of part (f). The
  $\leftarrow$ directions of parts (d) and (e) are a little tricky,
  because they require the classical rule RAA.
  
\item Do problem 2 on page 39. 

  There is a parenthesis missing in part (b); it should read $[ \ph
  \limplies (\psi \limplies \sigma)] \liff [ \psi \limplies ( \ph
  \limplies \sigma) ]$. Here the square brackets are only used to make
  the formula more readable; they are no different from parentheses.

\end{list1}

\end{document}