\documentclass{article}
\input{6045preamble}


\begin{document}
\handout{2}{Prof. Ron Rivest}{7 Wednesday 2002}{Jonathan
  Herzog}{Handout 2: Recitation Problems}


\begin{problem}
  Construct truth tables for all of the following formulae. For each
  pair of formulae, state which of the following holds:
  \begin{itemize}
  \item They are equivalent,
  \item They are not equivalent, but one implies the other (make sure
    to state which is which), or
  \item Neither of the above:
  \end{itemize}

  \begin{enumerate}
  \item $p \implies q$
  \item $p \vee q$
  \item $p \wedge q$
  \item $\lnot p \vee q$
  \item $\lnot (\lnot p \vee \lnot q)$
  \end{enumerate}
\end{problem}

\begin{problem}
  A Boolean formula is in \emph{disjunctive normal form} when it is in
  the form $(x_1 \wedge \lnot x_2 \wedge x_3 \ldots) \vee (x'_1 \wedge
  x'_2 \wedge \lnot x'_3 \ldots) \vee \ldots$

  \begin{enumerate}
  \item Find a boolean formula in disjunctive normal form equivalent
    to: 
    \begin{enumerate}
    \item $(p \wedge q) \implies r$
    \item $(p \vee q) \implies r$
    \end{enumerate}
  \item Sketch a proof that any Boolean formula has an equivalent formula
  in disjunctive normal form.
  \end{enumerate}
\end{problem}

\begin{problem}
  Suppose $R$ is a relation on a nonempty set $A$.  Define $R^t$ to be
  the intersection of all transitive relations on $A$ that contain
  $R$. Show that $R^t$ is transitive and the smallest transitive
  relation on $A$ containing $R$.
\end{problem}

\begin{problem}
  Let $R^u \eqdef R \union \cset{(x,y)}{\exists z . (xRz \wedge
    zRy)}$. Is $R^u = R^t$ from above? Prove that it is, or find a
  counterexample.
\end{problem}

\begin{problem}
  In a binary tree, what is the relationship between the number of
  internal nodes and the number of leaves? Prove your answer.
\end{problem}

\begin{problem}
  Create a finite automata, like the kind seen in class, that accepts
  the language $L_i = \cset{x}{x \mbox{ as a binary number is a
      multiple of }i}$, where
  \begin{enumerate}
  \item $i=2$,
  \item $i=4$,
  \item $i=6$
  \end{enumerate}
\end{problem}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
