\documentstyle[twoside,6044]{handout}
\newcommand{\successor}{\operatorname{succ}}
\begin{document}
\handout{diagnostic-quiz}{Diagnostic Quiz}{September 6, 1995}

You will not be graded on this quiz.  Take it sometime after class,
and return it in class on Monday, September~11.  Be sure to indicate
your name, the date and ``6.044 Diagnostic Quiz'' on your answer
sheet.

\problem Have you taken 6.042, 18.063 or 18.310?  If not, what are your
qualifications for taking this course?

\problem Let $\successor$ be the successor function on integers:
\begin{eqnarray*}
  \successor(x) & = & x + 1
\end{eqnarray*}
Describe the function ($\successor \circ \successor$), that is, the
composition of $\successor$ with itself.

\problem How many strings of length 4 are there over the
alphabet~$\set{a,b,c}$?

\problem Define $\preceq$ to be the binary relation between sets
such that $A \preceq B$ if and only if the cardinality of~$A$ is less
than or equal to the cardinality of~$B$.

\begin{subproblems}
\item What is the definition of ``uncountable set''?  Now express the
definition in terms of $\preceq$.  Give an example of an uncountable
set.

\item
For each of the following properties, state whether the
relation~$\preceq$ has the property, and if not, give a simple
counterexample.
\begin{enumerate}
\item reflexivity
\item symmetricity
\item transitivity
\end{enumerate}
\end{subproblems}

\problem
For any set,~$A$, let $\pow{A}$ be the powerset of~$A$, namely, the set
of all subsets of $A$.  Exhibit the members
of~$\pow{\pow{\pow\emptyset}}$.

\problem Two Boolean formulas $F_1(x_1,\ldots,x_n)$
and~$F_2(x_1,\ldots,x_n)$ are
{\em equivalent\/} iff they yield the same truth value for all truth
assignments to the variables $x_1,\ldots,x_n$.

\begin{subproblems}
\item The  Boolean binary operation {\em conjunction\/} (and), which
our text writes as~``$\conj$'', is commutative, namely $x_1
\conj x_2$ is equivalent to $x_2 \conj x_1$.  Describe a Boolean
binary operation which is not commutative.

\item Describe an infinite set of equivalent Boolean formulas.

\item Explain why ``equivalent'' is actually an equivalence relation
on formulas.

\item Explain why there are only a finite number of equivalence
classes of formulas with (at most) variables $x_1,\ldots,x_n$.

\item How many are there?
\end{subproblems}


\problem A binary relation $\leq$ is {\em anti-symmetric\/} if $x=y$
whenever $x\leq y$ and $y\leq x$.
A {\em partial order\/} of a set~$D$ is a binary relation~$\leq$ that
is reflexive, transitive, and anti-symmetric on~$D$.
A partial order is {\em total\/} if for every $d_1,d_2\in D$, either
$d_1 \leq d_2$ or $d_2 \leq d_1$.
If $X\subset D$ and $y\leq x$ for every $x\in X$, then $y$
is a {\em lower bound\/} of~$X$.
Similarly, if $x \leq y$ for every $x \in X$, then $y$ is an {\em
  upper bound\/} of~$X$.
If $y$ is a lower bound of $X$, and $z\leq y$ for every lower
bound~$z$ of~$X$, then $y$ is the {\em greatest lower bound\/}
(``glb'' or ``meet'') of~$X$.
If $y$ is an upper bound of $X$, and $y\leq z$ for every upper
bound~$z$ of~$X$, then $y$ is the {\em least upper bound\/} (``lub'')
of~$X$.

Let $A$ be the set~$\set{1,2,3,4,5}$.
\begin{subproblems}
\item Give a total order of $A$.  That is, describe a binary
  relation~$\leq$ on~$A$ that is a total order.
\item Give a partial order of $A$ such that: (1)~every pair of elements
  has a glb; and (2) there is no lub of~$\set{4,5}$.
\item Give a partial order of $A$ such that every pair of elements has
  both an lub and a glb, but the order is not total.
\end{subproblems}

\problem
About how long did it take you to complete this quiz?


\end{document}
