% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}

\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 02 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


\problem [5pts] Construct a truth table for the compound proposition $(p \iff q) \xor (\lnot p \iff \lnot r)$.

\textit{Solution:} (only the left three columns and right-most column are required)
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|c|}
\hline
$p$ & $q$ & $r$ & $p \iff q$ & $\lnot p \iff \lnot r$ & $(p \iff q) \xor (\lnot p \iff \lnot r)$\\
\hline
$\TRUE$ & $\TRUE$ & $\TRUE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ \\ \hline
$\TRUE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ \\ \hline
$\TRUE$ & $\FALSE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ \\ \hline
$\TRUE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ \\ \hline
$\FALSE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ \\ \hline
$\FALSE$ & $\TRUE$ & $\FALSE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ \\ \hline
$\FALSE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ \\ \hline
$\FALSE$ & $\FALSE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ \\ \hline
\end{tabular}
\end{center}



% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Construct a truth table for the compound propositions $((p\implies (q\implies r))\implies s)$.


\textit{Solution:} (only the left four columns and right-most column are required)
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|c|c|}
\hline
$p$ & $q$ & $r$ & $s$ & $(q\implies r)$ & $(p\implies (q\implies r))$ & $(p \implies (q\implies r))\implies s$ \\\hline
$\TRUE$ & $\TRUE$ & $\TRUE$ & $\TRUE$    	& $\TRUE$ & $\TRUE$ &$\TRUE$   \\ \hline
$\TRUE$ & $\TRUE$ & $\TRUE$ & $\FALSE$  	& $\TRUE$  &$\TRUE$ &$\FALSE$     \\ \hline
$\TRUE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ 		& $\FALSE$ &$\FALSE$ & $\TRUE$    \\ \hline
$\TRUE$ & $\TRUE$ & $\FALSE$ & $\FALSE$ 	& $\FALSE$ & $\FALSE$& $\TRUE$    \\ \hline
$\TRUE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ 		& $\TRUE$  & $\TRUE$& $\TRUE$  \\ \hline
$\TRUE$ & $\FALSE$ & $\TRUE$ & $\FALSE$ 	& $\TRUE$  &$\TRUE$ & $\FALSE$  \\ \hline
$\TRUE$ & $\FALSE$ & $\FALSE$ & $\TRUE$ 	& $\TRUE$ & $\TRUE$& $\TRUE$  \\ \hline
$\TRUE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ 	& $\TRUE$ &$\TRUE$ &  $\FALSE$ \\ \hline
$\FALSE$ & $\TRUE$ & $\TRUE$ & $\TRUE$ 		& $\TRUE$  &$\TRUE$ &$\TRUE$   \\ \hline
$\FALSE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ 	& $\TRUE$  &$\TRUE$ & $\FALSE$  \\ \hline
$\FALSE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ 	& $\FALSE$& $\TRUE$&  $\TRUE$ \\ \hline
$\FALSE$ & $\TRUE$ & $\FALSE$ & $\FALSE$ 	& $\FALSE$& $\TRUE$& $\FALSE$  \\ \hline
$\FALSE$ & $\FALSE$ & $\TRUE$ & $\TRUE$ 	& $\TRUE$  &$\TRUE$ &$\TRUE$   \\ \hline
$\FALSE$ & $\FALSE$ & $\TRUE$ & $\FALSE$ 	& $\TRUE$  & $\TRUE$& $\FALSE$  \\ \hline
$\FALSE$ & $\FALSE$ & $\FALSE$ & $\TRUE$ 	& $\TRUE$&$\TRUE$ &  $\TRUE$ \\ \hline
$\FALSE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ 	& $\TRUE$&$\TRUE$ &  $\FALSE$ \\ \hline
\end{tabular}
\end{center}

% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] On the island of Flopi, there are three types of people: Knights, Knaves, and Floppers. All inhabitants know which type the others are, but they are otherwise indistinguishable. Knights always tell the truth. Knaves always lie. Floppers always choose to lie or tell the truth by doing the opposite of the previous speaker (i.e. if someone just spoke a lie, the flopper will tell the truth; if someone just spoke a truth, the flopper will lie). While on your vacation, you come across three inhabitants, $A$, $B$, and $C$. They say the following, in order:
\begin{quote}
$A$ says, ``We are all knights.''\\
$B$ says, ``$C$ is a knight.''\\
$C$ says, ``$A$ is a knave.''\\
$A$ says, ``$C$ lied.''
\end{quote}
Determine all possibilities of $A$, $B$, and $C$ being Knights, Knaves, or Floppers (not all need to be distinct).

\textit{Solution:} We will use a method of elimination to determine which possibilities remain.

Since $A$ first says ``We are all knights.'' and $C$ says ``$A$ is a knave,'' it is impossible that both $A$ and $C$ are telling the truth. If $A$ told the truth, then $C$ lied, and $C$ is not a knight. Thus, $A$ lied and must be a Knave or a Flopper.

Case 1: $A$ is a Knave. Then $C$ tells the truth, so $C$ is not a Knave. 

Case 1.a: If $C$ is a Knight, then $B$ tells the truth and $A$ lies in the last statement (consistent with $A$ being a Knave). Thus, $B$ is not a Knave, but could be a Knight or a Flopper (since $A$ lied before $B$'s statement). 
This leads to the following possible assignments:
\begin{quote}
$A$ : Knave, $B$ : Knight, $C$ : Knight\\
$A$ : Knave, $B$ : Flopper, $C$ : Knight
\end{quote}

Case 1.b: If $C$ is a Flopper, then $B$ lies so $B$ is not a Knight or a Flopper (since $A$ lied in the first statement). So $B$ is a Knave.
This leads to the following possible assignments:
\begin{quote}
$A$ : Knave, $B$ : Knave, $C$ : Flopper
\end{quote}

Case 2: $A$ is a Flopper. Then $C$ lies, so $C$ is not a Knight. Also note that $A$ tells the truth in the last statement, as a Flopper should. Since $C$ is not a Knight, $B$ lied, so $B$ is not a Knight or a Flopper (since $A$ lied in the first statement). Thus $B$ is a Knave. If $C$ was a Flopper, then $C$ would tell the truth, but $C$ lied. Thus, $C$ is a Knave.
This leads to the following possible assignments:
\begin{quote}
$A$ : Flopper, $B$ : Knave, $C$ : Knave
\end{quote}

Therefore, the full list of possibilities is:
\begin{quote}
\begin{tabular}{lll}
$A$ : Knave, & $B$ : Knight, &$C$ : Knight\\
$A$ : Knave, &$B$ : Flopper, &$C$ : Knight\\
$A$ : Knave, &$B$ : Knave, &$C$ : Flopper\\
$A$ : Flopper, &$B$ : Knave, &$C$ : Knave
\end{tabular}
\end{quote}






% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [5pts] Show that $[p \land (p\implies q)]\implies q$ is a tautology using truth tables.


\textit{Solution:} 
\begin{center}
\begin{tabular}[h]{|c|c|c|c|c|c|}
\hline
$p$ & $q$ &$p\implies q$ & $p \land (p \implies q)$ & $(p\land (p\implies q)) \implies q$ \\
\hline
$\TRUE$ & $\TRUE$ & $\TRUE$ & $\TRUE$ & $\TRUE$  \\ \hline
$\TRUE$ & $\FALSE$ & $\FALSE$ & $\FALSE$ & $\TRUE$  \\ \hline
$\FALSE$ & $\TRUE$ & $\TRUE$ & $\FALSE$ & $\TRUE$  \\ \hline
$\FALSE$ & $\FALSE$ & $\TRUE$ & $\FALSE$ & $\TRUE$ \\ \hline
\end{tabular}
\end{center}



% Be sure to use this \clearpage to make sure your problems are on separate pages!
\clearpage
\problem [10pts] Prove\footnote{``Prove'' means do not use truth tables!} that $(p \implies q) \lor (p \implies r)$ and $p \implies (q\lor r)$ are logically equivalent (without using this equivalence from the tables).




\textit{Solution:} 
\begin{tabular}[h]{rll}
$(p\implies q) \lor (p\implies r)$ &$\equiv (\lnot p \lor q) \lor (p \implies r)$ &   Logical equivalence using conditionals\\
&$\equiv (\lnot p \lor q) \lor (\lnot p \lor r)$ &   Logical equivalence using conditionals\\
&$\equiv (\lnot p \lor \lnot p) \lor (q\lor r)$ &   Associative and Commutative Laws\\
&$\equiv \lnot p \lor (q \lor r)$ & Idempotent law\\
&$\equiv p \implies (q\lor r)$  & Logical equivalence using conditionals. 
\end{tabular}




\clearpage
\problem [5pts] Find an assignment of the variables $p, q, r$ such that the proposition
\[ (p \lor \lnot q) \land (p \lor q) \land (q \lor r) \land (q \lor \lnot r) \land (r \lor \lnot p)\land (r \lor p) \] 
is satisfied. For a bonus 5 points, prove that this assignment is \emph{unique}. (Hint: Prove an equivalence between this proposition and the proposition $(p \iff X) \land (q \iff Y)\land (r\iff Z)$ where $(X,Y,Z)$ is your assignment.)

There are a few ways to do this problem.

\textit{Solution:} Let $p$, $q$, and $r$ all be true. Then, $p\lor \lnot q$ is true, $p \lor q$ is true, $q \lor r$ is true, $q \lor \lnot r$ is true, $r \lor \lnot p$ is true, and $r \lor p$ is true. 
Since these statements are true, the AND of all of them is true.

 \textit{Solution:} We will reduce this compound proposition into its simplest form using logical equivalences.
\begin{tabular}[h]{rll}
&$(p \lor \lnot q) \land (p \lor q) \land (q \lor r) \land (q \lor \lnot r) \land (r \lor \lnot p)\land (r \lor p)$ &\\
& $\equiv (p \lor (\lnot q \land q)) \land (q \lor r) \land (q \lor \lnot r) \land (r \lor \lnot p)\land (r \lor p)$ &   Distributive law\\
& $\equiv (p \lor (\lnot q \land q)) \land (q \lor (r \land  \lnot r)) \land (r \lor \lnot p)\land (r \lor p)$ &   Distributive law\\
& $\equiv (p \lor (\lnot q \land q)) \land (q \lor (r \land  \lnot r)) \land (r \lor (\lnot p \land p))$ &   Distributive law\\
& $\equiv (p \lor \FALSE) \land (q \lor (r \land  \lnot r)) \land (r \lor (\lnot p \land p))$ &   Negation law\\
& $\equiv (p \lor \FALSE) \land (q \lor \FALSE) \land (r \lor (\lnot p \land p))$ &   Negation law\\
& $\equiv (p \lor \FALSE) \land (q \lor \FALSE) \land (r \lor \FALSE)$ &   Negation law\\
& $\equiv p \land (q \lor \FALSE) \land (r \lor \FALSE)$ &   Identity law\\
& $\equiv p \land q \land (r \lor \FALSE)$ &   Identity law\\
& $\equiv p \land q \land r$ &   Identity law\\
\end{tabular}

Since the proposition is true if and only if $p\land q\land r$ is true, it is satisfied only by the assignment $p = q = r = \TRUE$.





\end{document} 