CSc 8710 Deductive Databases and Logic Programming
Fall 1998
Solutions to Exam #1
Monday, October 12, 1998
---------------------------------------------------------------------------
1 (a)  member(X,tree(X,_,_).
       member(X,tree(Y,L,_)) :- X < Y, member(X,L).
       member(X,tree(Y,_,R)) :- X > Y, member(X,R).

  (b) insert(X,nil,tree(X,nil,nil)).
      insert(X,tree(X,L,R),tree(X,L,R)).
      insert(X,tree(Y,L,R),tree(Y,L1,R)) :- X < Y, insert(X,L,L1).
      insert(X,tree(Y,L,R),tree(Y,L,R1)) :- X > Y, insert(X,R,R1).

  (c) height(nil,0).
      height(tree(_,L,R),H) :- height(L,H1),
                               height(R,H2),
                               max(H1,H2,H3),
                               H is H3 + 1.
      max(A,B,B) :- A =< B.
      max(A,B,A) :- A > B.
---------------------------------------------------------------------------
2.

?- mystery1([a,b,c,d,e]).
no

?- mystery1([a,b,c,d]).
yes

?- mystery2([a,b,c]).
yes

?- mystery2([a,b]).
no

mystery1(L) iff L has even number of elements
mystery2(L) iff L has odd number of elements

---------------------------------------------------------------------------
3. (a) [[the,Y]|Z] and [[X,hare],[is,here]]

       { X <- the, Y <- hare, Z <- [[is,here]] }

   (b) [golden|T] and [golden,norfolk]

        { T <- [norfolk] }

   (c) [X,Y|Z] and [mary,likes,wine]

       { X <- mary, Y <- likes, Z <- [wine] }

   (d) A(X,3) and A(Y,Y)

        { X <- 3, Y <- 3 }

   (e) [] and [X|Y]

       Do not unify; because [] has zero elements and [X|Y] has at least
       one element.

   (f) [X|[Y|Z]] and [a,b,c,d,e]

       { X <- a, Y <- b, Z <- [c,d,e] }

   (g) append([b],[c,d],L) and append([X|Xs],Ys,[X|Zs])

       { X <- b, Xs <- [], Ys <- [c,d], L <- [b|Zs] }

---------------------------------------------------------------------------
4   (a) answer(D) :- movies(T,D), actors(T,D).
  
    (b) answer(T) :- movies(T,'Kurosawa').
        answer(T) :- plays('Odeon',T,_).

    (c) temp1(D,A) :- movies(_,D), actors(_,A).
        temp2(D,A) :- movies(T,D), actors(T,A).
        temp3(D) :- temp1(D,A), not temp2(D,A).
        answer(D) :- movies(_,D), not temp3(D).

    (d) temp1(A) :- actors(_,A).
        temp2(A) :- movies(T,D), actors(T,A), D <> 'Kurosawa'.
        answer(A) :- temp1(A), not temp2(A).

    (e) AnotwithB(A,B) :- actors(T1,A), actors(_,B), not actors(T1,B).
        answer(A,B) :- actors(_,A), actors(_,B),
                       not AnotwithB(A,B),
                       not AnotwithB(B,A).
---------------------------------------------------------------------------
5  (a) Herbrand universe of P is the set of all constants appearing in P.

   (b) Herbrand base of P is the set of all possible ground atomic formulas
       that can be constructed using the predicates of P and the constants
       of the Herbrand Universe of P.

   (c) Herbrand Interpretation for P is any subset of the Herbrand base
       of P.

   (d) Herbrand model of P is a Herbrand Interpretation of P in which
       all the clauses of P are true.

   (e) Minimal Herbrand model of P is a Herbrand model none of whose 
       proper subsets are Herbrand models of P.

   (f) Least Herbrand model of P is a Herbrand model which is a subset
       of every Herbrand model of P.
---------------------------------------------------------------------------
6  (a) Herbrand Universe = { a,b,c,d,e }
   (b) EHB contains 25 elements
   (c) IHB contains 25 elements
   (d) I1 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e) }

       not a Herbrand model because the ground instance
               P(a,c) :- Q(a,b), P(b,c).
       is not true in I1.

       I2 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e) }

       not a Herbrand model because the ground instance
               P(a,d) :- Q(a,b), P(b,d).
       is not true in I2.

       I3 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e),
                    P(a,d), P(b,e) }

       not a Herbrand model because the ground instance
               P(a,e) :- Q(a,b), P(b,e).
       is not true in I3.

       I4 = EDB U { P(a,b), P(b,c), P(c,d), P(d,e), P(a,c), P(b,d), P(c,e),
                    P(a,d), P(b,e), P(a,e) }

       is a Herbrand model; is also the least Herbrand model;
        because all clauses are true in I4.
---------------------------------------------------------------------------