\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, hyperref,varwidth}
\pagestyle{empty}
\newcommand{\st}{~\mid~}
\newcommand{\bAlg}[1]{\begin{center}\begin{varwidth}{\textwidth}
#1
\begin{enumerate}\setlength{\itemsep}{-3pt}}
\newcommand{\eAlg}{\end{enumerate}\end{varwidth}\end{center}}
%\name{}
\assignment{CSE 20 Homework 3}
\duedate{Due: Sunday Jan 29, 2017 at noon}
\begin{document}
\begin{center}
\begin{minipage}[t]{6in}
\rule{\linewidth}{2pt}
{\sc Topics} Equivalences, Proofs, and Puzzles
\newline
{\sc Reading} Rosen Sections 1.1, 1.2, 1.3 (up to page 31).
\newline
{\sc Key Concepts} Proposition, propositional variable, truth value, compound propositions,
truth table, negation, conjunction, disjunction, exclusive or, conditional statements,
converse, contrapositive, inverse,
biconditional, bitwise operations, consistent specifications, logical equivalence,
De Morgan's laws.\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.] ({\bf 9 points})
In class, we mentioned that conjunction and disjunction are both associative. In other words,
\[
(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)
\]
and
\[
(p \vee q) \vee r \equiv p \vee (q \vee r).
\]
Use truth tables (with intermediate columns) to determine
whether or not each of the following operators are associative too.\\
{\it Note: for full credit, answer Yes or No and include a complete and correct truth table.}
\begin{itemize}
\item[(a)] Is $\oplus$ associative? That is, is it true that
$(p \oplus q) \oplus r \equiv p \oplus (q \oplus r) ?$
\item[(b)] Is $\to$ associative? That is, is it true that
$(p \to q) \to r \equiv p \to (q \to r) ?$
\item[(c)] Is $\leftrightarrow$ associative? That is, is it true that
$(p \leftrightarrow q) \leftrightarrow r \equiv p \leftrightarrow (q \leftrightarrow r) ?$
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 8 points})
Give truth assignments to the input propositional variables that show that each of the
following pairs of compound propositions are {\bf not} logically equivalent.
For example, when considering $p \wedge q$ and $p \vee q$, the truth assignment $p=T$,
$q=F$ would make $p \wedge q$ evaluate to $F$ while $p \vee q$ evaluates to $T$. Since the
two compound propositions have different truth values, they are not logically equivalent.\\
{\it Note: for full credit, give a specific truth assignment and then specify which of the two compound propositions evaluates to T and which to F, and show your calculations.}
\begin{itemize}
\item[(a)] $\neg (p \to q)$ \qquad , \qquad $p \to \neg q$ \qquad.
\item[(b)] $\neg (p \wedge q)$ \qquad , \qquad $(\neg p) \wedge (\neg q)$ \qquad.
\item[(c)] $\neg (p \to q)$ \qquad , \qquad $\neg (q \to p)$ \qquad.
\item[(d)] $p \wedge q$ \qquad , \qquad $p \leftrightarrow q$ \qquad.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 15 points})
The {\bf majority} operator $M(x,y,z)$ with three input propositional variables has value
$T$ exactly when at least two of its inputs are set to $T$. For example, $M(T,F,T) = T$
but $M(F, F,T) = F$.
\begin{itemize}
\item[(a)] Using only NOT, OR, and AND gates
\begin{center}
\includegraphics[width=5in]{gates.png}
\end{center}
draw the diagram of a circuit with three inputs $x,y,z$ whose output is the {\bf majority} function.
\item[(b)] The NAND operator takes two propositions and evaluates to F when both propositions
are T and evaluates to T otherwise; in other words, it is given by the truth table
\begin{center}
\begin{tabular}{cc|c}
$p$ & $q$ & $p$ NAND $q$ \\
\hline
$T$ & $T$ & $F$ \\
$T$ & $F$ & $T$ \\
$F$ & $T$ & $T$ \\
$F$ & $F$ & $T$
\end{tabular}
\end{center}
Find a compound proposition whose {\bf only operation is NAND} and that is logically equivalent
to $M(x,y,z)$.
{\it Note: you might find exercises 46-50 on page 36 useful.}
\end{itemize}
\end{problem}
\begin{problem}[4.] ({\bf 10 points})
Consider the compound proposition
\[
(p \to q) \to (q \to p)
\]
\begin{itemize}
\item[(a)] Rewrite this compound proposition in {\bf disjunctive normal form} (DNF).
\item[(b)] Rewrite this compound proposition in {\bf conjunctive normal form} (CNF).
\item[(c)] Is this compound proposition a {\bf tautology}? Why or why not?
\item[(c)] Is this compound proposition a {\bf contradiction}? Why or why not?
\end{itemize}
\end{problem}
\begin{problem}[5.] ({\bf 8 points})
The following puzzle is similar to the ``This sentence is false" paradox we talked
about in class. In this puzzle, we think about an imaginary island where each inhabitant either
always tells the truth or always lies. Imagine meeting two people from the island, person A and person
B. {\bf Your goal is to determine whether each one of them is a truth-teller or a liar; or whether there's not
enough information to tell}. The only information
you have is one statement each person makes.
For example, if person A says ``B lies" and person B says ``I tell the truth": it's possible that
A is telling the truth and B is lying (because A is saying that B's statement is false, and B's statement
being false means that B is a liar); and it's also possible that A is lying and B is telling the truth
(because A lying would be that the statement ``B lies" is false, which means that B is telling the truth,
and that's what B is claiming). Therefore, there's not enough information to tell who is who in this scenario.
\begin{itemize}
\item[(a)] First scenario: Person A says ``I tell the truth". Person B says ``I tell the truth".
\item[(b)] Second scenario: Person A says ``We both tell the truth." Person B says ``A lies".
\end{itemize}
{\it Note: this is an adaptation of the textbook's adaptation of Smullyan's famous puzzle. For
worked examples, see Rosen p.\ 23 numbers 19 and 21. In the textbook, truth-tellers are called
knights and liars are called knaves.}
\end{problem}
\end{document}