\newcommand{\ig}[1]{}
\documentclass[12pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{shortvrb}
\usepackage{epsfig}
\usepackage{hyperref}
\usepackage{soul}

\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 8}
\end{center}

\begin{description}
\item[Assigned on:] Monday, Nov 20, 2023 {\em tentative}
\item[Due:] Monday, Dec 4, 2023 {\em tentative}
\end{description}

\noindent This is a pen-and-paper homework, to be returned in class or with web handin.\\
\noindent The homework is worth 130 points (+25 bonus points).  \\

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

\hrule
%\vspace{\baselineskip}

\vspace{\baselineskip}

\tableofcontents

\section{Researching Description Logic \hfill{\bf (Bonus 25 points)}}
Description Logic is a cornerstone of the Semantic Web technology.  In
this question, you are asked to research Description Logic {\em beyond
what is in your textbook}.  Write a two-page (typed) structured
summary about DL addressing whatever aspects you find meaningful and
interesting.  Below is a list of ideas {\em you may want to include},
they are mere suggestions.  Make sure you cite all your references.
\begin{enumerate}
\item 
What is the goal of DL? 

\item
To the extent possible, explain/state the syntax and semantics of DL.

\item 
How does DL relate to other types of Logic that we may or may not have
studies? 

\item
Explain some proof techniques used for DL and give their complexity.

\item 
Briefly describe the history/evolution of DL.
 
\item 
Discuss and compare various implementations of DL.

\item
Investigate the industrial impact of DL: list practical systems
implements some version of DL; are they public domain; have they
generated economic growth/benefit, etc.

\end{enumerate}

\section {Algorithms for Propositional Logic \hfill{\bf  (20 points)}}

Consider the following algorithms:
\begin{enumerate}
\item
{\sc TT-entails?}, AIMA Figure~7.10  page 221.

\item
{\sc PL-Resolution}, AIMA Figure~7.13  page 228.

\item
{\sc PL-FC-entails?}, AIMA Figure~7.15  page 231.

\item
{\sc DPLL-Satisfiable?}, AIMA Figure~7.17  page 234.


\item
{\sc WalkSAT}, AIMA Figure~7.18  page 235.
\end{enumerate}

For each of the above algorithms, carefully study the algorithm and
explain how it operates by 
\begin{itemize}
\item Clearly stating the input
\item Providing the representation on which it operates
\item Explaining when and why the algorithm stops
\item Stating what mechanism the algorithm implements (for example by relating it to
a known theorem.)
\end{itemize}
\hfill{(4 points for each algorithm)}


\section {Using the inference rules for logic \hfill{\bf (10 points)}}
prove that ``$\exists\, x\,  Z(x)$
follows from the givens.''  Be sure to justify your steps by stating
the inference rule used, along with the previous line(s) to which it
was applied and the unifications used. 
\begin{enumerate}
\item \hspace{1cm}
$P(1)$ \hfill{given}

\item \hspace{1cm}
$W(1) \wedge W(2) \wedge W(3)$ \hfill{given}

\item \hspace{1cm}
$\forall\, x\, [P(x) \Rightarrow \neg R(x)]$ \hfill{given}

\item \hspace{1cm}
$\forall\, x\, [Q(x) \vee R(x)]$ \hfill{given}

\item \hspace{1cm}
$\forall\, x\, [(Q(x) \wedge W(x)) \Rightarrow Z(x)]$ \hfill{given}

\end{enumerate}
\vspace{0.2cm}


\section {Chapter 8, Exercise 4 \hfill{\bf (2 points)}}
Source: AIMA online site.\\

Write down a logical sentence such that every world in which it is
true contains exactly one object.
\section {Chapter 8, Exercise 10 \hfill{\bf (20 points)}}
Source: AIMA online site. \\
This exercise uses the function \(\mathit{MapColor}\) and predicates \(\mathit{In}(x,y)\), \(\mathit{Borders}(x,y)\),  and \(\mathit{Country}(x)\), whose arguments are geographical regions,
along with constant symbols for various regions.  In each of the following we give an English 
sentence and a number of candidate logical expressions. For each of
the logical expressions, state whether it
(1) correctly expresses the English sentence; (2) is
syntactically invalid and therefore meaningless; or (3) is syntactically valid
but does not express the meaning of the English sentence. 
\begin{enumerate}
\item Paris and Marseilles are both in France. 
\begin{enumerate}
\item \(\mathit{In}(\mathit{Paris} \land \mathit{Marseilles}, \mathit{France})\).
\item \(\mathit{In}(\mathit{Paris},\mathit{France}) \land \mathit{In}(\mathit{Marseilles},\mathit{France})\).
\item \(\mathit{In}(\mathit{Paris},\mathit{France}) \lor \mathit{In}(\mathit{Marseilles},\mathit{France})\).
\end{enumerate}

\item There is a country that borders both Iraq and Pakistan.
\begin{enumerate}
\item \(\exists\, c\,  \mathit{Country}(c) \land \mathit{Border}(c,\mathit{Iraq}) \land \mathit{Border}(c,\mathit{Pakistan})\).
\item \(\exists\, c\,  \mathit{Country}(c) \Rightarrow [\mathit{Border}(c,\mathit{Iraq}) \land \mathit{Border}(c,\mathit{Pakistan})]\).
\item \(\exists\, c\,  \mathit{Country}(c) \Rightarrow [\mathit{Border}(c,\mathit{Iraq}) \land \mathit{Border}(c,\mathit{Pakistan})]\).
\item \(\exists\, c\, \mathit{Border}(\mathit{Country}(c),\mathit{Iraq} \land \mathit{Pakistan})\).
\end{enumerate}

\item All countries that border Ecuador are in South America.
\begin{enumerate}
\item \(\forall\,{c}\,  Country(c) \land \mathit{Border}(c,\mathit{Ecuador}) \Rightarrow \mathit{In}(c,\mathit{SouthAmerica})\).
\item \(\forall\,{c}\,  \mathit{Country}(c) \Rightarrow [\mathit{Border}(c,\mathit{Ecuador}) \Rightarrow \mathit{In}(c,\mathit{SouthAmerica})]\).
\item \(\forall\,{c}\,  [\mathit{Country}(c) \Rightarrow \mathit{Border}(c,\mathit{Ecuador})] \Rightarrow \mathit{In}(c,\mathit{SouthAmerica})\).
\item \(\forall\,{c}\,  Country(c) \land \mathit{Border}(c,\mathit{Ecuador}) \land \mathit{In}(c,\mathit{SouthAmerica})\).
\end{enumerate}

\item No region in South America borders any region in Europe.
\begin{enumerate}
\item \(\lnot [\exists\,{c,d}\,   \mathit{In}(c,\mathit{SouthAmerica}) \land \mathit{In}(d,\mathit{Europe}) \land \mathit{Borders}(c,d)]\).
\item \(\forall\,{c,d}\,  [\mathit{In}(c,\mathit{SouthAmerica}) \land \mathit{In}(d,\mathit{Europe})] \Rightarrow \lnot \mathit{Borders}(c,d)]\).
\item \(\lnot \forall\,{c}\,  \mathit{In}(c,\mathit{SouthAmerica}) \Rightarrow \exists\,{d}\,  \mathit{In}(d,\mathit{Europe}) \land 
\lnot \mathit{Borders}(c,d)\).
\item \(\forall\,{c}\, \mathit{In}(c,\mathit{SouthAmerica}) \Rightarrow \forall\,{d}\, \mathit{In}(d,\mathit{Europe}) \Rightarrow \lnot \mathit{Borders}(c,d)\). 
\end{enumerate}

\item No two adjacent countries have the same map color.
\begin{enumerate}

\item \(\forall\,{x,y}\, \lnot \mathit{Country}(x) \lor \lnot
  \mathit{Country}(y) \lor \lnot \mathit{Borders}(x,y) \lor \lnot
  (\mathit{MapColor}(x) = \mathit{MapColor}(y))\).

\item \(\forall\,{x,y}\, (\mathit{Country}(x) \land \mathit{Country}(y)
  \land \mathit{Borders}(x,y) \land \lnot(x=y)) \Rightarrow \lnot
  (\mathit{MapColor}(x) = \mathit{MapColor}(y))\).

\item \(\forall\,{x,y}\, \mathit{Country}(x) \land \mathit{Country}(y)
  \land \mathit{Borders}(x,y) \land \lnot (\mathit{MapColor}(x) =
  \mathit{MapColor}(y))\).

\item \(\forall\,{x,y}\, (\mathit{Country}(x) \land \mathit{Country}(y)
  \land \mathit{Borders}(x,y) ) \Rightarrow \mathit{MapColor}(x\neq
  y)\).
\end{enumerate}\end{enumerate}
\section {Chapter 8, Exercise 30 \hfill{\bf (12 points)}}
Source: AIMA online site.\\
Represent the following sentences in first-order logic, using a consistent
vocabulary (which you must define):
\begin{enumerate}
\item Some students took French in spring 2001.
\item Every student who takes French passes it.
\item Only one student took Greek in spring 2001.
\item The best score in Greek is always higher than the best score in French.
\item Every person who buys a policy is smart.
\item No person buys an expensive policy.
\item There is an agent who sells policies only to people who are not insured.
\item There is a barber who shaves all men in town who do not shave themselves.
\item A person born in the UK, each of whose parents is a UK citizen or a UK resident, is a UK citizen by birth.
\item A person born outside the UK, one of whose parents is a UK citizen by birth, is a UK citizen
by descent.
\item Politicians can fool some of the people all of the time, and they can fool
all of the people some of the time, but they can't fool all of the people all
of the time.
\item All Greeks speak the same language. (Use \(\mathit{Speaks}(x,l)\) to mean that person \(x\)
speaks language \(l\).)
\end{enumerate}

\section {Axioms in FOL (Adapted from AIMA, first edition) \hfill{\bf (15 points)}}

Using the following:

\begin{center} |Child(x,y)|, |Sibling(x,y)|, |Female(x)|, |Male(x)|, and |Spouse(x, y)| \end{center}

\begin{itemize}
\item (10 points) Write axioms describing the predicates: |GrandChild|,
|GreatGrandParent|, |Brother|, |Sister|, |Daughter|, |Son|, |Aunt|,
|Uncle|, |BrotherInLaw|, |SisterInLaw|, and |FirstCousin|.  We want
these axioms to be definitions, so use $\Leftrightarrow$ instead of
$\Rightarrow$.
\item (5 points) Knowing that a second cousin is a child of one's parent 
 first cousin, write the definition of a $N^{th}$|-cousin|, as a
 recursive expression in terms of the predicates defined above.  Hint:
 Let $N^{th}$|-cousin| be a ternary predicate, that takes as input
 $n$, and two persons $p_1$ and $p_2$.
\end{itemize}



\section {Chapter 9, Exercise 3 \hfill{\bf {(3 points)}}}
Source: AIMA online site. \\
Suppose a knowledge base contains just one sentence, \(\exists\,\,x\, \mathit{AsHighAs}(x,\mathit{Everest})\).
Which of the following are legitimate results of applying Existential Instantiation?
\begin{enumerate}
\item \(\mathit{AsHighAs}(\mathit{Everest},\mathit{Everest})\).
\item \(\mathit{AsHighAs}(\mathit{Kilimanjaro},\mathit{Everest})\).
\item \(\mathit{AsHighAs}(\mathit{Kilimanjaro},\mathit{Everest}) \land \mathit{AsHighAs}(\mathit{BenNevis},\mathit{Everest})\) \\
(after two applications).
\end{enumerate}
\section {Chapter 9, Exercise 4 \hfill{\bf {(4 points)}}}
Source: AIMA online site. \\
For each pair of atomic sentences,
give the most\index{unifier, most general (MGU)} 
\index{most general unifier (MGU)}\index{MGU (most general unifier)} general unifier if it exists:
\begin{enumerate}
\item \(P(A,B,B)\), \(P(x,y,z)\).
\item \(Q(y,G(A,B))\), \(Q(G(x,x),y)\).
\item \(\mathit{Older}(\mathit{Father}(y),y)\), \(\mathit{Older}(\mathit{Father}(x),\mathit{John})\).
\item \(\mathit{Knows}(\mathit{Father}(y),y)\), \(\mathit{Knows}(x,x)\).
\end{enumerate}
\section {Chapter 9, Exercise 7 \hfill{\bf {(12 points)}}}
Source: AIMA online site. \\
Write down logical representations for the following
sentences, suitable for use with Generalized Modus\index{Modus Ponens} Ponens:
\begin{enumerate}
\item Horses, cows, and pigs are mammals.
\item An offspring of a horse is a horse.
\item Bluebeard is a horse.
\item Bluebeard is Charlie's parent.
\item Offspring and parent are inverse relations.
\item Every mammal has a parent.
\end{enumerate}
\section {Chapter 9, Exercise 16 \hfill{\bf {(12 points)}}}
Source: AIMA online site.\\
In this exercise,  use the sentences you wrote
in Chapter 9, Exercise 7 (Previous Question) to answer a question by using a
backward-chaining algorithm.
\begin{enumerate}
\item
Draw the proof tree generated by an exhaustive backward-chaining
algorithm for the query \(\exists\, h\, \mathit{Horse}(h)\), where clauses are matched
in the order given.
\item
What do you notice about this domain?
\item 
How many solutions for \(h\) actually follow from your sentences?
\item 
  Can you think of a way to find all of them? ({\em Hint}: For this
  question, it is usefull to check the following paper
  \href{https://cse.unl.edu/~choueiry/Documents/Smith-Genesereth-AIJ86.pdf}{
Smith, D.E., Genesereth, M.R., and Ginsberg, M.L. (1986).  {\em Controlling
recursive inference.} Artificial Intelligence, Volume 30(3), pages
343--389.})
\end{enumerate}

\section {First-Order Logic \hfill{\bf (20 points)}}

Consider the following axioms:
\begin{enumerate}
\item
Anyone who rides any Harley is a rough character.
\item
Every biker rides [something that is] either a Harley or a BMW.
\item
Anyone who rides any BMW is a yuppie.
\item
Every yuppie is a lawyer.
\item
Any nice girl does not date anyone who is a rough character.
\item
Mary is a nice girl, and John is a biker.
\item
(Conclusion) If John is not a lawyer, then Mary does not date John.
\end{enumerate}
\begin{itemize}
\item
Choose appropriate predicates to write the above axioms in first-order
logic, clearly indicating the arguments and arity of each predicate:
\hfill{(2 points)}

\item 
Write each of the above axioms in first-order logic.  Use scratch
paper if necessary, and {\em neatly\/} report your results below. \hfill{(10
points)}
\begin{enumerate}
\item
\mbox{}
\vfill
\item
\mbox{} 
\vfill
\item
\mbox{}
\vfill
\item
\mbox{}
\vfill
\item
\mbox{}
\vfill
\item
\mbox{}
\vfill
\item
\mbox{}
\vfill
\end{enumerate}

\item 
Transform each of the above sentences into a conjunctive normal form.
Clearly state the Skolem functions and clearly number the statements.
\hfill{(4 points)}

\item
Establish the conclusion using the axioms by applying refutation
resolution.  Clearly show the variable bindings at each step and
clearly number the statements.

\hfill{(4 points)}

Negation of conclusion:

\end{itemize}

\end{document}

