Second mid-term exam - Solutions
------------------------------------


Question 1
----------

((a))



I (forall X) Animal(X) => 
     (exists Y,Z) Has_part(X,Y) ^ Has_part(X,Z) ^ Leg(X) ^ Leg(Y) ^ not (Y=Z)

II (forall X) Dog(X) => Animal(X)

III (forall X) (Dog(X) ^ Can_walk(X)) =>
     ((forall Y) Has_part(X,Y) ^ Leg(Y) => OK(Y))

IV Dog(Poopoo) ^ Can_walk(Poopoo)



((b))

I is equivalent to:
   
   (forall X) (exists Y,Z) not Animal(X) or (Has_part(X,Y) ^ .... ^ not(Y=Z))

This gets split into 5 INF axioms (with Leg1() and Leg2() being Skolem
functions that take one argument):

1)  Animal(?X) => Has_part(?X, Leg1(?X))

2)  Animal(?X1) => Has_part(?X1, Leg2(?X1))

3)  Animal(?X2) => Leg(Leg1(?X2))

4)  Animal(?X3)  => Leg(Leg2(?X3))

5)  Animal(?X4) ^  (Leg1(?X4) = Leg2(?X4)) => F

Then II is obvious:

6)  Dog(?X5) => Animal(?X5)


III is equivalent to:

(forall X) not Dog(X) or not Can_walk(X) or 
   (forall Y) not Has_part(X,Y) or not Leg(Y) or OK(Y)

which is equivalent to:

not Dog(?X6) or not Can_walk(?X6) or not Has_part(?X6,?Y) or not Leg(?Y) or OK(?Y)

finally, in INF:

7) Dog(?X6) ^  Can_walk(?X6) ^  Has_part(?X6,?Y) ^ Leg(?Y) =>  OK(?Y)

Then IV becomes 2 clauses:

8) Dog(Poopoo)  - alternately:      (T => Dog(Poopoo))

9) Can_walk(Poopoo)  - alternately:    (T => Can_walk(Poopoo))


((c))



(exists Y) Leg(Y) ^ Has_part(Poopoo, Y) ^ OK(Y)



negated: not ((exists Y) Leg(Y) ^ Has_part(Poopoo, Y) ^ OK(Y))


which is equivalent to: (forall Y) Leg(Y) or not Has_part(Poopoo, Y) or OK(Y)

And in INF:

10) Leg(?Y1) ^ Has-part(Poopoo, ?Y1) ^ OK(?Y1) => F



((d))



6 + 8  {?X5/ Poopoo}

11) T => Animal(Poopoo)



1 + 11 {?X/ Poopoo}

12) T => Has_part(Poopoo,Leg1(Poopoo))



7 + 8  {?X6 / Poopoo }

13)  Can_walk(Poopoo) ^ Has_part(Poopoo,?Y) ^ Leg(?Y) => OK(?Y)



13 + 9

14) Has_part(Poopoo,?Y) ^ Leg(?Y) => OK(?Y)



14 + 12  { ?Y / Leg1(Poopoo) }

15) Leg(Leg1(Poopoo)) => OK(Leg1(Poopoo))



3 + 11 { ?X1 / Poopoo}

16)  T => Leg(Leg1(Poopoo))



15 + 16

17) T => OK(Leg1(Poopoo))



Now, resolving with the negation of the query, 10 + 12  { ?Y1 / Poopoo }

18) Leg(Leg1) ^ OK(Leg1) => F


Resolving 18  with 16 , then 17 gets

20)  T  =>  F  

Which is a contradiction, proving the theorem by refutation.




((e))

Can use generalized Modus Ponens to prove each of the three conjuncts
of the goal, as above, since all steps only used resolvents with a
unit consequent. For example, backward chaining with a conjunctive
goal will work here. Of course, it is not ALWAYS the case that
generalized modus ponens will work, as it is incomplete.



Question 2
-----------



(a) False - Algorithm run in polynomial time but building of
            minimal decision tree is NP-hard


(b) True - with, e.g. fitness function being inverse of number of
           nodes plus some constant times number of classification
           errors.

(c) True

(d) False - Parity-2 = XOR ( learning in class) is not possible with one
            Perceptron (not linearly seperable).





Question 3
----------

 ((a))

 



                      Clouds       Sprinkler_on

                        |               |

                        |               |

                        |               |

                        |               |

                        v               v

                       Rain --------> Lawn_wet                 

                        |

                        |

                        |

                        v

                      Road_wet





 ((b))

 It is dependent  - the path Clouds--Rain--Lawn_wet--Sprinkler_on
 is not blocked - because there is evidence in Lawn-wet but no
 evidence in Rain.

 ((c))

Independent - Rain being a pass-throgh evidence node blocks the only path


 ((d))

If Rain is given, then from  ((c)) we have:

 P( Clouds | Rain, Splinker_on) = P(Clouds | Rain)



 With Bayes' Law

P(Clouds=black|Rain)=            P(Rain | Clouds= Balck) P(Clouds=black)

                     ------------------------------------- ---------------------------------------=

                     P(Rain|Clouds=black) P(Clouds=black)+P(Rain|Clouds=none)P(Clouds=none) +

                                                      P(Rain|Clouds=white)P(Clouds=white)



                                0.5  x  0.2                      0.1          1

                    = --------------------------------- =   ------------ =  -----                                                    

                      0.5 x 0.2 + 0.1 x 0.3 + 0 x 0.5         0.1 + 0.03     1.3                             

 ((e))

 Yes, the underlying undirected graph is a tree.



 ((f))

 Add  arc from Clouds to Sprinkler_on


The result is no longer a polytree, due to the following cycle in
the underlying undirected graph:

Clouds--Rain--Lawn_wet--Sprinkler_on--Clouds