Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).

12.11 Exercises

Exercise 12.1:
Consider a domain with two individuals (✄ and ☎), two predicate symbols (p and q), and three constants (a, b, and c). The knowledge base KB is defined by
p(X) ←q(X).
q(a).
  1. Give one interpretation that is a model of KB.
  2. Give one interpretation that is not a model of KB.
  3. How many interpretations are there? Give a brief justification for your answer.
  4. How many of these interpretations are models of KB? Give a brief justification for your answer.
Exercise 12.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:
KB_1 = {
p(a)}.

KB_2 = {
p(X) ←q(X)}.

KB_3 = {
p(X) ←q(X),
p(a),
q(b)}.

Now consider possible interpretations for this language of the form I = ⟨D, π, φ⟩, where D={✄, ☎, ✈, ✎}.

  1. 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 φ exist for the constant symbols, and consider how many extensions predicates p and q can have to determine how many assignments π exist.] Do not try to enumerate all possible interpretations.
  2. Of the interpretations outlined above, how many are models of KB1? Give a brief justification for your answer.
  3. Of the interpretations outlined above, how many are models of KB2? Give a brief justification for your answer.
  4. Of the interpretations outlined above, how many are models of KB3? Give a brief justification for your answer.
Exercise 12.3:
Consider the following knowledge base:
r(a).
r(e).
p(c).
q(b).
s(a,b).
s(d,b).
s(e,d).
p(X) ←q(X) ∧r(X).
q(X) ←s(X,Y) ∧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?

Exercise 12.4:
In Example 12.21, 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.
Exercise 12.5:
In Example 12.21, 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.
Exercise 12.6:
In a manner similar to Example 12.21, show derivations of the following queries:
  1. ask two_doors_east(r107,R).
  2. ask next_door(R,r107).
  3. ask west(R,r107).
  4. ask west(r107,R).

Give all answers for each query.

Exercise 12.7:
Consider the following knowledge base:
has_access(X,library) ←student(X).
has_access(X,library) ←faculty(X).
has_access(X,library) ←has_access(Y,library) ∧parent(Y,X).
has_access(X,office) ←has_keys(X).
faculty(diane).
faculty(ming).
student(william).
student(mary).
parent(diane,karen).
parent(diane,robyn).
parent(susan,sarah).
parent(sarah,ariel).
parent(karen,mary).
parent(karen,todd).
  1. Provide an SLD derivation of the query ask has_access(todd,library).
  2. The query ask has_access(mary,library) has two SLD derivations. Give both of them.
  3. Does there exist an SLD derivation for ask has_access(ariel,library)? Explain why or why not.
  4. Explain why the set of answers to the query ask has_access(X,office) is empty.
  5. Suppose following the clause is added to the knowledge base:
    has_keys(X) ←faculty(X).

    What are the answers to the query ask has_access(X,office)?

Exercise 12.8:
What is the result of the following application of substitutions:
  1. f(A,X,Y,X,Y){A/X,Z/b,Y/c}.
  2. yes(F,L)←append(F,c(L,nil),c(l,c(i,c(s,c(t,nil)))))
         1cm{F/c(l,X1), Y1/c(L,nil), A1/l ,Z1/c(i,c(s,c(t,nil)))}.
  3. append(c(A1,X1),Y1,c( A1,Z1))←append(X1,Y1,Z1)
         1cm{F/c(l,X1), Y1/c(L,nil), A1/l ,Z1/c(i,c(s,c(t,nil)))}.
Exercise 12.9:
Give a most general unifier of the following pairs of expressions:
  1. p(f(X), g(g(b))) and p(Z, g(Y))
  2. g(f(X),r(X),t) and g(W,r(Q),Q)
  3. bar(val(X,bb),Z) and bar(P,P)
Exercise 12.10:
For each of the following pairs of atoms, either give a most general unifier or explain why one does not exist:
  1. p(X,Y,a,b,W)
    p(E,c,F,G,F)
  2. p(X,Y,Y)
    p(E,E,F)
  3. p(Y,a,b,Y)
    p(c,F,G,F)
  4. ap(F0,c(b,c(B0,L0)),c(a,c(b,c(b,c(a,emp)))))
    ap(c(H1,T1),L1,c(H1,R1))
Exercise 12.11:
List all of the ground atomic logical consequences of the following knowledge base:
q(Y) ←s(Y,Z) ∧r(Z).
p(X) ←q(f(X)).
s(f(a),b).
s(f(b),b).
s(c,b).
r(b).
Exercise 12.12:
Consider the following logic program:
f(empty,X,X).
f(cons(X,Y),W,Z)←
     f(Y,W,cons(X,Z)).

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

ask f(cons( a,cons(b,cons(c,empty))),L,empty).

What are all of the answers?

Exercise 12.13:
Consider the following logic program:
rd(cons(H,cons(H,T)),T).
rd(cons(H,T),cons(H,R)) ←
     rd(T,R).

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

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.

Exercise 12.14:
Consider the following logic program:
ap(emp,L,L).
ap(c(H,T),L,c(H,R)) ←
      ap(T,L,R).
adj(A,B,L) ←
      ap(F,c(A,c(B,E)),L).
  1. Give a top-down derivation (including all substitutions) for one answer to the query
    ask  adj(b,Y,c(a,c(b,c(b,c(a,emp))))).
  2. 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 would a computer, without knowing what the symbols mean. If you want to give a meaning to this program, you could read ap as append, c as cons, emp as empty, and adj as adjacent.]

Exercise 12.15:
The aim of this question is to get practice writing simple logic programs.
  1. Write a relation remove(E,L,R) that is true if R is the resulting list of removing one instance of E from list L. The relation is false if E is not a member of L.
  2. Give all of the answers to the following queries:
    ask  remove(a,[b,a,d,a],R).
    ask  remove(E,[b,a,d,a],R).
    ask  remove(E,L,[b,a,d]).
    ask  remove(p(X),[a,p(a),p(p(a)),p(p(p(a)))],R).
  3. Write a relation subsequence(L1,L2) that is true if list L1 contains a subset of the elements of L2 in the same order.
  4. How many different proofs are there for each of the following queries:
    ask  subsequence([a,d],[b,a,d,a]).
    ask  subsequence([b,a],[b,a,d,a]).
    ask  subsequence([X,Y],[b,a,d,a]).
    ask  subsequence(S,[b,a,d,a]).

    Explain why there are that many.

Exercise 12.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 SegId is an identifier for the segment. (In a real application this will be enough information to extract the video segment). Duration is the time of the segment (in seconds). Covers 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,computational_intelligence,robots]).
segment(seg3,40,[graphics,dragons]).
segment(seg4,50,[skiing,robots]).

A presentation is a sequence of segments. You will represent a presentation by a list of segment identifiers.

  1. Axiomatize a predicate
    presentation(MustCover, Maxtime, Segments)

    that is true if Segments is a presentation whose total running time is less than or equal to Maxtime seconds, such that all of the topics in the list MustCover 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

    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 AILog or Prolog. Explain briefly why each answer is an answer.

  2. 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).
Exercise 12.17:
Construct a knowledge base and a dictionary [based on Figure 12.11] 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.