\documentclass{article}
\usepackage{times,amssymb,amsmath}
\input{6045preamble}

%%% THIS LINE IS WHY YOU NEED TO HAVE 6045preamble.tex

\begin{document}
%%%%%%%%%% FILL IN YOUR NAME BELOW %%%%%%%%%%%%%%
\homework{1}{Prof. Nancy Lynch}{Due: February 9, 2005}{TYPE IN YOUR NAME HERE}
\large
\begin{problem} 
% [[[Covers:  Set theory.  Binary relations and their properties.
% Equivalence relations.]]]
%
  Let $\Int$ be the set of Integers. 
  Let $R$ be the binary relation on $\Int$ such that $\{a,b\} \in R$
  if and only if $ab \geq 0$.
  \begin{enumerate}
  \item[(a)] Is $R$ reflexive?  Explain.
  \item[(b)] Is $R$ symmetric?  Explain.
  \item[(c)] Is $R$ transitive?  Explain.
  \item[(d)] Define a relation $R_1 \subseteq R$ that is reflexive and
        symmetric but not transitive. 
  \item[(e)] Define a relation $R_2 \subseteq R$ that is reflexive and
        transitive but not symmetric. 

  \item[(f)] Define a relation $R_3 \subseteq R$ that is symmetric and
        transitive but not reflexive.
  \item[(g)] Define a relation $R_4 \subseteq R$ that is an equivalence
        relation.
  \end{enumerate}
\end{problem}

\noindent
%%%%%%%%%% PROBLEM 1 SOLUTION GOES HERE %%%%%%%%%%%%%%
\begin{solution}
\begin{enumerate}

\item[(a)]

\item[(b)]

\item[(c)]

\item[(d)]

\item[(e)]

\item[(f)]

\item[(g)]

\end{enumerate}
\end{solution}

\noindent
\begin{problem}
  Construct truth tables for each of the following formulas.
  Also, for each pair of formulas, state which of the following holds:
  \begin{itemize}
  \item They are equivalent,
  \item They are not equivalent, but one implies the other (say which
  is which), or
  \item Neither of the above.
  \end{itemize}
  \begin{enumerate}

  \item[(i)] $p \oplus (q \Rightarrow \lnot p)$
  \item[(ii)] $(q \Rightarrow \lnot p) \Rightarrow \lnot p$
  \item[(iii)] $(p \Rightarrow q) \Rightarrow \lnot p$
  \item[(iv)] $p \wedge \lnot q \wedge (p \Rightarrow q)$
  \end{enumerate}
\end{problem}

\noindent
%%%%%%%%%% PROBLEM 2 SOLUTION GOES HERE %%%%%%%%%%%%%%
\begin{solution}
\begin{enumerate}  %% this begins your list of items
%%% below is how you make a table in LaTeX; the four c's right
%%% after {tabular} are telling the table will be 4 columns,
%%% all columns centered, with three internal lines
\item[(a)] \begin{center}\begin{tabular}{c|c|c|c|c}
	{$p$}&{$q$}&{$\lnot p$}&{$q \Rightarrow \lnot p$}&{$p \oplus (q \Rightarrow \lnot p)$} \\ \hline
	{f}&{f}&{}&{} \\
	{f}&{t}&{}&{} \\
	{t}&{f}&{}&{} \\
	{t}&{t}&{}&{} \\
	\end{tabular}\end{center}

\item[(b)]

\item[(c)]

\item[(d)]

\item[(e)] 
% Compare every pair of truth tables here -- are they 
% equivalent/ incomparable / one implies the other ?

\end{enumerate}
\end{solution}


\noindent
\begin{problem} 
% [[[Proofs.  Induction.]]]

\begin{enumerate}
\item[(a)] 
Prove that for every natural number $n \geq 12$, there exist integers
$a,b$ such that $n=3a+7b$.
\item[(b)]
A \emph{Hamiltonian cycle} in an undirected graph is a cycle that
goes through every vertex in the graph exactly once. \\
Suppose that $G$ is an undirected graph that has a Hamiltonian cycle.
Suppose that $H$ is another undirected graph that is obtained from $G$
by adding one node at a time, along with some edges between the new
node and some of the old nodes. \\
More precisely, we have a sequence of graphs
$G = G_0, G_1, G_2,\ldots,G_k = H$, where each graph $G_{i+1}$ is
obtained from the previous graph $G_i$ by adding one node $n_{i+1}$,
together with edges connecting the new node $n_{i+1}$ to strictly more
than half of the nodes in the previous graph $G_i$.
Prove that if $G$ has a Hamiltonian cycle, 
$H$ also must have a Hamiltonian cycle.
\end{enumerate}
\end{problem}

%%%%%%%%%% PROBLEM 3 SOLUTION GOES HERE %%%%%%%%%%%%%%
\begin{solution}

\bigskip \indent
(a)
\begin{itemize}
\item {\em Inductive Hypothesis: } 
\item {\em Base case: }
\item {\em Inductive Step: }  
\end{itemize}

\bigskip \indent
(b)
\begin{itemize}
\item {\em Inductive Hypothesis: }
\item {\em Base case: }
\item {\em Inductive Step: } 
\end{itemize}

\end{solution}

\end{document}

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