AI: Problem Set 4

Assigned: March 4
Due: March 25

Problem 1

Let D be a domain containing solid objects. Let L be the first-order language over D with the following non-logical symbols:
i(O1,O2) --- Object O1 is inside O2.
h(O) --- O is hollow.
r(O) --- O is red.
s(O) --- O is small.
m(O) --- O is medium-sized.
b(O) --- O is big.
ox --- Constant symbol.

A. Represent the following statements as Horn clauses in L.

B. Prove the statement ``There exists a hollow red object'' using backward chaining.

The negated goal G0 is ~h(O) V ~r(O).
Resolving G0 with (a) gives G1: ~i(O1,O2) V ~r(O2)
Resolving G1 with (b) gives G2: ~i(O1,OB) V ~i(OB,O2) V ~r(O2)
Resolving G2 with c.1 gives G3: ~s(O1) V ~i(sk1(O1),O2) V ~r(O2)
Resolving G3 with f gives G4: ~i(sk1(ox),O2) V ~r(O2).
Resolving G4 with d.1 gives G5: ~m(sk1(ox)) V ~r(sk2(sk1(ox))
Resolving G5 with c.2 gives G6: ~s(ox) V ~r(sk2(sk1(ox))
Resolving G6 with f gives G7: ~r(sk2(sk1(ox))
Resolving G7 with e gives G8: ~i(O1,sk2(sk1(ox))) V ~r(O1) V ~b(sk2(sk1(ox)).
Resolving G8 with b gives G9: ~i(O1,O2) V ~i(O2,sk2(sk1(ox)) V ~r(O1) V
                              ~b(sk2(sk1(ox)))
Resolving G9 with c.1 gives G10: ~sm(O1) V ~i(sk1(O1),sk2(sk1(ox)) V ~r(O1) V
                                 ~b(sk2(sk1(ox))
Resolving G10 with f gives G11: ~i(sk1(ox),sk2(sk1(ox))) V ~r(ox) V 
                                ~b(sk2(sk1(ox))
Resolving G11 with d.1 gives G12: ~m(sk1(ox)) V ~b(sk2(sk1(ox)))
Resolving G12 with c.2 gives G13: ~s(ox) V ~b(sk2(sk1(ox))
Resolving G13 with f gives G14: ~b(sk2(sk1(ox))
Resolving G14 with d.2 gives G15: ~m(sk1(ox))
Resolving G15 with c.2 gives G16: ~s(ox)
Resolving G16 with f gives the empty clause.

C. Prove the statement ``There exists a hollow red object'' using forward chaining.

The negated goal G0 is ~h(O) V ~r(O).
Resolving f with e gives A1: r(ox).
Resolving f with c.1 gives A2: i(ox,sk1(ox))
Resolving f with c.2 gives A3: m(sk1(ox))
Resolving A3 with d.1 gives A4: i(sk1(ox),sk2(sk1(ox)))
Resolving A3 with d.2 gives A5: b(sk2(sk1(ox))
Resolving A2 with b gives A6: ~i(sk1(ox),O3) V i(ox,O3)
Resolving A6 with A4 gives A7: i(ox,sk2(sk1(ox)))
Resolving A7 with e gives A8: ~r(ox) V ~b(sk2(sk1(ox))) V r(sk2(sk1(ox)))
Resolving A8 with A1 gives A9: ~b(sk2(sk1(ox))) V r(sk2(sk1(ox)))
Resolving A9 with A5 gives A10: r(sk2(sk1(ox)))
Resolving A4 with a gives A11: h(sk2(sk1(ox)))
Resolving A11 with G0 gives A12: ~r(sk2(sk1(ox))
Resolving A10 with A12 gives the empty clause.

Problem 2

Let A, B, C, D be Boolean random variables.

Given that:

Prob(A=T) = 0.8.
Prob(B=T | A=T) = 0.2
Prob(B=T | A=F) = 0.6
Prob(C=T | A=T) = 0.7
Prob(C=T | A=F) = 0.4
Prob(D=T | B=T) = 0.1
Prob(D=T | B=F) = 0.2
B and C are conditionally independent given A.
A and D are conditionally independent given B.

Evaluate the following expressions.

Prob(B=T) = P(B=T^A=T) + P(B=T^A=F) = 
     P(B=T | A=T) P(A=T) + P(B=T | A=F) P(A=F) = 0.2*0.8 + 0.6*0.2 = 0.28.

Prob(D=T) = 
  P(D=T^B=T^A=T) + P(D=T^B=T^A=F) + P(D=T^B=F^A=T) + P(D=T^B=F^A=F) =
  P(D=T | B=T^A=T) P(B=T | A=T) P(A=T) + P(D=T | B=T^A=F) P(B=T | A=F) P(A=F) +
  P(D=T | B=F^A=T) P(B=F | A=T) P(A=T) + P(D=T | B=F^A=F) P(B=F | A=F) P(A=F)

  By the conditional independences assumption P(D=T | B=x,A=y) = P(D=T | B=x).
  So the above sum is equal to 

  P(D=T | B=T) P(B=T | A=T) P(A=T) + P(D=T | B=T) P(B=T | A=F) P(A=F) +
  P(D=T | B=F) P(B=F | A=T) P(A=T) + P(D=T | B=F) P(B=F | A=F) P(A=F) =
  0.1*0.2*0.8 + 0.1*0.6*0.2 + 0.2*0.8*0.8 + 0.2*0.4*0.2 = 0.172

Prob(B=T,C=T | A=F) = P(B=T|A=F)P(C=T|A=F) = 0.6 * 0.4 = 0.24.

Prob(B=T,D=T | A=F) = P(D=T | B=T,A=F) * P(B=T | A=F).
   By conditional independence P(D=T | B=T,A=F) = P(D=T | B=T), so the above is
   P(D=T | B=T) * P(B=T | A=F) = 0.1 * 0.6 = 0.06.

Prob(A=T | B=T) = (Bayes' Law) P(B=T | A=T) P(A=T) / P(B=T) =
    0.2 * 0.8 / 0.28 = 0.57.

Prob(A=T | B=F, C=T) = (Bayes' Law) P(B=F, C=T | A=T) P(A=T) / P(B=F,C=T)

    Now, P(B=F,C=T) = P(B=F,C=T | A=T) P(A=T) + P(B=F,C=T | A=F) P(A=F).
    By conditional independence, P(B=F,C=T|A=x) = P(B=F|A=x) * P(C=T|A=x).
    Hence the above exprssion is equal to
      P(B=F|A=T) P(C=T|A=T) P(A=T) /
        [P(B=F|A=T) P(C=T|A=T) P(A=T) + P(B=F|A=F) P(C=T|A=F) P(A=F)] =
      0.8*0.7*0.8 / [0.8*0.7*0.8 +  0.4*0.4*0.2] = 0.93

Prob(A=T | D=T) = (Bayes' law) P(D=T | A=T) P(A=T) / P(D=T) =
   (repeating the calculations done for P(D=T)
   P(D=T|B=T) P(B=T|A=T) P(A=T) + P(D=T|B=F) P(B=F|A=T) P(A=T) /P(D=T)  =
   0.1*0.2*0.8 + 0.2*0.8*0.8 / 0.172 = 0.84

Prob(C=T | B=F) = P(C=T^A=T | B=F) + P(C=T^A=F | B=F) = (using independence)
    P(C=T|A=T) P(A=T|B=F) + P(C=T|A=F) P(A=F|B=F).
      Now P(A=T|B=F) = (Bayes' law) P(B=F|A=T) P(A=T)/P(B=F) 
         0.8 * 0.8 / 0.72 = 0.89
      Thus P(A=F|B=F) = 1-P(A=T|B=F) = 0.11
    So P(C=T|B=F) = 0.7*0.89 + 0.4*0.11 = 0.67