Assignment 3 Solutions cse2309/3309 csc2091/3091 Artificial Intelligence




Yüklə 124.02 Kb.
tarix22.02.2016
ölçüsü124.02 Kb.

Assignment 3 Solutions CSE2309/3309 CSC2091/3091 - Artificial Intelligence


CSE2309/3309 CSC2091/3091

Artificial Intelligence - Assignment 3

(Propositional Logic and First Order Predicate Calculus)


Solutions from Richard Nichols and Lam Phuong Lam

Question 1



F: The French team will win at least one gold medal.

G: The German team will win at least one gold medal.

D: The Danish team will win at least one gold medal.

P: The French team is plagued with injuries.

S: The star German runner is disqualified.

R: It rains during most of the competition.


  1. At least one (of the three teams) will win a gold medal.





  1. At most one of them will win a gold medal.

( F  G  D )  (F  G  D )  (F  G  D )  (F  G  D ) or

( F  G  D )  (F  G  D )  (F  G  D )  (F  G  D )



  1. Exactly one of them will win a gold medal.

( F  G  D )  (F  G  D )  (F  G  D )






  1. Provided it doesn't rain during most of the competition and their star runner isn't disqualified, the Germans will win a gold medal if either of the other teams does.

( R  S  ( F  D ) )  G







  1. The Germans will win a gold medal only if it doesn't rain during most of the competition and their star runner is not disqualified.

(
R  S )  G (AN: Note "only if" is opposite direction to "if")


Question 2





  1. (Smoke  Fire)  (Smoke  Fire)

Convert to clausal form:


: (Smoke  Fire)  (Smoke  Fire)

=  (Smoke  Fire)  (Smoke  Fire)

= (Smoke  Fire)  Smoke  Fire
Now construct truth table:




Smoke

Fire

Fire

Smoke  Fire

(Smoke  Fire)  Smoke  Fire

T

T

F

F

T

T

F

T

T

T

F

T

F

F

F

F

F

T

F

T

From the result column it can be seen that this expression is neither valid nor unsatisfiable.





  1. Smoke  Fire Fire

Already in clausal form: Smoke Fire Fire


Now construct truth table:


Smoke

Fire

Fire

Smoke  Fire Fire

T

T

F

T

T

F

T

T

F

T

F

T

F

F

T

T



From the result column it can be seen that this expression is always true, therefore -- valid.




  1. [(Smoke  Heat)  Fire]  [(Smoke  Fire)  (Heat  Fire)]

Convert to clausal form:


: [(Smoke  Heat)  Fire]  [(Smoke  Fire)  (Heat  Fire)]

= [(Smoke  Heat)  Fire]  [(Smoke  Fire)  (Heat  Fire)]

= (Smoke  Heat  Fire)  (Smoke  Fire  Heat  Fire)

= (Smoke  Heat  Fire)  (Smoke  Fire  Heat)

= Smoke  Heat  Fire
Now construct truth table:


Heat

Smoke

Fire

Smoke

Heat

Smoke  Heat

Fire



T

T

T

F

F

T

T

T

F

F

F

F

T

F

T

T

F

T

T

F

F

T

F

T

F

T

T

F

T

T

F

T

F

F

T

T

F

F

T

T

T

T

F

F

F

T

T

T


From the result column it can be seen that this expression is neither valid nor unsatisfiable.






  1. {[Smoke  Fire]  [(Smoke  Heat)  Fire]}

Convert to clausal form:


: {[Smoke  Fire]  [(Smoke  Heat)  Fire]}

= {[Smoke  Fire]  [(Smoke  Heat)  Fire]}

= {[Smoke  Fire]  [(Smoke  Heat)  Fire]}

= [Smoke  Fire]  [Smoke  Heat  Fire]

= [Smoke  Fire]  [Smoke  Heat  Fire]

= (Smoke  Fire)  Smoke  Heat  Fire


Now construct truth table:




Heat

Smoke

Fire

Smoke

Fire

Smoke  Fire

(Smoke  Fire)  Smoke  Heat  Fire

T

T

T

F

F

T

F

T

T

F

F

T

F

F

T

F

T

T

F

T

F

T

F

F

T

T

T

F

F

T

T

F

F

T

F

F

T

F

F

T

F

F

F

F

T

T

F

T

F

F

F

F

T

T

T

F


From the result column it can be seen that this expression is always false, therefore unsatisfiable.

Question 3


If the rain continues, then the river rises. If rain continues and the river rises, then the bridge will wash out. If continuation of rain will wash the bridge out, then a single road is not sufficient for the town. Either a single road is sufficient for the town or the traffic engineers have made a mistake. Prove the traffic engineers have made a mistake.
Symbols:


C

- Rain continues.

R

- River rises.

B

- Bridge washes out.

S

- Single road is not enough.

E

- Engineers have made a mistake.


Axioms:


1.

C  R

Or

C  R

2.

(R  C)  B

Or

R  C  B

3.

(C  B)  S

Or
So:

3.1

3.2

(C  B)  S =

(C  B)  S =

(S  C)  (S  B)


  • (S  C)

  • (S  B)

4.

S  E

Or

S  E



R
Used Modus Ponens.

Result: The engineers made a mistake.

Quad Erat Demonstrandum - It is proven!

Used resolution because B and B can't both be true.

Used resolution because C and C can't both be true.

Eliminated one C.

Used resolution because R and R can't both be true.
equired to Prove:
E






Question 4

If Mr. Smith is the brakeman's next-door neighbor, then Mr. Smith lives halfway between Detroit and Chicago. If Mr. Smith lives halfway between Detroit and Chicago, then he does not live in Chicago. Mr. Smith is the brakeman's next-door neighbor. If Mr. Robinson lives in Detroit, then he does not live in Chicago. Mr. Robinson lives in Detroit. Mr. Smith lives in Chicago or else either Mr. Robinson or Mr. Jones lives in Chicago. If Mr. Jones lives in Chicago, then the brakeman is Jones. Prove the brakeman is Jones.


Symbols:


SN

- Mr Smith is Brakeman's next door neighbour.

SH

- Mr Smith lives halfway between Detroit and Chicago.

SC

- Mr Smith lives in Chicago.

RD

- Mr Robinson lives in Detroit.

RC

- Mr Robinson lives in Chicago.

JC

- Mr Jones lives in Chicago.

JB

- Mr Jones is the brakeman.


A
xioms:

Required to Prove: JB


Result: Mr Robinson or Mr Jones live in Chicago.

Result: Mr Smith doesn't live in Chicago.

Result: Mr Smith lives halfway between Detroit and Chicago.





Result: Mr Jones is the Brakeman.
Quad Erat Demonstrandum - It is proven!

Result: Therefore Mr Jones lives in Chicago.

Result: Mr Robinson doesn't live in Chicago.


Question 5
Show by a resolution refutation that the following formulas is a tautology:

(P  Q)  [(R v P)  (R v Q)]



First must expand into clausal form:



N
ow negate the whole expression, ready to perform resolution:


N







ow take each term and perform resolution:












nil

The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be a tautology. Quad Erat Demonstrandum.




Question 6

Represent the following English sentences using predicate calculus:




  1. Every chicken hatched from an egg.

x y ( ( chicken(x)  egg(y) )  hatchedFrom(x,y) )

or simply: x y ( hatchedFrom(x,y) )


  1. Someone profited from the Great Depression.

x ( person(x)  profitedFrom(x,GreatDepression) )

or simply: x ( profitedFrom(x,GreatDepression) )


  1. Some language is spoken by everyone in this room.

y x ( ( language(y)  person(x)  inThisRoom(x) )  spoke(x,y) )

or simply: y x ( inThisRoom(x)  spoke(x,y) )


  1. One of the coats in the closet belongs to Sarah.

x ( coat(x)  inCloset(x)  belongsTo(Sarah) )




  1. All people are created equal.

X Y ([person(x)  person(y)  xy]  createdEqual(x,y) )





  1. Everybody loves somebody sometime.

x y t ( ( person(x)  person(y)  time(t) )  loves(x,y,t) )





  1. An apple a day keeps the doctor away.

d ( (day(d)  a (apple(a)  eat(a,d) ))  t visitDoctor(x,t) )



Question 7

Prove the validity of the following wff using the method of resolution refutation:

X Y [P(f(X))  Q(f(B))]  [P(f(A))  P(Y)  Q(Y)]
Convert the WFF to a clause:


  1. Eliminate "" and "".

X Y [P(f(X))  Q(f(B))]  [P(f(A))  P(Y)  Q(Y)]




  1. Move "" in as far as possible.

X Y [P(f(X))  Q(f(B))]  [P(f(A))  P(Y)  Q(Y)]

X Y [P(f(X))  Q(f(B))]  [P(f(A))  P(Y)  Q(Y)]

X Y P(f(X))  Q(f(B))  [P(f(A))  P(Y)  Q(Y)]




  1. Eliminate "".

Let X equal a constant "x" and Y equal a constant "f(x)".


P(f(x))  Q(f(B))  [P(f(A))  P(f(x))  Q(f(x))]


  1. Eliminate "". - No need.




  1. Put into Clausal form. - No need.

The final statement in clausal form: P(f(x))  Q(f(B))  [P(f(A))  P(y)  Q(y)].

Now negate the clause for resolution:

{P(f(x))  Q(f(B))  [P(f(A))  P(f(x))  Q(f(x))]} =

{P(f(x))  Q(f(B))  [P(f(A))  P(f(x))  Q(f(x))]} =

{P(f(x1))  Q(f(B))  [P(f(A))  P(f(x2))  Q(f(x2))]}


Resolution:


P(f(x1))



Q(f(B))

P(f(A))  P(f(x2))  Q(f(x2))



{x2/B}


P(f(A))  P(f(B))



{x1/B}

P(f(A))



The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be valid.

Quad Erat Demonstrandum.




{x1/A}



nil

Question 8


Prove using resolution refutation that Fido will die, given the axioms:



  1. Fido is a dog.

  2. All dogs are animals.

  3. All animals will die.



Axioms:


  1. dog(Fido).

  2. X dog(X)  animal(X).

  3. X animal(X)  dies(X).


Required to prove: dies(Fido)
So negate the goal and try to make a contradiction. Therefore add " dies(Fido)" to the list of axioms and begin resolution:
Final (clausal) list of axioms:


  1. dog(Fido).

  2. dog(X1)  animal(X1).

  3. animal(X2)  dies(X2).

  4. dies(Fido).


Resolution:


dog(Fido)



dog(X1)  animal(X1)

animal(X1)  dies(X1)

dies(Fido)


{X2/X1}



dog(X1)  dies(X1)



{X1/Fido}

dog(Fido)





nil

The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.

Question 9

Anyone passing his or her CSE1303 exam and winning the lottery is happy. But anyone who studies or is lucky can pass all his or her exams. Mary did not study but she is lucky. Anyone who is lucky wins the lottery. Is Mary happy? Use resolution refutation to prove your answer.


Represent the axioms in predicate calculus:


  1. X ([pass(X, CSE1303)  win(X, lotto)]  happy(X))

  2. X Y ([studies(X)  lucky(X)]  pass(X, Y))

  3. studies(Mary)

  4. lucky(Mary)

  5. X (lucky(X)  win(X, lotto))


Convert axioms to clauses:


1.

Eliminate 

Convert to CNF

Eliminate 


X [pass(X, CSE1303)  win(X, lotto)]  happy(X)

X pass(X, CSE1303)  win(X, lotto)  happy(X)

pass(X, CSE1303)  win(X, lotto)  happy(X)


2.

Eliminate 

Convert to CNF


Eliminate 

and split.



X Y ([studies(X)  lucky(X)]  pass(X, Y))

X Y ([studies(X)  lucky(X)]  pass(X, Y))

X Y ([studies(X)  pass(X, Y)]  [lucky(X)  pass(X, Y)])

2.1. studies(X)  pass(X, Y)

2.2. lucky(X)  pass(X, Y)


3.

Nothing to do.

studies(Mary)

4.

Nothing to do.

lucky(Mary)

5.

Eliminate 

Eliminate 



X (lucky(X)  win(X, lotto))

lucky(X)  win(X, lotto)





And we wish to prove: happy(Mary)

So negate the goal and try to make a contradiction. Therefore add "happy(Mary)" to the list of axioms.


Final list of axioms: (with variables renamed)


  1. pass(X1, CSE1303)  win(X1, lotto)  happy(X1)

  2. studies(X2)  pass(X2, Y1)

  3. lucky(X3)  pass(X3, Y2)

  4. studies(Mary)

  5. lucky(Mary)

  6. lucky(X4)  win(X4, lotto)

  7. happy(Mary)

pass(X1, CSE1303) 

win(X1, lotto)  happy(X1)

studies(X2) 

pass(X2, Y1)



lucky(X3) 

pass(X3, Y2)



studies(Mary)

lucky(Mary)

lucky(X4)  win(X4, lotto)

happy(Mary)



{X1/Mary}

{X4/Mary}

{X3/Mary}


pass(Mary, CSE1303) 

win(Mary, lotto)

win(Mary, lotto)

pass(Mary, Y2)





{Y2/CSE1303}


win(Mary, lotto)



nil


The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.


Question 10

All people who are not poor and are smart are happy. Those people who read are not stupid. John can read and is wealthy. Happy people have exciting lives. Can anyone be found with an exciting life? Use resolution refutation to prove your answer.


Represent the axioms in predicate calculus:


  1. X ([poor(X)  stupid(X)]  happy(X))

  2. X (reads(X)  stupid(X))

  3. reads(John)

  4. poor(John)

  5. X (happy(X)  exciting(life, X))


Convert axioms to clauses:


1.

Eliminate 

Convert to CNF

Eliminate 


X ( [poor(X)  stupid(X)]  happy(X))

X (poor(X)  stupid(X)  happy(X))

poor(X)  stupid(X)  happy(X)


2.

Eliminate 

Eliminate 



X (reads(X)  stupid(X))

reads(X)  stupid(X)



3.

Nothing to do.

reads(John)

4.

Nothing to do.

poor(John)

5.

Eliminate 

Eliminate 



X (happy(X)  exciting(life, X))

happy(X)  exciting(life, X)





And we wish to prove: X exciting(life, X)

So negate the goal and try to make a contradiction. Therefore add "exciting(life, X)" to the list of axioms.


Final list of axioms: (renamed variables)


  1. poor(X1)  stupid(X1)  happy(X1)

  2. reads(X2)  stupid(X2)

  3. reads(John)

  4. poor(John)

  5. happy(X3)  exciting(life, X3)

  6. exciting(life, X4)

poor(X1)  stupid(X1)  happy(X1)



reads(X2)  stupid(X2)

reads(John)

poor(John)

happy(X3)  exciting(life, X3)

exciting(life, X4)



{X2/John}


{X1/John}



{X4/X3}

stupid(John)



happy(X3)




{X3/John}

poor(John)  happy(John)





happy(John)






nil

The negation of the statement we're trying to prove has evaluated to nil , therefore the inverse (the original statement) must be true. Quad Erat Demonstrandum.




Page


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə