15.13 Exercises ‣ Chapter 15 Individuals and Relations ‣ Artificial Intelligence: Foundations of Computational Agents, 3rd Edition

Consider a domain with two individuals (✂ and ☎), two predicate symbols ( $p$ and $q$ ), and three constants ( $a$ , $b$ , and $c$ ). The knowledge base $K B$ is defined by

p(X)\leftarrow\mbox{}q(X).

q(a).

(a)

Give one interpretation that is a model of $K B$ .
(b)

Give one interpretation that is not a model of $K B$ .
(c)

How many interpretations are there? Give a brief justification for your answer.
(d)

How many of these interpretations are models of $K B$ ? Give a brief justification for your answer.

Suppose a language has constant symbols $a$ , $b$ , and $c$ ; predicate symbols $p$ and $q$ ; and no function symbols. The following knowledge bases are built from this language:

\begin{array}[]{l|l|l}KB_{1}&KB_{2}&KB_{3}\\ \hline\cr p(a).&p(X)\leftarrow\mbox{}q(X).&p(X)\leftarrow\mbox{}q(X).\\ &&p(a).~~~~~~~q(b).\end{array}

Consider possible interpretations for this language of the form $I=\left<D,\pi,\phi\right>$ , where $D=\{$ ✂, ☎, ✈, ✎ $\}$ .

(a)

How many interpretations with the four domain elements exist for our simple language? Give a brief justification for your answer. [Hint: Determine the number of possible assignments $\phi$ for the constant symbols. Consider how many extensions predicates $p$ and $q$ can have to determine how many assignments $\pi$ exist.] Do not try to enumerate all possible interpretations.
(b)

Of the interpretations outlined above, how many are models of $KB_{1}$ ? Give a brief justification for your answer.
(c)

Of the interpretations outlined above, how many are models of $KB_{2}$ ? Give a brief justification for your answer.
(d)

Of the interpretations outlined above, how many are models of $KB_{3}$ ? Give a brief justification for your answer.

Consider the following knowledge base:

\begin{array}[]{lll}{r(a).}&{r(e).}&{p(c).}\\ {q(b).}&{s(a,b).}&{s(d,b).}\\ {s(e,d).}&{p(X)\leftarrow\mbox{}q(X)\wedge\mbox{}r(X).}&{q(X)\leftarrow\mbox{}% s(X,Y)\wedge\mbox{}q(Y).}\end{array}

Show the set of ground atomic consequences derivable from this knowledge base. Use the bottom-up proof procedure assuming, at each iteration, the first applicable clause is selected in the order shown. Furthermore, applicable constant substitutions are chosen in “alphabetic order” if more than one applies to a given clause; for example, if $X/a$ and $X/b$ are both applicable for a clause at some iteration, derive $q(a)$ first. In what order are consequences derived?

Consider the following knowledge base:

\begin{array}[]{l}\begin{array}[]{lll}{has\_access(X,library)\leftarrow\mbox{}% student(X).}\\ {has\_access(X,library)\leftarrow\mbox{}faculty(X).}\\ {has\_access(X,library)\leftarrow\mbox{}parent(Y,X)\wedge\mbox{}has\_access(Y,% library).}\\ {has\_access(X,office)\leftarrow\mbox{}has\_keys(X).}\end{array}\\ \begin{array}[]{lll}{faculty(diane).}&{faculty(ming).}&{student(william).}\\ {student(mary).}&{parent(diane,karen).}&{parent(diane,robyn).}\\ {parent(susan,sarah).}&{parent(sarah,ariel).}&{parent(karen,chelsey).}\\ {parent(karen,todd).}\end{array}\end{array}

(a)

Provide an SLD derivation of the query $has\_access(todd,library)$ , similar to Figure 15.6.
(b)

The query $has\_access(mary,library)$ has two SLD derivations. Give both, but do not show the clauses chosen or the substitutions.
(c)

Is there a derivation for $has\_access(ariel,library)$ ? Explain why, or why not.
(d)

Explain why the set of answers to the query $has\_access(X,office)$ is empty.
(e)

Suppose the following clause is added to the knowledge base:

$has\_keys(X)\leftarrow\mbox{}faculty(X).$

What are the answers to the query $has\_access(X,office)$ ?

What is the result of the following applications of substitutions?

(a)

$f(A,X,Y,X,Y)\{A/X,Z/b,Y/c\}.$
(b)

$yes(F,L)\leftarrow append(F,c(L,nil),c(l,c(i,c(s,c(t,nil)))))$
$\{F/c(l,X_{1}),Y_{1}/c(L,nil),A_{1}/l,Z_{1}/c(i,c(s,c(t,nil)))\}.$
(c)

$append(c(A_{1},X_{1}),Y_{1},c(A_{1},Z_{1}))\leftarrow append(X_{1},Y_{1},Z_{1})$
$\{F/c(l,X_{1}),Y_{1}/c(L,nil),A_{1}/l,Z_{1}/c(i,c(s,c(t,nil)))\}.$

Give a most general unifier of the following pairs of expressions:

(a)

$p(f(X),g(g(b)))$ and $p(Z,g(Y))$
(b)

$g(f(X),r(X),t)$ and $g(W,r(Q),Q)$
(c)

$bar(val(X,bb),Z)$ and $bar(P,P)$

For each of the following pairs of atoms, either give a most general unifier or explain why one does not exist:

(a)

${p(X,Y,a,b,W)}$ and ${p(E,c,F,G,F)}$
(b)

${p(Y,a,b,Y)}$ and ${p(c,F,G,F)}$
(c)

$foo(Z,[a,z|X],X)$ and $foo([a,m|W],W,[i,n,g])$
(d)

${ap(F0,c(b,c(B0,L0)),c(a,c(b,c(a,emp))))}$ and ${ap(c(H1,T1),L1,c(H1,R1))}$ .

List all of the ground atomic logical consequences of the following knowledge base:

\begin{array}[]{lll}{q(Y)\leftarrow\mbox{}s(Y,Z)\wedge\mbox{}r(Z).}&{p(X)% \leftarrow\mbox{}q(f(X)).}&{s(f(a),b).}\\ {s(f(b),b).}&{s(c,b).}&{r(b).}\end{array}

Consider the following logic program:

rd(cons(H,cons(H,T)),T).

rd(cons(H,T),cons(H,R))\leftarrow rd(T,R).

Give a top-down derivation, showing all substitutions for the query

\mbox{{ask}~}~rd(cons(a,cons(cons(a,X),cons(B,cons(c,Z)))),W).

What is the answer corresponding to this derivation?

Is there a second answer? If yes, show the derivation; if not, explain why.

Consider the following logic program:

ap(emp,L,L).

ap(c(H,T),L,c(H,R))\leftarrow\mbox{}ap(T,L,R).

adj(A,B,L)\leftarrow\mbox{}ap(F,c(A,c(B,E)),L).

(a)

Give a top-down derivation (including all substitutions) for one answer to the query

$\mbox{{ask}~}~adj(b,Y,c(a,c(b,c(b,c(a,emp))))).$
(b)

Are there any other answers? If so, explain where a different choice could be made in the derivation in the previous answer, and continue the derivation, showing another answer. If there are no other answers, explain why not.

[You are meant to do this exercise as if you were a computer, without knowing what the symbols mean. If you want to give a meaning to this program, you could read $a p$ as $a p p e n d$ , $c$ as $c o n s$ , $e m p$ as $e m p t y$ , and $a d j$ as $a d j a c e n t$ .]

The aim of this question is to get practice writing simple logic programs.

(a)

Write a relation $remove(E,L,R)$ that is true if $R$ is the list resulting from removing one instance of $E$ from list $L$ . The relation is false if $E$ is not a member of $L$ .

(b)

Give all of the answers to the following queries:

\mbox{ask }remove(a,[b,a,d,a],R).

\mbox{ask }remove(E,[b,a,d,a],R).

\mbox{ask }remove(E,L,[b,a,d]).

\mbox{ask }remove(p(X),[a,p(a),p(p(a)),p(p(p(a)))],R).

(c)

Write a relation $subsequence(L1,L2)$ that is true if list $L1$ contains a subset of the elements of $L2$ in the same order.

(d)

How many different proofs are there for each of the following queries:

\mbox{ask }subsequence([a,d],[b,a,d,a]).

\mbox{ask }subsequence([b,a],[b,a,d,a]).

\mbox{ask }subsequence([X,Y],[b,a,d,a]).

\mbox{ask }subsequence(S,[b,a,d,a]).

Explain why there are that many.

In this question, you are to write a definite-clause knowledge base for the design of custom video presentations.

Assume that the video is annotated using the relation

segment(SegId,Duration,Covers)

where $S e g I d$ is an identifier for the segment. (In a real application this will be enough information to extract the video segment.) $D u r a t i o n$ is the running time of the segment (in seconds). $C o v e r s$ is a list of topics covered by the video segment. An example of a video annotation is the database

segment(seg0,10,[welcome]).

segment(seg1,30,[skiing,views]).

segment(seg2,50,[welcome,artificial\_intelligence,robots]).

segment(seg3,40,[graphics,dragons]).

segment(seg4,50,[skiing,robots]).

A presentation is a sequence of segments. Represent a presentation by a list of segment identifiers.

(a)

Axiomatize a predicate

presentation(MustCover,Maxtime,Segments)

that is true if $S e g m e n t s$ is a presentation whose total running time is less than or equal to $M a x t i m e$ seconds, such that all of the topics in the list $M u s t C o v e r$ are covered by a segment in the presentation. The aim of this predicate is to design presentations that cover a certain number of topics within a time limit.

For example, the query

\mbox{{ask}~}~presentation([welcome,skiing,robots],90,Segs)

should return at least the following two answers (perhaps with the segments in some other order):

presentation([welcome,skiing,robots],90,[seg0,seg4])

presentation([welcome,skiing,robots],90,[seg2,seg1]).

Give the intended interpretation of all symbols used and demonstrate that you have tested your axiomatization (including finding all answers to your query) in AIPython (aipython.org) or Prolog. Explain briefly why each answer is an answer.

(b)

Assuming you have a good user interface and a way to actually view the presentations, list three things that the preceding program does not do that you may want in such a presentation system. (There is no correct answer for this part. You must be creative to get full marks.)

The extra arguments in a definite-clause grammar makes it strictly more powerful than a context-free grammar. The language $\{a^{n}b^{n}c^{n}\mid n\geq 0\}$ , which consists of sentences that are made up of a number of $a$ s, followed by the same number of $b$ s followed by the same number of $c$ s cannot be defined with a context-free grammar. Define this language using a definite clause grammar. [Hint: Define a predicate $c o p i e s$ for a non-terminal that creates $n$ copies of one of its arguments, and represent numbers using $0$ for zero and $s(N)$ for the numbers after $n$ .]

Construct a knowledge base and a dictionary based on Figure 15.12 to answer geographical questions such as that given in Figure 1.3. For each query, either show how it can be answered or explain why it is difficult to answer given the tools presented in this chapter.

Consider what would happen in Example 15.44 if $empty\_course$ had been defined as

empty\_course(C)\leftarrow\mbox{}course(C)\wedge\mbox{}\mbox{$\sim$}enrolled(S% ,C).

Suppose the rest of the knowledge base is

\begin{array}[]{lll}{course(cs422).}&{course(cs486).}&{course(cs987).}\\ {enrolled(huan,cs422).}&{enrolled(sally,cs486).}\end{array}

(a)

What is Clark’s completion of the clause for $empty\_course$ ?
(b)

What is a counter example to the soundness of the completion? Give an instance of the clause for which the body is true and the head is false.
(c)

What does an implementation with negation as failure (e.g., Prolog) give? Compare with ${empty\_course(C)\leftarrow\mbox{}\mbox{$\sim$}enrolled(S,C)\wedge\mbox{}% course(C).}$

Artificial
Intelligence 3E

15.13 Exercises

Exercise 15.1.

Exercise 15.2.

Exercise 15.3.

Exercise 15.4.

Exercise 15.5.

Exercise 15.6.

Exercise 15.7.

Exercise 15.8.

Exercise 15.9.

Exercise 15.10.

Exercise 15.11.

Exercise 15.12.

Exercise 15.13.

Exercise 15.14.

Exercise 15.15.

Artificial Intelligence 3E