CSc 8710, Fall 2002
Exam 1
------

(1) Consider the following predicate logic formulas:

    F = ((Forall X)P(X) --> (Forall X)Q(X)) --> (Forall X)(P(X) --> Q(X))

    G = ((Exists X)P(X) --> (Forall X)Q(X)) --> (Forall X)(P(X) --> Q(X))

    For each formula, answer the following questions: Is the formula satisfiable? 
    Is it a tautology? Prove your answer.


(2) Do the following pairs of expressions have an MGU? If yes, what is it?
    Show your work.

    (a) g(a, X, X, Y, b) and g(V, V, W, c, W)

    (b) p(f(A,B), g(f(A)), B) and p(X, g(X), f(X))

    (c) times(1, X, X) and times(John, Mary, kisses)

    (d) append([H|T], Y, [H|Z]) and append(X, [a|X], [c,b,a,b])

    (e) p( f(X,X), g(h,a), h(a) ) and p( f(Y,Z), g(Y,a), Z ) 

(3) Consider the following program: 

    % maxlist(List, Max) is true if Max is the maximum of list.
    maxlist([H], H).
    maxlist([H|T], Max) :-
       maxlist(T, MaxT),
       max(H, MaxT, Max).

    max(X, Y, X) :- X > Y.
    max(X, Y, Y) :- X <= Y.

    Draw the SLD Refutation tree for this program and the query 
  
    ?- maxlist([4,6,5], M). 

(4) Consider the following Prolog program:

    q1([]).
    q1([X]).
    q1(L):- append([F|M],[F],L),q1(M). 

    q2([],[],[]).
    q2([X],[X],[]).
    q2([X,Y|L],[X|L1],[Y|L2]) :- q2(L,L1,L2).

    How will Prolog respond to the following queries?

    (a) q1([m, a, d, a, m]).

    (b) q1([a, r, i, s, t, o, t, l, e]).

    (c) q2([p, r, e, s, i, d, e, n, t], L1, L2).

    (d) q2([3, 4, 7, 1, 8, 9, 1, 2, 0, 12], L1, L2).

    Explain in words what the predicate q1 is.

    Explain in words what the relation q2 is.

(5) Given is a database defining the predicates male and female, for example: 

    male(john, 35).    female(anna, 27).
    male(eric, 26).    female(tina, 30).
    male(fred, 28).    female(karen, 28).

    Write a predicate separate(Names, Males, Females), which given a list of 
    names Names returns two sublists Males and Females, containing the male 
    and female names respectively of Names. 

    Notes: The second argument of male/female is irrelevant. You may assume 
    that no name is both male and female. You may not assume that all names 
    in the list Names occur in the database. Those names that are neither male 
    nor female according to the database are neither in Males nor in Females. 
    Solve the problem by going through the list, not by using setof. 

(6) Consider the following Logic Program P:

    trip(L,S,E) :- leg(L,S,E).
    trip(L,S,E) :- leg(L,S,I), trip(L,I,E). 
    trip(L,S,E) :- interchange(L,M,I), trip(L,S,I), trip(M,I,E).
    leg(red,a,b).
    leg(red,b,c).
    leg(red,c,d).
    leg(blue,f,c).
    leg(blue,c,e).
    leg(green,h,e).
    leg(green,e,g).
    interchange(red,blue,c).
    interchange(blue,green,e).

    (a) List the Herbrand Universe for the database.
    (b) How many elements does the Herbrand Base contain.
    (c) Starting with the empty Herbrand interpretation, compute T_P^{i},
        i >= 0, until a fixed point solution is generated. 
        Show work after each application of T_P.

(7) Consider the following Deductive Database/Logic Program, P.
     edge(a,b).
     edge(b,c).
     edge(c,d).
     edge(d,e).
     edge(e,f).
     edge(f,g).
     path(X,Y) :- edge(X,Y).
     path(X,Y) :- path(X,Y), path(Y,Z).
   What is the value of T_P(T_P(T_P(I))) where I is the following
   Herbrand Interpretation:

     I = { edge(a,c), edge(c,e), edge(e,g), path(c,b), path(e,d) }