13.11 Exercises‣ Chapter 13 Individuals and Relations ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition

1.

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

	$\displaystyle{p(X)\leftarrow\mbox{}q(X).}$
	$\displaystyle{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.

2.

Consider the language that contains the constant symbols $a$ , $b$ , and $c$ ; the predicate symbols $p$ and $q$ ; and no function symbols. We have the following knowledge bases built from this language:

	$\displaystyle KB_{1}=\{$	$\displaystyle p(a)\>\}$
	$\displaystyle KB_{2}=\{$	$\displaystyle p(X)\leftarrow\mbox{}q(X)\>\}$
	$\displaystyle KB_{3}=\{$	$\displaystyle p(X)\leftarrow\mbox{}q(X),$
		$\displaystyle p(a),$
		$\displaystyle q(b)\>\}.$

Now 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: Consider how many possible assignments $\phi$ exist for the constant symbols, and 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.

3.

Consider the following knowledge base:

	$\displaystyle{r(a).}$
	$\displaystyle{r(e).}$
	$\displaystyle{p(c).}$
	$\displaystyle{q(b).}$
	$\displaystyle{s(a,b).}$
	$\displaystyle{s(d,b).}$
	$\displaystyle{s(e,d).}$
	$\displaystyle{p(X)\leftarrow\mbox{}q(X)\wedge\mbox{}r(X).}$
	$\displaystyle{q(X)\leftarrow\mbox{}s(X,Y)\wedge\mbox{}q(Y).}$

Show the set of ground atomic consequences derivable from this knowledge base. Assume that a bottom-up proof procedure is used and that 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?

4.

In Example 13.23, the algorithm fortuitously chose $imm\_west(r109,r111)$ as the clause to resolve against. What would have happened if another clause had been chosen? Show the sequence of resolutions that arise, and either show a different answer or give a generalized answer clause that cannot resolve with any clause in the knowledge base.

5.

In Example 13.23, we always selected the leftmost conjunct to resolve on. Is there a selection rule (a selection of which conjunct in the query to resolve against) that would have resulted in only one choice for this example? Give a general rule that – for this example, at least – results in fewer failing branches being made. Give an example where your rule does not work.

6.

In a manner similar to Example 13.23, show derivations of the following queries:

(a)

$\mbox{{ask}~{}}~{}two\_doors\_east(r107,R).$
(b)

$\mbox{{ask}~{}}~{}next\_door(R,r107).$
(c)

$\mbox{{ask}~{}}~{}west(R,r107).$
(d)

$\mbox{{ask}~{}}~{}west(r107,R).$

Give all answers for each query.

7.

Consider the following knowledge base:

	$\displaystyle{has\_access(X,library)\leftarrow\mbox{}student(X).}$
	$\displaystyle{has\_access(X,library)\leftarrow\mbox{}faculty(X).}$
	$\displaystyle{has\_access(X,library)\leftarrow\mbox{}has\_access(Y,library)% \wedge\mbox{}parent(Y,X).}$
	$\displaystyle{has\_access(X,office)\leftarrow\mbox{}has\_keys(X).}$
	$\displaystyle{faculty(diane).}$
	$\displaystyle{faculty(ming).}$
	$\displaystyle{student(william).}$
	$\displaystyle{student(mary).}$
	$\displaystyle{parent(diane,karen).}$
	$\displaystyle{parent(diane,robyn).}$
	$\displaystyle{parent(susan,sarah).}$
	$\displaystyle{parent(sarah,ariel).}$
	$\displaystyle{parent(karen,mary).}$
	$\displaystyle{parent(karen,todd).}$

(a)

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

The query $has\_access(mary,library)$ has two SLD derivations. Give both of them.
(c)

Does there exist an SLD 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:

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

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

8.

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)))\}.$

9.

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)$

10.

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)}$
${p(E,c,F,G,F)}$
(b)

${p(X,Y,Y)}$
${p(E,E,F)}$
(c)

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

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

11.

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

	$\displaystyle{q(Y)\leftarrow\mbox{}s(Y,Z)\wedge\mbox{}r(Z).}$
	$\displaystyle{p(X)\leftarrow\mbox{}q(f(X)).}$
	$\displaystyle{s(f(a),b).}$
	$\displaystyle{s(f(b),b).}$
	$\displaystyle{s(c,b).}$
	$\displaystyle{r(b).}$

12.

Consider the following logic program:

	$\displaystyle{f(empty,X,X).}$
	$\displaystyle{f(cons(X,Y),W,Z)\leftarrow}$
	$\displaystyle\ \ \ \ {f(Y,W,cons(X,Z)).}$

Give each top-down derivation, showing substitutions (as in Example 13.32) for the query

\displaystyle{\mbox{{ask}~{}}~{}f(cons(a,cons(b,cons(c,empty))),L,empty).}

What are all of the answers?

13.

Consider the following logic program:

	$\displaystyle{rd(cons(H,cons(H,T)),T).}$
	$\displaystyle{rd(cons(H,T),cons(H,R))\leftarrow}$
	$\displaystyle\ \ \ \ {rd(T,R).}$

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

\displaystyle{\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.

14.

Consider the following logic program:

	$\displaystyle{ap(emp,L,L).}$
	$\displaystyle{ap(c(H,T),L,c(H,R))\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {ap(T,L,R).}$
	$\displaystyle{adj(A,B,L)\leftarrow\mbox{}}$
	$\displaystyle\ \ \ \ {ap(F,c(A,c(B,E)),L).}$

(a)

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

$\displaystyle{\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$ .]

15.

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:

	$\displaystyle{\mbox{ask }remove(a,[b,a,d,a],R).}$
	$\displaystyle{\mbox{ask }remove(E,[b,a,d,a],R).}$
	$\displaystyle{\mbox{ask }remove(E,L,[b,a,d]).}$
	$\displaystyle{\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:

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

Explain why there are that many.

16.

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

	$\displaystyle{segment(seg0,10,[welcome]).}$
	$\displaystyle{segment(seg1,30,[skiing,views]).}$
	$\displaystyle{segment(seg2,50,[welcome,artificial\_intelligence,robots]).}$
	$\displaystyle{segment(seg3,40,[graphics,dragons]).}$
	$\displaystyle{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

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

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

	$\displaystyle{presentation([welcome,skiing,robots],90,[seg0,seg4])}$
	$\displaystyle{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 AILog 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.)

17.

Construct a knowledge base and a dictionary based on Figure 13.13 to answer geographical questions such as that given in Figure 1.2. 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.

Artificial Intelligence 2E

13.11 Exercises

Artificial
Intelligence 2E