\Question{Always True or Always False?}
Classify the following statements as being one of the following and justify your answers.
\begin{itemize}
\item True for all combinations of $x$ and $y$ (Tautology)
\item False for all combinations of $x$ and $y$ (Contradiction)
\item Neither
\end{itemize}
\begin{Parts}
\Part $x \land (x \implies y) \land (\neg y)$
\Part $x \implies (x \lor y)$
\Part $(x \lor y) \lor (x \lor \neg y)$
\Part $(x \implies y) \lor (x \implies \neg y)$
\Part $(x \lor y) \land (\neg(x \land y))$
\Part $(x \implies y) \land (\neg x \implies y) \land (\neg y)$
\end{Parts}
\Question{Lewis Carroll}
Here is an extract from Lewis Carroll's treatise \emph{Symbolic Logic} of 1896:
\begin{Parts}
\Part[(I)] No one, who is going to a party, ever fails to brush his or her hair.
\Part[(II)] No one looks fascinating, if he or she is untidy.
\Part[(III)] Opium-eaters have no self-command.
\Part[(IV)] Everyone who has brushed his or her hair looks fascinating.
\Part[(V)] No one wears kid gloves, unless he or she is going to a party.
\Part[(VI)] A person is always untidy if he or she has no self-command.
\end{Parts}
\begin{Parts}
\Part 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 Now rewrite each proposition equivalently using the contrapositive.
\Part 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{Equivalences with Quantifiers}
Evaluate whether the expressions on the left and right sides are equivalent in each part, and briefly justify your answers.
\begin{tabular} { | c || c | c | }
\hline
(a) & $\forall x~\big((\exists y~Q(x,y))\Rightarrow P(x)\big)$ & $\forall x~\exists y~\big(Q(x,y)\Rightarrow P(x)\big)$ \\
(b) & $\neg\exists x~\forall y~\big(P(x,y)\Rightarrow\neg Q(x,y)\big)$ & $\forall x ~\big( (\exists y~P(x,y)) \land (\exists y~Q(x,y)) \big)$ \\
(c) & $\forall x~\exists y~\big(P(x)\Rightarrow Q(x,y)\big)$ & $\forall x~\big(P(x)\Rightarrow(\exists y~Q(x,y))\big)$ \\
\hline
\end{tabular}
\Question{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{Parts}
\Part 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*}
\Part 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}
\Part Using your Karnaugh map, write down a simplified expression for $Z$.
\Part Show that this simplification could also be found algebraically by factoring the expression for $Z$.
\end{Parts}
\Question{Social Network}
Suppose that $p_{1}, p_{2}, \ldots, p_{n}$ denote $n$ people where every two people are either friends or strangers. Let $\text{Friends}(x,y)$ be the predicate ``$x$ and $y$ are friends''. Prove or provide a counterexample for the following statements.
\begin{Parts}
\Part For all cases with $n=5$ people, there exists a group of 3 people that are either all friends or all strangers. In mathematical notation we write this as:
\begin{align*}
\exists (i,j,k) &\in \{1,2, \ldots, 5\}^3 \text{ such that } i n!$.
\end{Parts}