## 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.

• a. If O1 is inside O2, then O2 is hollow.
• b. If O1 is inside O2 and O2 is inside O3, then O1 is inside O3.
Answer ~i(O1,O2) V ~i(O2,O3) V i(O1,O3).
• c. Every small object is inside some medium-sized object.
~s(O1) V m(sk1(O1)
• d. Every medium-sized object is inside some big object.
~m(O1) V b(sk2(O1))
• e. Every small object is red.
• e. If O1 is inside O2, O1 is red, and O2 is big, then O2 is red.
Answer: ~i(O1,O2) V ~r(O1) V ~b(O2) V r(O2)
• f. ox is small.

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
```