\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29:00pm} on {\bf Friday, 22 September}. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX).}

Directions

Solve as many of the problems as you can. For maximum credit, your answers should be correct, clear, well-written, and convincing.

Sets

1. For each set $S$ defined below, indicate whether or not it is always equal to $A$, where $A$ and $B$ are arbitrary sets. Support your answer with a brief explanation.

\begin{quote} \begin{enumerate}[a.] \item $S ::= A \cup \emptyset$. \item $S ::= { x \mid x \in A \wedge x \in \overline{B} }$ \item $S ::= { x \mid x \in A \wedge x \notin \overline{A} }$ \item $S ::= A \cap (B \cup A)$. \item $S ::= A - (B \cap \overline{B})$. \end{enumerate} \end{quote}

1. Use the definitions of the set operations to prove that for all sets $A$ and $B$, $$A = (A \cap B) \cup (A - B).$$

2. In Class 7, we defined set difference as: $$\forall x. x \in A - B \iff x \in A \wedge x \notin B.$$ Provide an alternate (but equivalent in meaning) definition of set difference using only the other defined set operations (you may use any of the union ($\cup$), intersection ($\cap$), and complement ($\overline{S}$) operations in your definition, but no other operations or qualifiers). A good answer will include a proof that shows your definition is equivalent to the original set difference definition.

3. Suppose $A,B$ are two finite sets. \begin{enumerate}[a.] \item What is the smallest set $U$ that \emph{could} be a universe with respect to both sets $A,B$? \item What is $\overline{A}$ with respect to the universe defiuned in part (a)? \end{enumerate}

4. In class 7, we saw a version of De Morgan’s law for sets. In Problem 4.5 of MCS book you are asked to prove this formally. Namely, give a formal proof that $$ \overline{A \cup B} = \overline{A} \cap \overline{B} $$ for any sets $A,B$ and a universe $U$ where $A \subseteq U$ and $B \subseteq U$.

Functions and Relations

1. For each expression below, identify a domain and codomain that make $f$ a total function.\footnote{This is updated from the original version of PS4, where the question used function'' but we intended to meantotal function”. If you answered the original question already, you do not need to update your answer, just indicate clearly for which questions the function you defined is partial.} For example, for $f(x) ::= 1/x$ you could correctly answer that a possible domain is $\mathbb{R} - { 0 }$ for which a possible codomain is $\mathbb{R}$. But the domain, in this case, could not be $\mathbb{R}$ (because $1/0$ is not defined) and also for domain $\mathbb{R} - { 0 }$ the codomain could not be the rationals $\mathbb{Q}$ (because $1/\sqrt{2}$ is not a rational).

\begin{quote} \begin{enumerate}[a.] \item $f(x) ::= x + 1$

\item $f(x) ::= \frac{x}{(x - 1)}$

\item $f(S) ::= \textrm{ minimum}{<}(S \cap \mathbb{N})$ where $\textrm{ minimum}{<}$ is defined for all sets $A$ that are well-ordered by $<$ as: $$ \textrm{minimum}_{<}(A) = x \in A \textrm{ such that } \forall a \in A - { x } \ldotp x < a. $$ and $<$ is a binary relation on the real numbers. \end{enumerate} \end{quote}

1. Consider the relation $R$, defined by comparison $<$, with the domain set, ${ 1, 2, 3 }$ and codomain set, ${ 0, 1, 2 }$. Namely, $(a,b) \in R$ iff $(a<b)$.

   \begin{enumerate}[a.] \item Describe the graph of the relation. Your description can be a picture showing the graph, or some other clear way of defining that graph. \item Recall that $R$ is a set. If we let the cartesian product of the domain and codomain be the universe. What is the graph of $\overline{R}$, and what is the meaning of this relation? \end{enumerate}

2. Consider the relation, $\le$, with the domain set, $\mathbb{N}$ and codomain set $\mathbb{N}$.

   \begin{enumerate}[a.] \item Describe the graph of the relation. (For this one, you won’t be able to draw a complete picture since the domain set is infinite. Instead, your description can be a picture illustrating the graph in a clear way, or some other clear way of defining that graph.) \item Is the relation of part (a) a function? why? \end{enumerate}

3. In each case below, describe the number of elements in the cartesian product of $A$ and $B$ (i.e., $A \times B$). Explain your answers briefly.

   \begin{enumerate}[a.] \item $A = \emptyset$ and $B = {\emptyset}$. \item $A = \emptyset$ and $B = \mathbb{N} = {0,1,2,\dots }$. \item $A = {\emptyset}$ and $B = \mathbb{N} = {0,1,2,\dots }$. \end{enumerate}

4. Suppose $A,B$ are two Boolean variables, and let $OP$ be a two-input Boolean operator. In class 8 we saw that $OP$ can be seen as a function from ${T,F} \times {T,F}$ to ${T,F}$. Show that there is another way to define Boolean operators using Binary relations. Namely, show an equivalence between Boolean operators (with two inputs) and relations between ${T,F}$ and ${T,F}$.