\newcommand{\ig}[1]{}
\documentclass{article}

\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

\usepackage{shortvrb}

\ig{
\topmargin=0in
\textheight=8.5in
\textwidth=6.5in
\oddsidemargin=-.5in
\pagestyle{plain}
}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{-.0600in}
\setlength{\evensidemargin}{.0625in}

\MakeShortVerb{\|}

\begin{document}

\noindent
{\bf CSCE476/876 \hfill Fall 2020}

\begin{center}
{\bf\large Homework 6}
\end{center}

\begin{description}
\item[Assigned on:]  Friday, October 16, 2020.
\item[Due:] Friday, October 23, 2020. 
\item[Points:]  120 points + up to 20 bonus

\end{description}

\hrule\vspace{\baselineskip}

\tableofcontents
\vspace{\baselineskip}

\noindent {\bf Alert:} If you submit your homework handwritten, it must be {\em  absolutely neat} 
or it {\em will not} be corrected. If you type your homework
(preferable), submit using webhandin.\\

\hrule\vspace{\baselineskip}

\vspace{\baselineskip}

\newpage

\section{SAT Modeling \hfill (15 Points)} 
For each of the following scenarios, write a CNF formula to describe the scenario and complete the following four steps:
\begin{enumerate}
\item 
First state the propositions and what they represent.
\item
State the sentence. 
\item
Explain the meaning of the clauses. 
\item Is the sentence satisfiable? Explain why or why not.
\end{enumerate}

\subsection{Scenario A  (5 Points)}
Write a CNF formula to model the following scenario and complete the four steps from above:
\begin{enumerate}
\item There are four choices of desserts: ice cream, fruit bowl, cake, pie. 
\item Exactly one dessert must be selected (i.e., one and only one).
\end{enumerate}


\subsection{Scenario B  (5 Points)} 
Write a CNF formula to model the following scenario and complete the four steps from above:
\begin{enumerate}
\item 
Damon, Enrique, and Lois need to complete a paper and a presentation
for a class. 

\item To complete each task, they need to select a day to meet during the week (Mon,
Tue, Wed, Thu, Fri).
\item 
Damon cannot meet on Monday.  Further, he wants to complete the paper before the presentation and not both on the same day. 
\item
Enrique can meet any day but cannot meet on two consecutive days. 
\item
Lois wants to complete the presentation on or before Wednesday.
\end{enumerate}

\subsection{Scenario C  (5 Points)}  
Write a CNF formula to model the following scenario and complete the four steps from above:
\begin{enumerate}
\item 
The four states (NE, IA, KS, MO) on the map shown in
Figure~\ref{fig:map} must be colored using three colors: red, green,
and blue.
 \begin{figure}[ht]
\centerline{\includegraphics[width=1.5in]{map.pdf}}
  \caption{\small Four states (NE, IA, KS, MO)}
  \label{fig:map}
\end{figure}
\item
Each state must be colored with exactly one color.
\item
Adjacent states (i.e., states sharing a border line) cannot have the
same color.
\end{enumerate}

\section{AIMA, Exercise 7.1, page 279. \hfill (16 points)}  
\section{AIMA, Exercise 7.2, page 280. \hfill (5 points)}  

\section{AIMA, Exercise 7.7, page 281. \hfill (6 points)}




\section{Truth Tables \hfill (8 points)}
Use truth tables to show that each of the following is a
tautology.
\begin{enumerate}
\item $(p \land q) \to \neg (\neg p \lor \neg q)$
\item $[Mary \land (Mary \to Susy)] \to Susy$
\item $\alpha \to [\beta \to (\alpha \land \beta)]$
\item $(a \to b) \to [(b \to c) \to (a \to c)]$
\end{enumerate}


\section{AIMA, Exercise 7.10, page 281. \hfill (16 points)} 
Only b, c, d, e, f, and g. 

\section{Logical Equivalences \hfill (8 points)}
Using a method of your choice, verify:
\begin{enumerate}
\item $(\alpha \to \beta) \equiv $
$(\neg \beta \to \neg \alpha)$ contraposition

\item $\neg (\alpha \land \beta) \equiv $
$(\neg \alpha \lor \neg \beta)$ de Morgan

\item $(\alpha \land (\beta \lor \gamma)) \equiv $
$((\alpha \land \gamma) \lor (\alpha \land \beta))$ 
distributivity of $\land$ over $\lor$
\end{enumerate}

\section{AIMA, Exercise 7.22, page 284. \hfill (18 points + 20 bonus)}
Parts a, b, and c are required. Parts d, e, and f are bonus.

\section{Proofs \hfill (28 points)}
Give the explantions of each step if the steps are given, and give
both the explanation and step if they are not.

\begin{itemize}

\item If $q \land (r \land p), t \to v, v \to \neg p,$ then $\neg t \land r.$

{\bf Proof \hfill Explanations \hfill}
\begin{enumerate}
\item $q \land (r \land p)$ \hfill Given \hfill
\item $t \to v$ \hfill Given \hfill 
\item $v \to \neg p$ \hfill Given \hfill
\item $t \to \neg p$
\item $(r \land p)$
\item $r$
\item $p$
\item $\neg \neg p$
\item $\neg t$
\item $\neg t \land r$
\end{enumerate}

\item If $p \to (q \land r), q \to s,$ and $r \to t,$ then $p \to (s \land t).$

{\bf Proof \hfill Explanations \hfill}
\begin{enumerate}
\item
\item
\item
\item
\item
\item
\item
\end{enumerate}

\item {\bf Prove by contradiction.}

If $\neg(\neg p \land q), p \to (\neg t \lor r), q,$ and $t,$ then $r.$

{\bf Proof \hfill Explanations \hfill}
\begin{enumerate}
\item $\neg(\neg p \land q)$ \hfill Given \hfill
\item $ p \to (\neg t \lor r)$ \hfill Given \hfill
\item $q$ \hfill Given \hfill
\item $t$ \hfill Given \hfill
\item $\neg r$ \hfill Negation of Conclusion \hfill
\item
\item
\item
\item
\item
\item
\item
\end{enumerate}

\end{itemize}

\end{document}


