Take Home Test, CS 156, due November 17, 2005

There are 100 points on the test. Each question is worth 10 points.
 

  1. For the knowledge base KB whose clauses are given below, give a description in informal English of the first clause and the last clause.
    1. surname(x1,n1) ∨ ~surname(y1,n1) ∨ ~father-of(y1,x1) ∨ wife(x1)
    2. ~male(x2) ∨ ~wife(x2)
    3. male(chuck)
    4. male(andy)
    5. father-of(andy,bea)
    6. father-of(phil,chuck)
    7. father-of(phil,andy)
    8. ~wife(bea)
    9. surname(x9,name(x9))

  2. For the knowledge base with clauses
    1. ~gt(x,y) ∨ ~gt(y,z) ∨ gt(x,z)
    2. ~succ(a,b) ∨ gt(a,b)
    3. ~gt(x,x)
    why does the following attempt at a resolution proof that gt(5,2) run into problems? Here the predicate names gt and succ are abbreviations for is-greater-than and is-a-successor-of.

    The negation of the query (omitting the universal quantifier) is
      0. ~gt(5,2) Assuming that the sentences of the knowledge base are numbered in order beginning with 1, then
    Unifying 0 and 1 by the unifying substitution {5/x, 2/z}, we get
    4. ~gt(5,y) ∨ ~gt(y,2)
    Unifying 4 and 2 by the unifying substitution {y/a, 2/b}, we get
    5. ~gt(5,y) ∨ ~succ(y,2)
    Unifying 5 and 1 by the unifying substitution {5/x, y/z}, we get
    6. ~gt(5,y) ∨ ~gt(y,y) ∨ ~succ(y,2)

    But now, since the middle disjunct is in the knowledge base, we cannot hope to derive a contradiction from this clause, regardless of whatever other clauses might be in the knowledge base.

  3. Using the knowledge base KB of the Problem 1, use resolution to prove that
    (∃x) surname(chuck,x) ∧ surname(bea,x)
    For each step of the proof, state which two clauses are being resolved, show the unifying substitution, and give a new number to the resulting clause.

  4. Use resolution and a dummy answer predicate to find bea's surname given the knowledge base of the previous problem, if the sentences
    surname(phil,patel)
    and
    surname(anne, chang)
    replace the final sentence of that knowledge base. For each step of the proof, state which two clauses are being resolved, show the unifying substitution, and give a new number to the resulting clause.

  5. Suppose that in the first added sentence of the previous problem, phil is replaced by chuck. Would we still be able to find bea's surname? Why or why not?

  6. The following question is about Prolog. You may use a Prolog interpreter to assist you with this question if you want.
    1. For clause 1 of the knowledge base of Problem 1, a natural way of converting it to Prolog is
      surname(X,N) :- surname(Y,N), fatherOf(Y,X), not(wife(X)).
      However if this rule is read into Prolog along with translations of the other clauses, Prolog will run out of stack space before it finds an answer to the query
      surname(chuck,N).
      Rewrite the Prolog rule so that the query will be answered appropriately. If you are using a Prolog interpreter, you may leave clauses 2 and 8 untranslated without harm.

    2. If the fact fatherOf(phil,anne) is added to the corrected Prolog facts and rules of part 1 above, Prolog will report in response to the query surname(anne,X). that Anne has the same surname as Phil. However if not(wife(X)) is replaced in the first rule by nonwife(anne) (and the translations of clauses 2 and 8 of KB use this nonwife predicate), then Prolog will not report this. Which answer is most appropriate?

    3. Why does Prolog give two different answers in the two cases of part 2?

  7. Assuming that p(d) = 0.0011, p(s1) = 0.04, p(s2) = 0.01, p(s1|d) = 0.76, p(s2|d) = 0.1, p(t) = 0.11, and p(t|s1) = 0.99, and assuming that s1 and s2 are independent (as well as conditionally independent given d), find the probability of the disease d given that symptom s1 is present and symptom s2 is not.

  8. Using the assumptions of #7, 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?

    1. What independence assumption(s) did you make for Problems #8?

    2. For Problem #7, is it enough that s1 and s2 be conditionally independent? If not, what additional information would you need to solve the problem, and how would you use this information?

    1. In #7, assuming a universe of population 10,000,000, find the number of people in each of the 8 sets defined by all possible intersections of the set of people with the disease, the set of people exhibiting symptom s1, and the set of people exhibiting symptom s2. You may express your answer as a Venn diagram if you want.
    2. Try redoing this problem under the assumption that p(d) equals 0.011 rather than 0.0011. What goes wrong?