\documentclass{article}
\input{6045preamble}


\begin{document}
\homework{1}{Prof. Ron Rivest}{Due: 13 February 2002}{}

\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) \vee (p \implies \lnot q)$
  \item $p \vee (p \implies q)$
  \item $p \wedge (p\implies q)$
  \item $(p \implies q) \vee ( \lnot p \implies q)$
  \end{enumerate}
\end{problem}

\begin{problem}
  Suppose $R$ is a relation on a nonempty set $A$.  Define $R^s \eqdef
  R \union \cset{(x,y)}{ yRx}$. Show that $R^s$ is symmetric and is
  the smallest symmetric relation on $A$ containing $R$. (We say that
  a set $S$ is the smallest set that satisfies a property $P$ if and
  only if for all other sets $S'$ that satisfy $P$, $S \subseteq S'$.)
  We call $R^s$ the \emph{symmetric closure} of $R$.
\end{problem}

\begin{problem}
  Show that every binary tree with $L$ leaves contains a subtree
  having between $L/3$ and $2L/3$ leaves, inclusive. 
\end{problem}

\begin{problem}
  A \emph{Hamiltonian cycle} in an undirected graph is a cycle that
  goes through every node in the graph exactly once. Does every
  connected, undirected graph, where each node has degree at least 3,
  contain a Hamiltonian cycle? Prove it if true, find a counterexample if
  false.
\end{problem}

\end{document}

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