\documentclass {exam}
\usepackage {graphicx}
\pagestyle {headandfoot}
\lfoot {\oddeven {}{Page \thepage \space of \numpages }}
\cfoot {}
\rfoot {\oddeven {Page \thepage \space of \numpages }{}}
\pointsinmargin \boxedpoints \addpoints
\newcommand \solution {\par \textbf {Solution:}\enspace }
\newcommand \NOT {\mathop {\mathrm {NOT}}}
\newcommand \AND {\mathbin {\mathrm {AND}}}
\newcommand \OR {\mathbin {\mathrm {OR}}}
\newcommand \onlyif {\mathbin {\rightarrow }}
\newcommand \NAND {\mathbin {\mathrm {NAND}}}
\newcommand \nand {\mathbin {\uparrow }}
\newcommand \NOR {\mathbin {\mathrm {NOR}}}
\newcommand \nor {\mathbin {\downarrow }}
\newcommand \TRUE {\mathrm {TRUE}}
\newcommand \IF {\mathbin {\mathrm {IF}}}
\newcommand \IFF {\mathbin {\mathrm {IFF}}}
\newcommand \XOR {\mathbin {\mathrm {XOR}}}
\newcommand \FALSE {\mathrm {FALSE}}
\begin {document}
\noindent \textbf{MATH 112}\hfill
\textbf{Week 1 homework}\hfill
\textbf{2003 August 5}
\vskip 12pt plus 4pt minus 4pt
\begin {questions}
\question [2]
State De~Morgan's laws. Use truth tables to show why they're correct.
\solution
De Morgan's laws state
that $\lnot (p \land q)$ is equivalent to $\lnot p \lor \lnot q$
and $\lnot (p \lor q)$ is equivalent to $\lnot p \land \lnot q$.

The truth table for the first law is:

\begin {tabular}{c c||c|c||c|c|c}
$p$ & $q$     &     $p \land q$   &   $\lnot(p \land q)$     &
$\lnot p$   &   $\lnot q$   &   $\lnot p \lor \lnot q$\\
\hline
$T$ & $T$     &     $T$   &   $F$     &     $F$   &   $F$   &   $F$\\
$T$ & $F$     &     $F$   &   $T$     &     $F$   &   $T$   &   $T$\\
$F$ & $T$     &     $F$   &   $T$     &     $T$   &   $F$   &   $T$\\
$F$ & $F$     &     $F$   &   $T$     &     $T$   &   $T$   &   $T$\\
\end {tabular}

$\lnot(p \land q)$ and $\lnot{p} \lor \lnot{q}$ have the same truth table,
so they are equivalent.

The truth table for the second law is:

\begin {tabular}{c c||c|c||c|c|c}
$p$ & $q$     &     $p \lor q$   &   $\lnot(p \lor q)$     &
$\lnot p$   &   $\lnot q$   &   $\lnot p \land \lnot q$\\
\hline
$T$ & $T$     &     $T$   &   $F$     &     $F$   &   $F$   &   $F$\\
$T$ & $F$     &     $T$   &   $F$     &     $F$   &   $F$   &   $T$\\
$F$ & $T$     &     $T$   &   $F$     &     $F$   &   $T$   &   $F$\\
$F$ & $F$     &     $F$   &   $T$     &     $T$   &   $T$   &   $T$\\
\end {tabular}

$\lnot(p \lor q)$ and $\lnot{p} \land \lnot{q}$ have the same truth table,
so they are equivalent.
\question [1]
Assume that $P$ is a compound proposition
obtained from $p_{1},\ldots,p_{n}$ by using only
negation ($\NOT$, or~$\neg$), disjunction ($\OR$, or~$\vee$),
and conjunction ($\AND$, or~$\wedge$).
State the definition of the \textbf{dual} $P^{*}$ of $P$.
\solution
To form $P^{*}$ from $P$,
change every $\AND$ to an $\OR$ and every $\OR$ to an $\AND$.
[\textsl{There is no change to\/ $\NOT$.}]
\question [1]
Assume that $P$ and $Q$ are logically equivalent compound propositions
obtained from $p_{1},\ldots,p_{n}$ by using only
negation, disjunction, and conjunction.
Show that the duals $P^{*}$ and $Q^{*}$ are also logically equivalent.
[Hint: \textsl{You may want to use De~Morgan's laws.}]
\solution
The generalised De Morgan Law is
$$\lnot P(p_{1},\ldots,p_{n}) \equiv P^{*}(\lnot p_{1},\ldots,\lnot p_{n}).$$
If $P \equiv Q$, then $\lnot P \equiv \lnot Q$,
so by De Morgan, $P^{*}(\lnot p_{1},\ldots,\lnot p_{n})
\equiv Q^{*}(\lnot p_{1},\ldots,\lnot p_{n})$.
But $P^{*}$ and $Q^{*}$ are determine by their form,
so $P^{*} \equiv Q^{*}$ as well.
\question [2]
State the definitions of \textbf{tautology} and \textbf{contradiction}.
\solution
A tautology is a statement that is always true,
no matter what truth values are used
for the primitive propositions that make it up.
Similarly, a contradiction is a statement that is always false.
\question
Show that $\bigl(p \wedge (p \onlyif q)\bigr) \onlyif q$ is a tautology using:
\begin {parts}
\part [1]
truth tables.
\solution
The truth table for $\bigl(p \land (p \onlyif q)\bigr) \onlyif q$ is:

\begin {tabular}{c c||c|c|c}
$p$ & $q$     &     $p \onlyif q$   &   $p \land (p \onlyif q)$  &
$\bigl(p \land (p \onlyif q)\bigr) \onlyif q$\\
\hline
$T$ & $T$     &     $T$   &   $T$   &   $T$  \\
$T$ & $F$     &     $F$   &   $F$   &   $T$  \\
$F$ & $T$     &     $T$   &   $F$   &   $T$  \\
$F$ & $F$     &     $T$   &   $F$   &   $T$  \\
\end {tabular}

Since this is $T$ is every row, we have a tautology.
\part [1]
logical equivalences.
\solution
One proof is:
\begin {eqnarray*}
\bigl(p \land (p \onlyif q)\bigr) \onlyif q &
\equiv & \lnot\bigl(p \land (p \onlyif q)\bigr) \lor q \\
& \equiv & \lnot p \lor \lnot(\lnot p \lor q) \lor q \\
& \equiv & \lnot p \lor (p \land \lnot q) \lor q \\
& \equiv & (\lnot p \lor p \lor q) \land (\lnot p \lor \lnot q \lor q) \\
& \equiv & (T \lor q) \land (p \lor T) \\
& \equiv & T \land T \\
& \equiv & T
\end {eqnarray*}
[\textsl{There are several other ways that you could have gone through this.}]
\end {parts}
\question \relax [\textsl{Disjunctive normal form.}]
A compound proposition is in \textbf{disjunctive normal form}
if it obtained by taking
the disjunction of conjunctions of the variables and their negations,
with one conjunction for each combination of truth values
for which the proposition is true.
[Hint: \textsl{Consider individual rows of the truth table.}]
\begin {parts}
\part [2] \label {conjunctions}
Let $p_{1},\ldots,p_{n}$ be propositions.
Given arbitrary truth values $t_{1},\ldots,t_{n}$,
find a compound proposition which is true
exactly when the proposition $p_{i}$ has the truth value $t_{i}$.
[Hint: \textsl{This can be done using only
conjunctions (\/$\AND$, or\/ $\wedge$)
of the propositions\/ $p_{i}$ and their negations.}]
\solution
This part has to do with a single row of the truth table.
We wish to make this row true and all of the others false.
As an abbreviation, let $p'_{i}$ be $p_{i}$ if $t_{i} = T$
and let it be $\lnot p_{i}$ if $t_{i} = F$.
Then the conjunction which is true
exactly when each $p_{i}$ has truth value $t_{i}$ is:
$$p'_{1} \land \cdots \land p'_{n}\textnormal{.}$$
Because $p'$ is just an abbreviation here,
this statement is actually a conjunction of the $p_{i}$ and their negations.
\part [2] \label {disjunctions}
Suppose now that a truth table in $n$ propositional variables is specified.
Use part \ref{conjunctions}
to construct a compound proposition with this truth table.
[Hint: \textsl{This can be done using only
disjunctions (\/$\OR$, or\/ $\vee$)
of compound propositions of the form you found in part \ref{conjunctions}.}]
\solution
We get a statement like the answer to part \ref{conjunctions}
for each of the $2^{n}$ rows of the truth table.
Let these statements be abbreviated $q_{1},\ldots,q_{2^{n}}$ in order.
Then let $q'_{i}$ be $q_{i}$ if $T$ appears in that row of the truth table,
and let it be $F$ is $F$ appears in that row.
Then the disjunction with that truth table is:
$$q'_{1} \lor \cdots q'_{2^{n}}\textnormal{.}$$
Because $q'$ is just an abbreviation here,
this statement is actually a disjunction
of conjunctions of the $p_{i}$ and their negations.
Actually, there are also some $F$ in the disjunction ---
so just throw those out without changing the truth value.
\part
Use parts \ref{conjunctions} and \ref{disjunctions}
to explain why the disjunctive normal form of a truth table always exists.
\solution
In part \ref{disjunctions},
we constructed a statement with any given truth table.
This statement was a disjunction of conjunctions
as required for the disjunctive normal form.
But also, each of the individual conjunctions
was true for only one row in the truth table ---
specifically the rows where the proposition is true.
So this is in disjunctive normal form.
[\textsl{I decided that this question was badly written, so I didn't grade it.
But I hope that you understand the explanation!\/}]
\part [1]
What is the disjunctive normal form of $p \onlyif q$?
\solution
The truth table for $p \onlyif q$ is:

\begin {tabular}{c c||c}
$p$ & $q$    &    $p \onlyif q$\\
\hline
T & T     &     T \\
T & F     &     F \\
F & T     &     T \\
F & F     &     T \\
\end{tabular}

This is true in rows $1$, $3$, and $4$ of the truth table.
That is, $q'_{1} = q_{1}$, $q'_{3} = q_{3}$, and $q'_{4} = q_{4}$.
But $q'_{2} = F$, so we don't include it.
Thus the statement will be $q_{1} \lor q_{3} \lor q_{4}$.
To find $q_{1}$, note that both $p$ and $q$ are true in row $1$.
That is, $t_{1}$ and $t_{2}$ and both $T$ there.
Thus $p'_{1} = p_{1} = p$ and $p'_{2} = p_{2} = q$,
so $q_{1} = p'_{1} \land p'_{2} = p \land q$.
But in row $3$, $t_{1}$ is $F$, so $p'_{1} = \lnot p_{1} = \lnot p$ there.
Thus $q_{3} = p'_{1} \land p'_{2} = \lnot p \land q$.
Finally in row $4$, $t_{2}$ is also $F$,
so $p'_{2} = \lnot p_{2} = \lnot q$ now.
Thus $q_{4} = p'_{1} \land p'_{2} = \lnot p \land \lnot q$.
So in all, the statement is $q_{1} \lor q_{3} \lor q_{4}
= (p \land q) \lor (\lnot p \land q) \lor (\lnot p \land \lnot q)$.
[\textsl{You didn't need any explanation to get credit here.}]
\end {parts}
\question \label {nandnor}
We define the logical operators $\NAND$, or $\nand$, and $\NOR$, or $\nor$,
by $p \nand q := \neg(p \wedge q)$ and $p \nor q := \neg(p \vee q)$.
\begin {parts}
\part [1]
Find a proposition equivalent to $\neg{p}$ using only $\nor$.
\solution
$p \equiv p \lor p$, so $\lnot p \equiv \lnot(p \lor p) = p \nor p$.
\part [1]
Find a proposition equivalent to $p \wedge q$ using only $\nand$.
\solution
$P \nand P = \lnot(P \land P) \equiv \lnot P$ similarly,
so $p \land q \equiv \lnot(p \nand q) \equiv (p \nand q) \nand (p \nand q)$.
[\textsl{Note that\/ $\nand$ is not associative,
so you need parentheses here.}]
\end {parts}
\question \relax [\textsl{Functional completeness.}]
A collection of logical operators is called \textbf{functionally complete}
if every truth table in $n$ propositional variables
is the truth table of a compound proposition
which uses only those logical operators.
\begin {parts}
\part [2]
Show that $\neg$, $\wedge$, and $\vee$
form a functionally complete collection of logical operators.
[Hint: \textsl{Use disjunctive normal form.}]
\solution
Every statement is equivalent to one in disjunctive normal form,
and that uses only $\lnot$, $\land$, and $\lor$.
[\textsl{Another solution would be
to write every other logical operator in terms of these three,
similarly to the solutions to the following parts.}]
\part [1]
Show that $\neg$ and $\wedge$ alone
form a functionally complete collection of logical operators.
[Hint: \textsl{Use De~Morgan's laws.}]
\solution
By De Morgan's Law, $p \lor q \equiv \lnot(\lnot p \land \lnot q)$.
So we don't need $\lor$ either, and $\lnot$ and $\land$ are enough.
\part [1]
Show that $\nand$ by itself
forms a functionally complete collection of logical operators.
[Hint: \textsl{Use problem \ref{nandnor}.}]
\solution
We know that $\lnot p \equiv p \nand p$
and $p \land q \equiv (p \land q) \land (p \land q)$.
So $\lnot$ and $\land$ can be replaced by $\land$ alone;
that's all that we ever need.
\end {parts}
\question [2]
How many different truth tables of compound propositions
are there involving $n$ propositional variables?
List those involving two propositions $p$ and $q$.
Do you have descriptive names (such as `$p \AND q$') for all of them?
\solution
A truth table featuring $n$ propositions has $2^{n}$ rows,
since each proposition in a given row can be true or false.
Then since each row can be true or false in a given truth table,
there are $2^{2^{n}}$ truth tables in all.

In the case where $n = 2$, this gives $2^{2^{2}} = 16$ truth tables:

\begin{tabular}{c c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
$p$ & $q$ \\
\hline
$T$ & $T$     &
$T$   &   $T$   &   $T$   &   $T$   &   $T$   &   $T$   &   $T$   &   $T$   &
$F$   &   $F$   &   $F$   &   $F$   &   $F$   &   $F$   &   $F$   &   $F$ \\
$T$ & $F$     &
$T$   &   $T$   &   $T$   &   $T$   &   $F$   &   $F$   &   $F$   &   $F$   &
$T$   &   $T$   &   $T$   &   $T$   &   $F$   &   $F$   &   $F$   &   $F$ \\
$F$ & $T$     &
$T$   &   $T$   &   $F$   &   $F$   &   $T$   &   $T$   &   $F$   &   $F$   &
$T$   &   $T$   &   $F$   &   $F$   &   $T$   &   $T$   &   $F$   &   $F$ \\
$F$ & $F$     &
$T$   &   $F$   &   $T$   &   $F$   &   $T$   &   $F$   &   $T$   &   $F$   &
$T$   &   $F$   &   $T$   &   $F$   &   $T$   &   $F$   &   $T$   &   $F$ \\
\end{tabular}

The names for these are, respectively:
`$\TRUE$', `$p \OR q$', `$p \IF q$', `$p$',
`$q \IF p$', `$q$', `$p \IFF q$', `$p \AND q$',
`$p \NAND q$', `$p \XOR q$', `$\NOT q$', none,
`$\NOT p$', none, `$p \NOR q$', and `$\FALSE$'.
So only two of these don't have snappy names yet ---
but you could invent some!
\question \label {consistent}
\begin {parts}
\part [1] \label {same}
Show that $\forall{x}\, P(x) \vee \forall{x}\, Q(x)$
and $\forall{x}\, \forall{y}\, \bigl(P(x) \vee Q(y)\bigr)$
are logically equivalent.
[Hint: \textsl{The new variable\/ $y$ is necessary
to combine the quantifications correctly.}]
\solution
Suppose that $\forall{x}\, P(x) \lor \forall{x}\, Q(x)$ is true.
That is, either $P$ holds for every value or $Q$ does (or both).
If it's $P$, then $P(x) \lor Q(y)$ is always true,
no matter what $x$ and $y$ are.
On the other hand, if $Q$ always holds,
then $P(x) \lor Q(y)$ is still always true.
Thus, $\forall{x}\, \forall{y}\, \bigl(P(x) \lor Q(y)\bigr)$ is true.

Conversely, suppose that $\forall{x}\, P(x) \lor \forall{x}\, Q(x)$ is false.
That is, $P$ fails for at least one value and so does $Q$.
Then if $x$ is a value for which $P$ fails
and $y$ is a value for which $Q$ fails,
then $P(x) \lor Q(y)$ is false,
so $\forall{x}\, \forall{y}\, \bigl(P(x) \lor Q(y)\bigr)$ must be false.

Therefore, the two statements are equivalent.
[\textsl{You don't need nearly this much detail to get credit,
but you must give a reason why
the\/ $\forall{y}$ can be pushed past the\/ $P(x)$.}]
\part [1] \label {mixed}
Show that $\forall{x}\, P(x) \vee \exists{x}\, Q(x)$
and $\forall{x}\, \exists{y}\, \bigl(P(x) \vee Q(y)\bigr)$
are logically equivalent.
\solution
Suppose that $\forall{x}\, P(x) \lor \exists{x}\, Q(x)$ is true.
That is, either $P$ holds for every value
or $Q$ holds for at least one value (or both).
If it's $P$, then $P(x) \lor Q(x)$ is always true,
no matter what $x$ is,
which means that $P(x) \lor Q(y)$ is true if we pick $y$ to just be $x$.
On the other hand, if $Q$ holds for at least one value $y$,
then $P(x) \lor Q(y)$ is still always true.
Thus, $\forall{x}\, \exists{y}\, \bigl(P(x) \lor Q(y)\bigr)$ is true.

Conversely, suppose that $\forall{x}\, P(x) \lor \exists{x}\, Q(x)$ is false.
That is, $P$ fails for at least one value
while $Q$ fails for every value.
Then if $x$ is a value for which $P$ fails,
then $P(x) \lor Q(y)$ is false no matter what $y$ is,
so $\forall{x}\, \exists{y}\, \bigl(P(x) \lor Q(y)\bigr)$ must be false.

Therefore, the two statements are equivalent.
[\textsl{You don't need nearly this much detail to get credit,
but you must give a reason why
the\/ $\exists{y}$ can be pushed past the\/ $P(x)$.}]
\end {parts}
\question \relax [\textsl{Prenex normal form.}]
A proposition is in \textbf{prenex normal form}
if it consists of a string of quantifiers (universal or existential)
followed by a compound proposition involving no quantifiers.
\begin {parts}
\part
Put the following statements in prenex normal form:
[Hint: \textsl{Use problem \ref{consistent} for some of these.}]
\begin {subparts}
\subpart [1]
$\neg\forall{x}\, P(x)$;
\solution
By the qualifier version of De Morgan's Law,
$\lnot\forall{x}\, P(x) \equiv \exists{x}\, \lnot P(x)$.
\subpart [1]
$\neg\exists{x}\, P(x);$
\solution
By the other qualifier version of De Morgan's Law,
$\lnot\exists{x}\, P(x) \equiv \forall{x}\, \lnot P(x)$.
\subpart [1]
$\forall{x}\, P(x) \wedge \forall{x}\, Q(x);$
\solution
This just means that $P$ and $Q$ are both always true;
$\forall{x}\, P(x) \land \forall{x}\, Q(x)
\equiv \forall{x}\, \bigl(P(x) \land Q(x)\bigr)$.
[\textsl{An answer involving\/ $y$ is also correct.}]
\subpart [1] \label {someandall}
$\forall{x}\, P(x) \wedge \exists{x}\, Q(x);$
\solution
This is basically the negation of part \ref{mixed} of problem \ref{consistent},
with some of the names changed around;
$\forall{x}\, P(x) \land \exists{x}\, Q(x)
\equiv \exists{x}\, \forall{y}\, \bigl(Q(y) \land P(x)\bigr)$.
[\textsl{Using\/ $\forall\exists$ instead of $\exists\forall$ is wrong ---
in case the domain of discourse might be empty!
But nobody lost any credit for such a subtle point.}]
\subpart [1]
$\exists{x}\, P(x) \wedge \exists{x}\, Q(x);$
\solution
This is basically the negation of part \ref{same} of problem \ref{consistent},
with some of the names changed around;
$\exists{x}\, P(x) \land \exists{x}\, Q(x)
\equiv \exists{x}\, \exists{y}\, \bigl(Q(y) \land P(x)\bigr)$.
[\textsl{It makes no difference which order you write this one in.}]
\subpart [1]
$\forall{x}\, P(x) \vee \forall{x}\, Q(x);$
\solution
This is precisely part \ref{same} of problem \ref{consistent};
$\forall{x}\, P(x) \lor \forall{x}\, Q(x)
\equiv \forall{x}\, \forall{y}\, \bigl(P(x) \lor Q(y)\bigr)$.
\subpart [1]
$\forall{x}\, P(x) \vee \exists{x}\, Q(x);$
\solution
This is precisely part \ref{mixed} of problem \ref{consistent};
$\forall{x}\, P(x) \lor \exists{x}\, Q(x)
\equiv \forall{x}\, \exists{y}\, \bigl(P(x) \lor Q(y)\bigr)$.
\subpart [1]
$\exists{x}\, P(x) \vee \exists{x}\, Q(x).$
\solution
This just means that $P$ and $Q$ are both sometime true;
$\exists{x}\, P(x) \lor \exists{x}\, Q(x)
\equiv \exists{x}\, \bigl(P(x) \lor Q(x)\bigr)$.
[\textsl{An answer involving\/ $y$ is also correct.}]
\end {subparts}
\part [2]
Show how to transform an arbitrary statement
into a statement in prenex normal form.
[Hint: \textsl{Use disjunctive normal form.}]
\solution
First, write all of the propositions involved in disjunctive normal form.
Then no logical connectives are used besides $\lnot$, $\land$, and $\lor$.
Once that's done, the above rules can be used one by one
to move all of the qualifiers to the left.
\part
Express $\exists!x\, P(x)$ (`There exists a unique $x$ such that \dots')
in prenex normal form.
[Hint: \textsl{You will need to use the statement `\/$x = y$'.}]
\solution
Normally, $\exists!x\, P(x)$ is defined
as $\exists{x}\, P(x)
\land \forall{x}\, \forall{y}\,
\Bigl(\bigl(P(x) \land P(y)\bigr) \onlyif (x = y)\Bigr)$.
That is, some $x$ exists that satisfies $P$,
and any pair $x$ and $y$ that both satisfy $P$ must be the same.
To do this systematically,
I should rewrite the conditional in disjunctive normal form,
but this isn't really necessary,
since there aren't any quantifiers involved in the conditional itself.
Only the main conjunction is standing in the way.
So if I use $Q(x,y)$
to abbreviate $\bigl(P(x) \land P(y)\bigr) \onlyif (x = y)$,
then I'm looking at $\exists{x}\, P(x) \land \forall{x}\, \forall{y}\, Q(x,y)$.
First I treat $\forall{y}\, Q(x,y)$ as a unit $R(x)$
and apply part \ref{someandall} above
to get $\exists{x}\, \forall{z}\, \bigl(P(x) \land R(z)\bigr)
= \exists{x}\, \forall{z}\, \bigl(P(x) \land \forall{y}\, Q(z,y)\bigr)$ ---
I used $z$ because $y$ was already in use.
Then if I interpret $P(x)$ as an existential statement
that just happens to be independent of its variable,
then I can use this same part \ref{someandall}
to get $\exists{x}\, \forall{z}\, \forall{y}\, \bigl(P(x) \land Q(z,y)\bigr)
= \exists{x}\, \forall{z}\, \forall{y}\,
\Bigl(P(x) \land \bigl(P(z) \land P(y)\bigr) \onlyif (z = \nobreak y)\Bigr)$.
[\textsl{Since I didn't explain\/ $\exists!$ in class soon enough,
I didn't grade this part of the problem.}]
\end {parts}
\question [2]
Describe a procedure for listing all the subsets of a finite set.
\solution
Each element in the original set is either in a given subset or not.
Label the elements with the numbers from $1$ to $n$.
To list all of the subsets, list in order
all of the strings of length $n$ consisting of the numbers $0$ and $1$.
Given an element (encoded with a number marking a location in these strings)
and a string (meant to encode a subset),
include the element in the subset
if the number in that location is $1$ but not if it's $0$.
This specifies a subset.
By going through all of the lists in order, we get all of the subsets.
[\textsl{There are other methods, like ranking the subsets by size,
but you still must describe how to list all of the subsets of a given size.}]
\question [2]
If $A,B,C$ are finite sets,
then $|A \cup B \cup C|
= |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$.
Draw a Venn diagram illustrating this;
then explain in words why it is true without using the diagram.
\solution
This picture is courtesy Victoria Winters:
\begin {center}
\includegraphics [width = 1.5 in]{ps1.png}
\end {center}
The set $A$ is coloured red, $B$ is blue, and $C$ is yellow.
But on their intersections, the colours mix.
$|A|$ counts the red, purple, grey, and orange parts;
$|B|$ counts the blue, green, grey, and purple parts;
and $|C|$ counts the yellow, orange, grey, and green parts.
Thus, purple, green, and orange get counted twice,
while grey gets counted three times.
Now, $|A \cap B|$ counts the purple and grey parts;
$|B \cap C|$ counts the green and grey parts;
and $|C \cap A|$ counts the orange and grey parts.
Thus if these are subtracted,
then purple, green, and orange will only be counted once in all.
But now grey has been
both counted three times and subtracted away again three times.
So to count grey, add $|A \cap B \cap C|$.
Thus, the formula is
$|A \cup B \cup C|
= |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C|$.
[\textsl{On the course website, you can see this diagram in living colour!\/}]

To explain the formula without referring to the diagram,
just express the parts covered by these colours in set-theoretic language.
Thus red is $A \cap \bar B \cap \bar C$,
blue is $\bar A \cap B \cap \bar C$,
yellow is $\bar A \cap \bar B \cap C$,
purple is $A \cap B \cap \bar C$,
green is $\bar A \cap B \cap C$,
orange is $A \cap \bar B \cap C$,
and grey is $A \cap B \cap C$.
Then exactly the same words make sense applied to these sets.
[\textsl{The important thing is to explain
why\/ $|A \cap B \cap C|$ is being added back in.}]
\question
Let $A_{k} := \{1,2,\ldots,k\}$ for $k = 1,2,3,\ldots\,$.
In terms of $n$, find:
\begin {parts}
\part [1]
$A_{1} \cup A_{2} \cup A_{3} \cup \cdots \cup A_{n}$;
\solution
$\{1\} \cup \{1,2\} \cup \{1,2,3\} \cup \cdots \cup \{1,2,\ldots,n\}
= \{1,2,\ldots,n\} = A_{n}$.
\part [1]
$A_{1} \cap A_{2} \cap A_{3} \cap \cdots \cap A_{n}$;
\solution
$\{1\} \cap \{1,2\} \cap \{1,2,3\} \cap \cdots \cap \{1,2,\ldots,n\}
= \{1\} = A_{1}$.
\part [1]
$A_{2} \cup A_{3} \cup \cdots \cup A_{n}$ (assuming $n \ge 2$);
\solution
$\{1,2\} \cup \{1,2,3\} \cup \cdots \cup \{1,2,\ldots,n\}
= \{1,2,\ldots,n\} = A_{n}$ still.
[\textsl{Most people got a typo which made the answer\/ $A_{3}$,
so I accepted either version.}]
\part [1]
$A_{2} \cap A_{3} \cap \cdots \cap A_{n}$ (assuming $n \ge 2$).
\solution
But $\{1,2\} \cap \{1,2,3\} \cap \cdots \cap \{1,2,\ldots,n\}
= \{1,2\} = A_{2}$ now.
\end {parts}
\question [3]
State the definitions of
\textbf{domain}, \textbf{codomain} and \textbf{range} of a function.
\solution
The domain is the set of possible arguments or inputs for the function,
while the codomain is the set of possible values or outputs.
But the range is the set of only
those outputs that are actually reached from some input.
\question
State the definitions of when a function is
\textbf{injective} (or one-to-one), \textbf{surjective} (or onto),
and \textbf{bijective} (or invertible):
\begin {parts}
\part [3]
in words;
\solution
A function is injective if distinct inputs are mapped only to distinct outputs.
It's surjective if every output is reached by some input.
And it's bijective if it's both injective and surjective.
\part [3]
in logical notation (with quantifiers).
\solution
$f\colon X \to Y$ is injective
if $(\forall{x}{\in}X)(\forall{x'}{\in}X)
\Bigl(\bigl(f(x) = f(y)\bigr) \onlyif (x = y)\Bigr)$.
$f\colon X \to Y$ is surjective
if $(\forall{y}{\in}Y)(\exists{x}{\in}X)\bigl(f(x) = y\bigr)$.
Thus $f\colon X \to Y$ is bijective
if $(\forall{x}{\in}X)(\forall{x'}{\in}X)
\Bigl(\bigl(f(x) = f(y)\bigr) \onlyif (x = y)\Bigr)
\land (\forall{y}{\in}Y)(\exists{x}{\in}X)\bigl(f(x) = y\bigr)$.
\end {parts}
\end {questions}
\end {document}
