Transcript Document

Notes on Assignment 3
Foundations of Artificial Intelligence
English to FOPC
(Similar to Assignment 3 - Problem 2)
Not all students take both History and Biology
~ "x student(x) => (takes(x, hist) /\ takes(x, bio))
or alternatively
$x student(x) /\ ~(takes(x, hist) /\ takes(x, bio))
Only one student failed History
$x student(x) /\ fails(x, hist)
/\ ( "y student(y) /\ fails(y, hist) => x = y
Foundations of Artificial Intelligence
2
Forward Chaining Proof – Example
(Similar to Assingment 3 - Problem 1)
KB1: (A \/ B) => E
KB2: ~D \/ C
KB3: D /\ C => A
KB4: D
Give a derivation (proof) for the sentence E.
1.
2.
3.
4.
5.
6.
D
C
D /\ C
A
A \/ B
E
Foundations of Artificial Intelligence
KB4
Step 1, KB2, using Resolution rule
Step 1, Step 2, using AND-Introduction
Step 3, KB3, using Modus Ponens
Step 4, using OR-Introduction (introducing B)
Step 5, KB1, using Modus Ponens
3
Similar to Assignment 3 - Problem 1
(resolution-refutation)
 Can we do this using resolution-refutation?
 First need to convert everything into clause form
KB1:
KB2:
KB3:
KB4:
(A \/ B) => E
~D \/ C
D /\ C => A
D
KB1.1:
KB1.2:
KB2:
KB3:
KB4:
~A \/ E
~B \/ E
~D \/ C
~D \/ ~C \/ A
D
 Next we need to negate the sentence to be proved and convert to clause form:
E
~E
Initial subgoal for resolution
Foundations of Artificial Intelligence
4
Similar to Assignment 3 - Problem 1
(resolution-refutation)
KB1.1:
KB1.2:
KB2:
KB3:
KB4:
~A \/ E
~B \/ E
~D \/ C
~D \/ ~C \/ A
D
Subgoal
Resolve with
~E
KB1.1: ~A \/ E
~A
KB3: ~D \/ ~C \/ A
~D \/ ~C
~C
~D
KB4:
D
KB2: ~D \/ C
KB4:
D
X
Foundations of Artificial Intelligence
5
Resolution Example
(Assignment 3 - Problem 3)
 John likes all kinds of food.
 Apples are food.
 Chicken is food.
 Anything anyone eats and isn't killed by is food.
 Bill eats peanuts and is still alive.
 Anyone who is killed by anything is not alive.
 Sue eats everything Bill eats.







"x food(x) => likes(john, x)
food(apple)
food(chicken)
"x "y eats(x, y) /\ ~killed-by(x, y) => food(y)
eats(bill, peanuts) /\ alive(bill)
"x "y killed-by(x, y) => ~alive(x)
"x eats(bill, x) => eats(sue, x)
Foundations of Artificial Intelligence
6
Resolution Example
(Assignment 2 - Problem 5)
 "x food(x) => likes(john, x)
 food(apple)
 food(chicken)
 "x "y eats(x, y) /\ ~killed-by(x, y) => food(y)
 eats(bill, peanuts) /\ alive(bill)
 "x "y killed-by(x, y) => ~alive(x)
 "x eats(bill, x) => eats(sue, x)
Clausal Form
Foundations of Artificial Intelligence
1. ~food(x) \/ likes(john, x)
2. food(apple)
3. food(chicken)
4. ~eats(x, y) \/ killed-by(x, y) \/ food(y)
5a. eats(bill, peanuts)
5b. alive(bill)
6. ~killed-by(x,y) \/ ~alive(x)
7. ~eats(bill, x) \/ eats(sue, x)
7
Resolution Example
(Assignment 2 - Problem 5)
1. ~food(x) \/ likes(john, x)
2. food(apple)
3. food(chicken)
4. ~eats(x, y) \/ killed-by(x, y) \/ food(y)
5a. eats(bill, peanuts)
5b. alive(bill)
6. ~killed-by(x,y) \/ ~alive(x)
7. ~eats(bill, x) \/ eats(sue, x)
Prove that
john likes peanuts:
resolve with (to get) subgoal (resolvant)
(1)
(4)
(5a)
(6)
(5b)
Foundations of Artificial Intelligence
~likes(john, peanuts)
~food(peanuts)
~eats(x, peanuts) \/ killed-by(x, peanuts)
killed-by(bill, peanuts)
~alive(bill)
Empty caluse
8
Resolution Example
(Assignment 3 -Problem 3)
1. ~food(x) \/ likes(john, x)
2. food(apple)
3. food(chicken)
4. ~eats(x, y) \/ killed-by(x, y) \/ food(y)
5a. eats(bill, peanuts)
5b. alive(bill)
6. ~killed-by(x,y) \/ ~alive(x)
7. ~eats(bill, x) \/ eats(sue, x)
What food does sue eat?
( i.e., $x food(x) /\ eats(sue, x)? )
$x food(x) /\ eats(sue, x)
negate
~($x food(x) /\ eats(sue, x))
This can be resolved with
candidate clauses 2, 3, and 4
Convert to clause form
~food(x) \/ ~eats(sue, x))
Foundations of Artificial Intelligence
9
English to FOPC
(Similar to Assignment 3 - Problem 2)
Not all students take both History and Biology
~ "x student(x) => (takes(x, hist) /\ takes(x, bio))
or alternatively
$x student(x) /\ ~(takes(x, hist) /\ takes(x, bio))
Only one student failed History
$x student(x) /\ fails(x, hist)
/\ ( "y student(y) /\ fails(y, hist) => x = y
Foundations of Artificial Intelligence
10