Take-Home Test
CS 156                   (100 points)            due April 29, 1997


Problems are worth 10 points unless labeled otherwise.  In problems
#1-4, assume that p(d) = .0002, p(s1) = .0025, p(s2) = .01, p(s1|d) =
.5, p(s2|d) = .1, p(t) = .02, and p(t|s1) = .8.

1)  Find the probability of the disease d given that symptom s2 is
present and symptom s1 is absent.

2)  Suppose symptom s1 is not observable directly, but that test t is
used as a test for it.  What is the probability of the disease d
given a positive result for test t?

3)  What assumptions are necessary in Problems #1 and #2?

4)  Verify or refute (for the probabilities given above) for the following
analog of Theorem 3:
    p(d|s2) = p(d|s1,s2)p(s1) + p(d|s1',s2)p(s1')

5)  Problem #9, p. 168, Rich & Knight

6)  Why is it a bad idea to have both rules
       male(X):- not female(X).
       female(X):- not male(X).
in a Prolog knowledge base?  Hint:  what happens in response to the query
       female(andy).
if the only other facts and rules in the knowledge base are
       male(chuck).
       female(liz).

7)  (15 points)  Suppose that the Prolog list [a,b] is represented by
the pair of terms [a,b|X] and X.  The Prolog list [c,d,e] could then
be represented by the pair of terms [c,d,e|Y] and Y.  This representation is
called a "difference list" representation, since the list being represented
corresponds to the difference of the two terms.  The append relation would
then have 6 arguments -- suppose that it is defined solely by the fact
                  append(S,T,T,Y,S,Y).
where the last pair of arguments represents the value of the "append" function.
    a) What will be bound to U and V as a result of the query
                  append([a,b|X],X,[c,d,e|Y],Y,U,V)
Justify your answer.  Does this answer make sense in terms of the new
representation for lists?
    b) What would be a good representation for the empty list?  Verify using
the definition given above that if the first or second argument to the "append"
function is empty, the value is equal to that of the remaining argument
    c) Give an advantage of the difference list representation.







                        Take-Home Test
CS 156                   (100 points)            due April 29, 1997


8)  Given the Prolog knowledge base
          mother(liz,chuck).
          mother(liz,andy).
          father(chuck,bill).
          father(chuck,hank).
          father(andy,bea).
Can you get a positive answer to the query
            older(liz,bea)
Justify your answer.  Show that you can add another rule involving only the
binary predicate "older" and get a positive answer to the query.  Justify your
answer by giving the resolution proof found by Prolog.


9) (15 points)
(a)  Convert your final knowledge base of #8 to clause form.
(b)  What clause(s) would correspond to the information that X is the
grandmother of Y only if (as opposed to if) there's a Z with X being a mother
of Z and Z being a parent of Y
(c)  Using the clauses of (a) and (b), find a resolution proof that for all X
and Y, X is older than Y if X is a grandmother of Y.