CSc 8710, Fall 2005
Practice Test 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 relational database schema:

MOVIES(TITLE,Director)
ACTORS(TITLE,ACTOR)
THEATERS(TNAME,Address,Phone)
PLAYS(TNAME,TITLE,STARTTIME)

The key attributes are shown in all capital letters.
The MOVIES table records information about
current movies, the ACTORS table records information
about the different actors acting in each movie,
the THEATERS table records information
about the various theaters in a city and the PLAYS
table records information about which movie is being played in
which theater and at what time.

Write Datalog programs to answer the following queries.

(1) Find the directors who have acted in a movie they directed.

(2) Find the movies that are directed by Kurosawa or
    are being played in theater Odeon.

(3) Find the directors such that EVERY actor has acted
    in at least one of his or her movies.

(4) Find actors who act ONLY for director Kurosawa.

(5) Find all pairs of actors who act in EXACTLY the same movies.