\Question
\textbf{Lewis Carroll}
Here is an extract from Lewis Carroll's treatise \emph{Symbolic Logic} of 1896:
\begin{enumerate}
\item[(I)] No one, who is going to a party, ever fails to brush his or her hair.
\item[(II)] No one looks fascinating, if he or she is untidy.
\item[(III)] Opium-eaters have no self-command.
\item[(IV)] Everyone who has brushed his or her hair looks fascinating.
\item[(V)] No one wears kid gloves, unless he or she is going to a party.
\item[(VI)] A person is always untidy if he or she has no self-command.
\end{enumerate}
\begin{Parts}
\Part (3 points) Write each of the above six sentences as a quantified proposition over the universe of all people. You should use the following symbols for the various elementary propositions: $P(x)$ for ``$x$ goes to a party'', $B(x)$ for ``$x$ has brushed his or her hair'', $F(x)$ for ``$x$ looks fascinating'', $U(x)$ for ``$x$ is untidy'', $O(x)$ for ``$x$ is an opium-eater'', $N(x)$ for ``$x$ has no self-command'', and $K(x)$ for ``$x$ wears kid gloves''.
\Part (2 points) Now rewrite each proposition equivalently using the contrapositive.
\Part (2 points) You now have twelve propositions in total. What can you conclude from them about a person who wears kid gloves? Explain clearly the implications you used to arrive at your conclusion.
\end{Parts}
\Question
\textbf{Karnaugh Maps}
Below is the truth table for the boolean function
\begin{equation*}
Y = (\lnot A \land \lnot B \land C) \lor (\lnot A \land B \land \lnot C) \lor (A \land \lnot B \land C) \lor (A \land B \land C).
\end{equation*}
%
\begin{center}
\begin{tabular}{ c | c | c || c }
$A$ & $B$ & $C$ & $Y$ \\
\hline
0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 1 & 1
\end{tabular}
\end{center}
In this question, we will explore a different way of representing a truth table, the \emph{Karnaugh map}. A Karnaugh map is just a grid-like representation of a truth table, but as we will see, the mode of presentation can give more insight.
The values inside the squares are copied from the output column of the truth table, so there is one square in the map for every row in the truth table.
Around the edge of the Karnaugh map are the values of the input variables. Note that the sequence of numbers across the top of the map is not in binary sequence, which would be 00, 01, 10, 11. It is instead 00, 01, 11, 10, which is called \emph{Gray code} sequence. Gray code sequence only changes one binary bit as we go from one number to the next in the sequence. That means that adjacent cells will only vary by one bit, or Boolean variable. In other words, \textit{cells sharing common Boolean variables are adjacent}.
For example, here is the Karnaugh map for $Y$:
%
\begin{center}
\includegraphics[trim = 0mm 2in 0mm 1.75in, clip,width=3in]{src/problems/propositionallogic/resources/figures/kmap1}
\end{center}
%
The Karnaugh map provides a simple and straight-forward method of minimizing boolean expressions by visual inspection. The technique is to examine the Karnaugh map for any groups of adjacent ones that occur, which can be combined to simplify the expression. Note that ``adjacent'' here means in the modular sense, so adjacency wraps around the top/bottom and left/right of the Karnaugh map; for example, the top-most cell of a column is adjacent to the bottom-most cell of the column.
For example, the ones in the second column in the Karnaugh map above can be combined because $(\lnot A \land \lnot B \land C)\lor (A \land \lnot B \land C)$ simplifies to $(\lnot B \land C)$. Applying this technique to the Karnaugh map (illustrated below), we obtain the following simplified expression for $Y$:
\begin{equation*}
Y = (\lnot B \land C) \lor (A \land C) \lor (\lnot A \land B \land \lnot C).
\end{equation*}
%
\begin{center}
\includegraphics[trim = 0mm 2in 0mm 1.75in, clip,width=3in]{src/problems/propositionallogic/resources/figures/kmap2}\end{center}
%
\begin{enumerate}
\item Write the truth table for the boolean function
\begin{align*}
Z &= (\lnot A \land \lnot B \land \lnot C \land \lnot D) \lor (\lnot A \land \lnot B \land C \land \lnot D) \lor (A \land \lnot B \land \lnot C \land \lnot D) \\
&\qquad \lor (A \land \lnot B \land C \land \lnot D).
\end{align*}
\item Using your truth table, fill in the Karnaugh map for $Z$ below.
\begin{center}
\includegraphics[trim = 0mm 0in 1in 1.75in, clip,width=3in]{src/problems/propositionallogic/resources/figures/kmap3}\end{center}
\item Using your Karnaugh map, write down a simplified expression for $Z$.
\item Show that this simplification could also be found algebraically by factoring the expression for $Z$.
\end{enumerate}
\Question
\textbf{Prove or Disprove}
Prove or disprove each of the following statements. For each proof, state which of the proof types (as discussed in Note~2) you used.
\begin{Parts}
\Part
For all natural numbers $n$, if $n$ is odd then $n^2+3n$ is even.
\Part
For all real numbers $a,b$, if $a+b \ge 20$ then $a\ge 17$ or $b\ge 3$.
\Part
For all real numbers $r$, if $r$ is irrational then $r+1$ is irrational.
\Part
For all natural numbers $n$, $10n^3>n!$.
\Part
For all natural numbers $a$ where $a^5$ is odd, then
$a$ is odd.
\end{Parts}