\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                  % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query


\def\bparts{\begin{problemparts}}
\def\eparts{\end{problemparts}}
\def\ppart{\problempart}

\renewcommand{\exampreamble}{   % !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{llll}
  Ashish    & Carole   & Christos & Eric \\
  George    & Jack     & Nick     & Tina   
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}.  There is an Appendix giving the 
  definitions of standard properties of relations.
  \item 
  There are four (4) problems totaling 100 points.  Problems are
  labeled with their point values.
  \item 
  Put your name on the top of {\bf every} page -- \emph{these
  pages may be separated for grading}.
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  \item 
  You may assume any of the results presented in class or in the
  lecture notes.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}

\begin{document} 
\quiz{1}                        % !! start the paper

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\ifshowsolutions
{}
\else
\newpage
\fi

\begin{problem}[25] Consider the following system specifications\footnote{Rosen, Exercise 1.1.35}.

\begin{enumerate}

\item The system is in multiuser state iff it is operating normally.

\item If the system is operating normally, then the kernel is functioning.

\item The kernel is not functioning or the system is in interrupt mode.

\item If the system is not in multiuser state, then it is in interrupt mode.

\item The system is not in interrupt mode.

\end{enumerate}

\begin{problemparts}

\ppart To make sense of these confusing conditions, let's introduce four Boolean
variables.
\begin{eqnarray}
M  & \eqdef &   \text{in Multiuser state}\\
N  & \eqdef &   \text{operating Normally}\\
K  & \eqdef &   \text{Kernel is functioning}\\
I  & \eqdef &   \text{in Interrupt mode}
\end{eqnarray}

Translate the five statements in the specification into propositional
logic notation: $\land,\lor,\neg,\implies,\bicond$



\ifshowsolutions
{}
\else
\begin{enumerate}

\item \hfill\brule{5in} \vspace{0.3in}

\item \hfill\brule{5in} \vspace{0.3in}

\item \hfill\brule{5in} \vspace{0.3in}

\item \hfill\brule{5in} \vspace{0.3in}

\item \hfill\brule{5in}

\end{enumerate}
\newpage
\fi


\solution{
\begin{eqnarray}
M & \bicond & N\label{M}\\
N & \implies & K \label{N}\\
\neg K & \lor & I \label{K}\\
\neg M & \implies & I \label{notM}\\
&\neg I& \label{notI}
\end{eqnarray}}

\ppart  Are these system specifications consistent?  \brule{4em}.
Prove it!

\ifshowsolutions
{}
\else
\newpage
\fi

\solution{
There are several ways to approach this problem.  One is to construct a
truth table with sixteen lines---one for each way of assigning truth
values to the four variables $M$, $N$, $K$, and $I$.

We can avoid the cumbersome truthtable if we reason by cases.  Case 1: $I$
is true.  Then the last formula~(\ref{notI}) is false, and the whole
specification is false.  Case 2: $I$ is false.  Now formula~(\ref{notM})
can be true only if $\neg M$ is false, that is, only if $M$ is true.
Likewise, formula~(\ref{K}) can be true only if $\neg K$ is true, that is,
$K$ is false.

Since $K$ is false, formula~(\ref{N}) can be true only if $N$ is
false.  Thus,
we have deduced that in order to be consistent in this case, we must have
\begin{eqnarray*}
I       & = &   \text{false} \\
M       & = &   \text{true} \\
K       & = &   \text{false} \\
N       & = &   \text{false}.
\end{eqnarray*}
But now formula~(\ref{M}) is false, so it is impossible for all the
formulas to be true: the system is inconsistent.
}
\end{problemparts}
\end{problem}


\begin{problem}[20]             % !! Define points next to each problem
For each of the following logical formulas with domain of
discourse the natural numbers, $\naturals$, indicate whether it
is a possible formulation of
\begin{itemize}
\item[I:] the \textbf{I}nduction Axiom, 
\item[S:] the \textbf{S}trong Induction Axiom,
\item[L:] the \textbf{L}east Number Principle (also known as
  Well-ordering), or
\item[N:] \textbf{N}one of these.
\end{itemize}

For example, the ordinary Induction Axiom could be expressed by the
following formula, so it gets labelled ``I''.
\[
(P(0) \land [\forall k\; P(k) \implies P(k+1)]) \implies
\forall k\; P(k) \qquad\text{\underline{\quad  I \quad}}
\] 

This is a multiple choice problem: do not explain your answer.

\begin{problemparts}

\ppart $(P(b) \land [\forall k\ge b\; P(k) \implies P(k+1)])
\implies \forall k\ge b\; P(k)$ \hfill\brule{2em} \solution{I. This is a perfect formulation of the Induction Axiom. $b$ is used for the base case; $P(k) \implies P(k+1)$ is the inductive case.}

\ppart $(P(b) \land [\forall k \le b \; P(k) \implies P(k+1)])
\implies \forall k \le b\; P(k)$ \hfill\brule{2em} \solution{N. The two occurences of $k<=b$ should have been $k>=b$}

\ppart $[\forall b\; (\forall k < b\; P(k)) \implies P(b)]
\implies \forall k\; P(k)$ \hfill\brule{2em}  \solution{S.  Since you are assuming $P(k)$ for all $k<b$, this is strong induction.}

\ppart $(\exists n\; P(n)) \implies \exists n\; \forall k < n\;
\bar{P(k)}$ \hfill\brule{2em} \solution{N. This statement is in fact
\emph{always} true; when $n=0$, $\forall k < n\;\bar{P(k)}$. It should say
$P(n) \land \forall k<n;\bar{P(k)}$}

\ppart $\forall n\; [P(n) \implies (\exists n\; P(n) \land \forall k <
n\; \bar{P(k)})]$ \hfill\brule{2em} \solution{L.  This is a valid 
formulation; it does not have that problem in (2d).}

\eparts
\end{problem}


\begin{problem}[20] Classify each of the following binary relations as
\begin{enumerate}
\item[E:] An equivalence relation.
\item[T:] A Total order,
\item[P:] A Partial order that is not total.
\item[S:] A Symmetric relation that is not transitive.
\item[N:] None of the above.
\end{enumerate}

This is a multiple choice problem: do not explain your answer.

\bparts

\ppart The relation $xRy$ between times of day such that $x$ and $y$ are
at most twenty minutes apart. \hfill\brule{2em} 

\solution{\textbf{S}: This relation is reflexive and symmetric. It is
not transitive; Consider the counter-example: {\footnotesize
1:00}$R\,${\footnotesize 1:15}, {\footnotesize
1:15}$R\,${\footnotesize 1:22} but $\neg${\footnotesize
1:00}$R\,${\footnotesize 1:22}.}

%% NOTE: THIS SHOULD SAY TIMES OF ``A'' DAY IN THE FUTURE!
\ppart The relation $xRy$ between times of day such that $x$ is more
than twenty minutes later than $y$. \hfill\brule{2em}
\solution{\textbf{P}: This relation is antisymmetric and transitive
but not reflexive (since a time isn't 20 minutes after itself). This
is not a total ordering because some times are incomparable to each
other. For example, {\footnotesize 1:15} is incomparable to
{\footnotesize 1:22}.

\textbf{Note:} This answer assumes that the question was referring to
the moments in time in a \emph{single} day.  Otherwise, one could
argue that {\footnotesize 1:00} precedes {\footnotesize 1:22} on
tuesday, but {\footnotesize 1:22} on tuesday precedes {\footnotesize
1:00} on wednesday, and then the relation would not be antisymmetric.}

\ppart The relation $xRy$ over all words in this sentence such that $x$ does
not appear after $y$.  (Consider ``$x$'', ``$y$'', and ``$xRy$'' to be words.)
\hfill\brule{2em} 

\solution{\textbf{T}: Because all the words in the sentence are
unique, this relation is transitive, antisymmetric, and reflexive.
This makes the relation a partial order.  However, the relation is
also a total order, because any two elements are comparable.}

\ppart The relation $xRy$ over all words in this sentence such that word
$x$ does not appear after word $y$.  \hfill\brule{2em} 

\solution{\textbf{P}: This is the same as saying that \emph{all}
appearances of a word $x$ occur before all appearances of a word $y$.
While apparently very similar to part \textbf{c}, this relation is not
reflexive because the word {\footnotesize word} appears twice in the
sentence.  It is transitive and antisymmetric, but not a total order
because all the words between the two occurrences of {\footnotesize word} are
incomparable to {\footnotesize word}.}

\ppart The relation $xRy$ over all words in this sentence such that the
final appearance of $y$ occurs after $x$.  \hfill\brule{2em} 

\solution{\textbf{N}: This relation is not reflexive and
transitive. It is neither symmetric nor antisymmetric; the word
{\footnotesize the} occurs twice, all the others once.  All words
$w$, between the two occurrences of {\footnotesize the} satisfy
$wR\,${\footnotesize the} and {\footnotesize the}$Rw$.  So $R$ is not
anti-symmetric.  But ``{\footnotesize $x$}'' is maximal, so it's not
symmetric either.}

\eparts
\end{problem}


\begin{problem}[35]
To encourage collaborative study, the 6.042 staff is considering assigning
each student to a study group with two or three other students.  Prove that
as long as the enrollment is large enough, the class can always be divided
into such study groups.

\solution{\begin{proof} The proof is by strong induction.  The induction
hypothesis is that a class with $n \geq 6$ students can be divided into
teams of 3 or 4.  More precisely
\[
P(n) \eqdef\quad  n\geq 6 \implies \exists x,y \in \naturals\ 3x+4y = n.
\]

For any $n \geq 0$, we may assume $P(6), \dots, P(n-1)$ to prove $P(n)$.

\textbf{Case 1:} ($n <6$).  $P(n)$ holds because the hypothesis $n \geq 6$
is false.

\textbf{Case 2:} ($n=6,7,\text{ or }8$) $P(6)$ is true because there could
be two teams of 3, $P(7)$ is true because there could be a team of 3 and a
team of 4, and $P(8)$ is true because there could be two teams of 4.

\textbf{Case 3:} ($n \geq 9$).  Of course $n> n-3$ so
$P(n-3)$ holds by the strong induction hypothesis.  But $n-3 \geq 6$, so
$P(n-3)$ implies $3x'+4y' = n-3$ for
some $x',y'\in\naturals$, and therefore $3x+4y=n$ where $x\eqdef x'+1$
and $y \eqdef y'$.  So $P(n)$ holds, as required.
\end{proof}}
\end{problem}


\ifshowsolutions
{}
\else
\newpage

\section*{Appendix}

A binary relation, $R$, on a set $A$ is
\begin{itemize}

\item \emph{reflexive} iff $xRx$,

\item \emph{symmetric} iff $xRy \implies yRx$,

\item \emph{anti-symmetric} iff $xRy \land yRx \implies x = y$,

\item \emph{transitive} iff $xRy \land yRz \implies xRz$,

\end{itemize}
for all $x, y, z \in A$.
\begin{itemize}

\item $R$ is an \emph{equivalence relation} iff it is reflexive, symmetric and
transitive.

\item $R$ is a \emph{partial order} iff it is transitive and anti-symmetric.

\item $R$ is a \emph{total order} iff it is a partial order and for all
$x \neq y \in A$ either $x R y$ or $yRx$.

\end{itemize}

\fi

\end{document}                            
