CMSC380_FE_02_ALL

FINAL EXAM
ARTIFICIAL INTELLIGENCE

CMSC 380

SPRING 2002a

Problems :

1. Represent the following sentences in First Order Logic using a consistent vocabulary (which you must first define) :

There is a senior who helps all juniors who need help.

]x Sen(x) & Vy (Jun(y) & NeedsHelp(y) => Helps(x,y))

There is a senior who doesn't help anybody except the juniors who he knows personally.

]x Sen(x) & Vy (Jun(y) & Knows(x,y) ó Helps(x,y))

Not all seniors who have a good research presentation have a high GPA.

! Vx (Sen(x) & GoodResPres(x) => HighGPA(x))

(d) Not all professors who have poor student evaluations are bad teachers.

(25 (=12+13) points)

! Vx (Prof(x) & PoodStuEval(x) => BadTeach(x))

2. Convert the following First Order Logic sentence into its Conjunctive Normal Form :

"x Friendly(x) <== $y ( Parent(y,x) & TaughtFriendliness(y,x) )

= Vx (! (]y (Parent(y,x) & TaughtFriendliness(y,x))) V Friendly(x))

= Vx (Vy (! Parent(y,x) V ! TaughtFriendliness(y,x)) V Friendly(x))

= Vx Vy (! Parent(y,x) V ! TaughtFriendliness(y,x) V Friendly(x))

= ! Parent(y,x) V ! TaughtFriendliness(y,x) V Friendly(x)

"x Baby(x) <== $y ( Toy(y) & FavoriteToy(y,x) )

= Vx ( ! (]y ( Toy(y) & FavoriteToy(y,x) ) ) V Baby(x) )

= Vx ( Vy ( ! Toy(y) V ! FavoriteToy(y,x) )

V Baby(x) )

= Vx Vy ( ! Toy(y) V ! FavoriteToy(y,x)

V Baby(x) )

= ! Toy(y) V ! FavoriteToy(y,x)

V Baby(x)

(25 points)

3. The following is a knowledge base (its sentences numbered and described by Horn Clauses) :

(I)

*Mike is an average athlete*	*1. AveAthlete(Mike)*
*Sandra is an extraordinary programmer*	*2. ExtraAthlete(Sandra)*
*An extraordinary athlete performs better in competitions than an average one.*	*3. Vx Vy ExtraAthlete(x) & AveAthlete(y)* *è PerformsBetter(x,y)*

Provide a proof that Sandra performs better in competitions than Mike . In the proof, for each step indicate :
    (a) the inference rule being used,
    (b) the unifiers being applied,
    (c) the sentences the rule is being applied to, and
    (d) the sentence derived by the rule (number it, as well)

- (UE) with x=Sandra and y=Mike applied to 3. yields :

4. ExtraAthlete(Sandra) & AveAthlete(Mike) è PerformsBetter(Sandra,Mike)

(AI) applied to 1. and 2. yields :

5. ExtraAthlete(Sandra) & AveAthlete(Mike)

(MP) applied to 5. and 4. yields :

6. PerformsBetter(Sandra,Mike).

(II)

*Mike is a snake*	*1. Snake(Mike)*
*Sandra is a mouse*	*2. Mouse(Sandra)*
*Mice are terrified by snakes*	*3. Vx Vy Snake(x) & Mouse(y)* *è TerrifiedBy(y,x)*

Provide a proof that Sandra is terrified by Mike . In the proof, for each step indicate :
    (a) the inference rule being used,
    (b) the unifiers being applied,
    (c) the sentences the rule is being applied to, and
    (d) the sentence derived by the rule (number it, as well)

(25 points)

- (UE) with x=Sandra and y=Mike applied to 3. yields :

4. Mouse(Sandra) & Snake(Mike) è TerrifiedBy(Sandra,Mike)

(AI) applied to 1. and 2. yields :

5. Mouse(Sandra) & Snake(Mike)

(MP) applied to 5. and 4. yields :

6. TerrifiedBy(Sandra,Mike).

4. The following is a knowledge base (its sentences numbered and described by First Order Logic clauses) :

(I)

*Students with good homeworks are well prepared for exams*	*1. HasGoodHWs(x) è* *ExamsReady(x)*
*Students without good homeworks have more time to study*	*2. ! HasGoodHWs(x) è* *StudiesMore(x)*
*Students who have more time to study get good grades.*	*3. StudiesMore(x) è* *GettingGoodGrade(x)*
*Students who are well prepared for exams get good grades*	*4. ExamsReady(x) è* *GettingGoodGrade(x)*

Provide a proof for GettingGoodGrade(Amy). In the proof, for each step indicate :
    (a) the inference rule being used,
    (b) the unifiers being applied,
    (c) the sentences the rule is being applied to, and
    (d) the sentence derived by the rule (number it, as well)

Add negated GettingGoodGrade(Amy) to the knowledge base :

0. ! GettingGoodGrade(Amy)

- Turn this into CN form knowledge base :

*Students with good homeworks are well prepared for exams*	*1. ! HasGoodHWs(x) V* *ExamsReady(x)*
*Students without good homeworks have more time to study*	*2. HasGoodHWs(x) V* *StudiesMore(x)*
*Students who have more time to study get good grades.*	*3. ! StudiesMore(x) V* *GettingGoodGrade(x)*
*Students who are well prepared for exams get good grades*	*4. ! ExamsReady(x) V* *GettingGoodGrade(x)*

(RR) applied to 1. and 2. yields :

5. ExamsReady(x) V StudiesMore(x)

(RR) applied to 5. and 3. yields :

6. ExamsReady(x) V GettingGoodGrade(x)

(RR) applied to 6. and 4. with x=Amy yields :

7. GettingGoodGrade(Amy)

contradicting 0.

(II)

*Students missing classes have more time to study*	*1. MissingClasses(x) è* *StudiesMore(x)*
*Students not missing classes learn a lot in class*	*2. ! MissingClasses(x) è* *LearnsALotInClass(x)*
*Students who have more time to study are good students.*	*3. StudiesMore(x) è* *GoodStudent(x)*
*Students who learn a lot in class are good students*	*4. LearnsALotInClass(x) è* *GoodStudent(x)*

Provide a proof for GoodStudent(Susan). In the proof, for each step indicate :
    (a) the inference rule being used,
    (b) the unifiers being applied,
    (c) the sentences the rule is being applied to, and
    (d) the sentence derived by the rule (number it, as well)

(25 points)

Add negated GoodStudent(Susan) to the knowledge base :

0. ! GoodStudent(Susan)

- Turn this into CN form knowledge base :

*Students missing classes have more time to study*	*1. ! MissingClasses(x) V* *StudiesMore(x)*
*Students not missing classes learn a lot in class*	*2. MissingClasses(x) V* *LearnsALotInClass(x)*
*Students who have more time to study are good students.*	*3. ! StudiesMore(x) V* *GoodStudent(x)*
*Students who learn a lot in class are good students*	*4. ! LearnsALotInClass(x) V* *GoodStudent(x)*

(RR) applied to 1. and 2. yields :

5. StudiesMore(x) V LearnsALotInClass(x)

(RR) applied to 5. and 3. yields :

6. LearnsALotInClass(x) V GoodStudent(x)

(RR) applied to 6. and 4. with x=Susan yields :

7. GoodStudent(Susan)

contradicting 0.

5. A doctor says that an infant who predominantly turns the head to the right while lying on the back will be right handed, and one who turns to the left will be left-handed. Mary predominantly turned her head to the left. Given that 90% of the population is right-handed, what is Mary's probability of being right-handed if the test is 80% accurate ?

(25=15+5+5 points)

P(RH) = 0.9 è

P(LH) = P(!RH) = 1-0.9 = 0.1

P(THR | RH) = 0.8 è

P(THL | RH) = 1 - P(THR | RH) = 1 - 0.8 = 0.2

P(THL | LH) = 0.8 è

P(THL | RH) = 1 - P(THL | LH) = 1 - 0.8 = 0.2

P(MRH | MTHL) = P(RH | THL) = P ( RH & THL) / P(THL) = [ P(RH) * P (THL | RH) ] / P(THL) =

[ P(RH) * P (THL | RH) ] / [ P(LH & THL) + P(RH & THL) ] =

[ P(RH) * P (THL | RH) ] / [ P(LH) * P(THL | LH) + P(RH) * P(THL | RH) ] =

[ 0.9 * 0.2 ] / [ 0.1 * 0.8 + 0.9 * 0.2 ] =

0.69231

6. Consider the following situation : You have a new burglar alarm system installed at home. It is fairly reliable at detecting a burglary, but also responds on occasion to minor earthquakes. The two neighbours, John and Mary, have promissed to call you at work when they hear the alarm. John always calls when he hears the alarm but sometimes confuses the telephone ringing withthe alarm and calls then, too. Mary, on the other hand, likes rather loud music and sometimes misses the alarm altogether. Assume that the burglary and earthquakes directly affect the alarm going off, but Mary or John calling depends only on the alarm (they percieve neither burglaries or earthquakes directly).

Given the topology of the belief network as below, as well as all of its corresponding conditional probabilities, compute the following probabilities :

                (a)    P(J & M & A & B & E) = P(J|A) * P(M|A) * P(A|B,E) * P(B) * P(E) = 0.9 * 0.7 * 0.95 * 0.001 * 0.002
                (b)    P(J & !M & A & B & E) = P(J|A) * P(!M|A) * P(A|B,E) * P(B) * P(E) = 0.9 * 0.3 * 0.95 * 0.001 * 0.002
                (c)    P(!J & M & A & B & E) = P(!J|A) * P(M|A) * P(A|B,E) * P(B) * P(E) = 0.1 * 0.7 * 0.95 * 0.001 * 0.002
                (d)    P(!J & !M & A & B & E) =

P(!J|A) * P(!M|A) * P(A|B,E) * P(B) * P(E) = 0.1 * 0.3 * 0.95 * 0.001 * 0.002

(25=12+13 points)

7.
(I)
Consider the following situation : You are at an AI class in which both, studying from your textbook, and doing your homework assignments makes you a knowledgeable AI person. For the sake of keeping the example simple, assume that the two (studying and doing homeworks) are not related or dependent in any way (?!). Also, assume that a person knowledgeable in AI will do very well on the assigned AI project, as well as on the AI final exam. In addition, while studying from the textbook and doing the homeworks directly affect being AI knowledgeable, doing well on the project and doing well on the final depends directly only on person's being AI knowledgeable or not.

Specify a topology for the belief network described above, as deemed appropriate to the description.

<AIK>

Specify all conditional probability tables for each node in the network from (a).

0.6 <S> 0.6 <HW>

S HW

0.95 T T

<AIK> 0.55 T F

0.55 F T

0.01 F F

AIK AIK

T 0.95 <PDW> <FDW> 0.9 T

F 0.2 0.1 F

Using (a) and (b) compute the following probability

P(PDW & FDW & AIK & !S & !HW) = P(PDW|AIK) * P(FDW|AIK) * P(AIK|!S,!HW) * P(!S) * P(!HW) =

0.95 * 0.9 * 0.01 * 0.4 * 0.4 =

        Here :
        PDW stands for doing well on the project
        FDW stands for doing well on the final
        AIK stands for being AI knowledgeable
        S stands for studying a lot from the textbook, and
        HW stands for doing well on homeworks.