13 Individuals and Relations

13.11 Exercises

  1. 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. (a)

      Give one interpretation that is a model of KB.

    2. (b)

      Give one interpretation that is not a model of KB.

    3. (c)

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

    4. (d)

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

  2. 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:

    KB1={ p(a)}
    KB2={ p(X)q(X)}
    KB3={ p(X)q(X),
    p(a),
    q(b)}.

    Now consider possible interpretations for this language of the form I=D,π,ϕ, where D={✢, , ✨, ✮}.

    1. (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 ϕ 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. (b)

      Of the interpretations outlined above, how many are models of KB1? Give a brief justification for your answer.

    3. (c)

      Of the interpretations outlined above, how many are models of KB2? Give a brief justification for your answer.

    4. (d)

      Of the interpretations outlined above, how many are models of KB3? Give a brief justification for your answer.

  3. 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?

  4. 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. 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. 6.

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

    1. (a)

      𝖺𝗌𝗄 two_doors_east(r107,R).

    2. (b)

      𝖺𝗌𝗄 next_door(R,r107).

    3. (c)

      𝖺𝗌𝗄 west(R,r107).

    4. (d)

      𝖺𝗌𝗄 west(r107,R).

    Give all answers for each query.

  7. 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. (a)

      Provide an SLD derivation of the query has_access(todd,library).

    2. (b)

      The query has_access(mary,library) has two SLD derivations. Give both of them.

    3. (c)

      Does there exist an SLD derivation for has_access(ariel,library)? Explain why or why not.

    4. (d)

      Explain why the set of answers to the query has_access(X,office) is empty.

    5. (e)

      Suppose the following clause is added to the knowledge base:

      has_keys(X)faculty(X).

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

  8. 8.

    What is the result of the following applications of substitutions?

    1. (a)

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

    2. (b)

      yes(F,L)append(F,c(L,nil),c(l,c(i,c(s,c(t,nil)))))
               {F/c(l,X1),Y1/c(L,nil),A1/l,Z1/c(i,c(s,c(t,nil)))}.

    3. (c)

      append(c(A1,X1),Y1,c(A1,Z1))append(X1,Y1,Z1)
               {F/c(l,X1),Y1/c(L,nil),A1/l,Z1/c(i,c(s,c(t,nil)))}.

  9. 9.

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

    1. (a)

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

    2. (b)

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

    3. (c)

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

  10. 10.

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

    1. (a)

      p(X,Y,a,b,W)
      p(E,c,F,G,F)

    2. (b)

      p(X,Y,Y)
      p(E,E,F)

    3. (c)

      p(Y,a,b,Y)
      p(c,F,G,F)

    4. (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. 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).
  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 13.32) for the query

    𝖺𝗌𝗄 f(cons(a,cons(b,cons(c,empty))),L,empty).

    What are all of the answers?

  13. 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

    𝖺𝗌𝗄 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. 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. (a)

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

      𝖺𝗌𝗄 adj(b,Y,c(a,c(b,c(b,c(a,emp))))).
    2. (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 ap as append, c as cons, emp as empty, and adj as adjacent.]

  15. 15.

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

    1. (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.

    2. (b)

      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. (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.

    4. (d)

      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.

  16. 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 running 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,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.

    1. (a)

      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

      𝖺𝗌𝗄 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. (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. 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.