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

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

\usepackage{url}
\usepackage{soul}
  
\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 2023}

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

\begin{description}
\item[Assigned on:]  Friday, November 10, 2023.
\item[Due:] Friday, November 17, 2023.
\item[Points:]  120 points + up to 20 bonus

\end{description}

\noindent  \textbf{Exercises:} AIMA exercises are available online: \url{https://aimacode.github.io/aima-exercises}\\

\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{Chapter 7, Exercise 1, Source: AIMA online site. \hfill (16 points)} 
Suppose the agent has progressed to the point shown in Figure 7.4(a), Page 213, having perceived nothing in [1,1], a
breeze in [2,1], and a stench in [1,2], and is now concerned with the
contents of [1,3], [2,2], and [3,1]. Each of these can contain a pit,
and at most one can contain a wumpus. Following the example of
Figure 7.5, construct the set of possible
worlds. (You should find 32 of them.)  Mark the worlds in which the KB
is true and those in which each of the following sentences is true:
\[\alpha_2 = \mbox{``There is no pit in [2,2].''}\]
\[\alpha_3 = \textrm{``There is a wumpus in [1,3].''}\]
Hence show that ${KB} \models \alpha_2$ and ${KB} \models \alpha_3$.

\section{Chapter 7, Exercise 2, Source: AIMA online site. \hfill (5 points)}  
(Adapted from Barwise and  Etchemendy (1993).)  Given the following,
can you prove that the unicorn\index{unicorn} is mythical?  How about
magical?  Horned?
\begin{quote}
If the unicorn is mythical, then it is immortal, but if it is not mythical,
then it is a mortal mammal.  If the unicorn is either immortal or a mammal,
then it is horned.  The unicorn is magical if it is horned.
\end{quote}

\section{Chapter 7, Exercise 9, Source: AIMA online site. \hfill (6 points)}
Consider a vocabulary with only four propositions, \(A\), \(B\), \(C\), and
\(D\).  How many models are there for the following sentences?
\begin{enumerate}
\item \(B\lor C\).
\item \(\lnot A\lor \lnot B \lor \lnot C \lor \lnot D\).
\item \((A\implies B) \land A \land \lnot B \land C \land D\).
\end{enumerate}
\ig{
Note that $A \Leftrightarrow B  \Leftrightarrow C$ is equivalent to 
$A \Leftrightarrow B $ and $B \Leftrightarrow C$.}



\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{Chapter 7, Exercise 12, Source: AIMA online site. \hfill (16 points)} 
Decide whether each of the following sentences is valid,
unsatisfiable, or neither.  Verify your decisions using truth tables
or the equivalence rules of Figure 7.11, Page 223).
%%<<consider some new ones]]
\begin{enumerate}
\item \({Smoke} \implies {Smoke}\)
\item \({Smoke} \implies {Fire}\)
\item \(({Smoke} \implies {Fire}) \implies (\lnot {Smoke} \implies \lnot {Fire})\)
\item \({Smoke} \lor {Fire} \lor \lnot {Fire}\)
\item \((({Smoke} \land {Heat}) \implies {Fire}) 
        \Leftrightarrow (({Smoke} \implies {Fire}) \lor ({Heat} \implies {Fire}))\)
\item \({Big} \lor {Dumb} \lor ({Big} \implies {Dumb})\)
\item \(({Big} \land {Dumb}) \lor \lnot {Dumb}\)
\end{enumerate}


\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{Chapter 7, Exercise 28, Source: AIMA online site. \hfill (18 points + 20 bonus)}

Parts  1, 2, and 3 below are required. Parts 4, 5, and 6 are bonus.

Minesweeper, the well-known computer game, is closely related to the
wumpus world. A minesweeper world is a rectangular grid
of \(N\) squares with \(M\) invisible mines scattered among them.
Any square may be probed by the agent; instant death follows if a mine
is probed. Minesweeper indicates the
presence of mines by revealing, in each probed square, the {\em
number} of mines that are directly or diagonally adjacent.
The goal is to  probe every unmined square.
\begin{enumerate}

\item (Required) Let \(X_{i,j}\) be true iff square \([i,j]\) contains a mine.
Write down the assertion that exactly two mines are adjacent to
[1,1] as a sentence involving some logical combination of \(X_{i,j}\) propositions. 
Where [1,1] is a corner adjacent to cells: [1,2], [2,2], and [2,1].

\item (Required) Generalize your assertion from (1)
 by explaining how to construct a CNF sentence
asserting that \(k\) of \(n\) neighbors contain mines.

\item (Required) Explain precisely how an agent can use DPLL to prove
that a given square does (or does not) contain a mine, ignoring the
global constraint that there are exactly \(M\) mines in all.

\item (Bonus) Suppose that the global constraint is constructed
from your method from part (2). How does the number of clauses
depend on \(M\) and \(N\)? Suggest a way to modify DPLL so that
the global constraint does not need to be represented explicitly.

\item (Bonus) Are any conclusions derived by the method in part (3)
altered or invalidated when the global constraint is taken into account?

\item (Bonus) Give examples of configurations of probe values that induce {\em
long-range dependencies} such that the contents of a
given unprobed square would give information about the contents of a
far-distant square. ({\em Hint}: consider an \(N\times 1\) board.)
\end{enumerate}


\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}


