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