CSc 8710 DDLP
Exam 1 Solutions; Fall 2002
---------------------------

(1) CLAIM: F is satisfiable
    PROOF: Consider the interpretation I such that
    Domain(I) = {a,b}; I(P) = {(a),(b)}, I(Q) = {(a)}
    F is TRUE under I

    CLAIM: F is not a tautology
    PROOF: Consider the interpretation I such that
    Domain(I) = {a, b}; I(P) = {(a)}, I(Q) = {(b)}
    F is FALSE under I

    CLAIM: G is satisfiable
    PROOF: Consider the interpretation I such that
    Domain(I) = {a,b}; I(P) = {(a)}, I(Q) = {(a)}
    G is TRUE under I

    ALTERNATE PROOF: Follows from the fact that G is a tautology

    CLAIM: G is a tautology.
    PROOF (BY CONTRADICTION): Let G not be a tautology. Then
      there is an interpretation I in which G is FALSE i.e.
      (1) (Exists X)P(X) --> (Forall X)Q(X) is TRUE in I and
      (2) (Forall X)(P(X) --> Q(X)) is FALSE in I.
      Since (2) is FALSE, there must be some a in Domain(I) such 
             that P(a) is TRUE and Q(a) is FALSE.
      Since there is an "a" for which P(a) is TRUE, (Exists X)P(X)
         is TRUE in I. Hence, by (1) (Forall X)Q(X) must be TRUE; in
         particular Q(a) must be TRUE, a contradiction!

    ALTERNATE PROOF (USING IMPLICATIONS):
            (Exists X)P(X) --> (Forall X)Q(X)
    implies not (Exists X)P(X) V (Forall X)Q(X)
    implies (Forall X)not P(X) V (Forall X)Q(X)
    implies (Forall X)(not P(X) V Q(X))
    implies (Forall X)(P(X) --> Q(X))
    Therefore, (Exists X)P(X) --> (Forall X)Q(X) --> 
               (Forall X)(P(X) --> Q(X)) is a tautology

(2) (a) NO
    (b) NO
    (c) YES; mgu = { John <-- 1, X <-- kisses, Mary <-- kisses }
    (d) YES; mgu = { H <-- c, Y <-- [a,c|T], Z <-- [b,a,b], X <-- [c|T] }
    (e) NO

(3)               ?-maxlist([4,6,5],M).
                           | (Rule 2) 
                           | {H' <-- 4, T' <-- [6,5], Max' <-- M}
                  ?-maxlist([6,5],MaxT'), max(4,MaxT',M).
                           | (Rule 2) 
                           | {H'' <-- 6, T'' <-- [5], Max'' <-- MaxT'}
                  ?-maxlist([5],MaxT''), max(6,MaxT'',maxT'), max(4,MaxT',M).
                           | (Rule 1) 
                           | {MaxT'' <-- 5}
                  ?-max(6,5,maxT'), max(4,MaxT',M).
 {X<-6,Y<-5,MaxT'<-6}     /             \ {X<-6,Y<-5,MaxT'<-5} 
 (Rule 3)                /               \  (Rule 4)
                  ?-6>5,max(4,6,M)     ?-6<=5,max(4,5,M)
                        |                  FAIL
                        |
                   ?-max(4,6,M)
   {M <- 4}           /    \   {M <- 6}
   (Rule 3)          /      \  (Rule 4)
               ?-4>6      ?-4<=6
               FAIL          |
                             |
                          SUCCESS (M = 6)

(4) (a) Yes
    (b) No
    (c) L1 = [p,e,i,e,t]
        L2 = [r,s,d,n]
    (d) L1 = [3,7,8,1,0]
        L2 = [4,1,9,2,12]
     q1(L) is true if list L = reverse(L) (palindrome!)
     q2(L,L1,L2) is true if L1 contains every alternate element
          from L starting at position 1 and L2 contains every 
          alternate element from L starting at position 2.

(5) separate([],[],[]).
    separate([A|T],[A|M],F) :- male(A,_), separate(T,M,F).
    separate([A|T],M,[A|F]) :- female(A,_), separate(T,M,F).
    separate([A|T],M,F) :- not male(A,_), not female(A,_), separate(T,M,F).

(6) (a) {a,b,c,d,e,f,g,h,red,blue,green}
    (b) 3x11x11x11 = 3993
    (c) Tp1 = { 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) }

        Tp2 = Tp1 U 
             { trip(red,a,b), trip(red,b,c), trip(red,c,d), trip(blue,f,c),
               trip(blue,c,e), trip(green,h,e), trip(green,e,g) }

       Tp3 = Tp2 U 
             { trip(red,a,c), trip(red,b,d), trip(red,b,e), trip(blue,f,e),
               trip(blue,c,g), trip(green,h,g) }

       Tp4 = Tp3 U 
             { trip(red,a,d), trip(red,a,e), trip(red,b,g),
               trip(blue,f,g), trip(red,a,g) }

       Tp5 = Tp4 

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

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

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