First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

First-Order Logic
Introduction to Articial Intelligence Steven Bethard
Department of Computer Science University of Colorado

CSCI 3202

1 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Outline
1

First Order Logic Motivation Core Components Quantiers Example Translations Animal Kingdom Wumpus World Harry Potter First-Order Logic Inference Propositionalization Unication Inference Algorithms Forward Chaining Backward Chaining Prolog Resolution
2 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Outline
1

First Order Logic Motivation Core Components Quantiers Example Translations Animal Kingdom Wumpus World Harry Potter First-Order Logic Inference Propositionalization Unication Inference Algorithms Forward Chaining Backward Chaining Prolog Resolution
3 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Whats Wrong with Propositional Logic?

Translate: All squares adjacent to pits are breezy

4 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Whats Wrong with Propositional Logic?

Translate: All squares adjacent to pits are breezy Problem: Propositional Logic B1,1 (P1,2 P2,1 ) B1,2 (P1,1 P2,2 P1,3 ) B2,1 (P1,1 P2,2 P2,1 ) ...

4 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Whats Wrong with Propositional Logic?

Translate: All squares adjacent to pits are breezy Problem: Propositional Logic B1,1 (P1,2 P2,1 ) B1,2 (P1,1 P2,2 P1,3 ) B2,1 (P1,1 P2,2 P2,1 ) ... Solution: First Order Logic (Preview) s Breezy(s) r Adjacent(r , s) Pit(r )
4 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Core Ideas of First Order Logic

Propositional Logic World consists of facts All facts are either true or false

5 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Core Ideas of First Order Logic

Propositional Logic World consists of facts All facts are either true or false First Order Logic World consists of objects and relations Statements that a relation R holds between objects X1 , . . . , Xn are either true or false

5 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Core Ideas of First Order Logic

Propositional Logic World consists of facts All facts are either true or false First Order Logic World consists of objects and relations Statements that a relation R holds between objects X1 , . . . , Xn are either true or false Objects people, numbers, houses, colors, years. . . Relations blonde, round, prime, multi-storied. . . brother-of, comes-between, has-color, after. . .
5 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Constants
Key Idea Constants represent named objects in the world Examples RichardTheLionheart RonaldMcDonald Blue 42 12pm

6 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Functions
Key Idea Functions relate object(s) to exactly one other object Examples LeftLegOf(x ) LengthOf(x ) SquareRoot(x ), Sum(x , y ), Intersection(x , y ), i.e. x i.e. x + y i.e. x y

7 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Predicates
Key Idea Predicates describe relations between objects (or a property of a single object) Examples Person(x ) Female(x ) BrotherOf(x , y ) Positive(x ), i.e. x > 0 MemberOf(x , y ), i.e. x y SubsetOf(x , y ), i.e. x y
8 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Connectives
Connectives in First-Order Logic Used to construct more complex sentences Semantics match those of Propositional Logic Examples Brother(LeftLeg(Richard), John) Positive(42) LessThan(42, 100) Male(Pat) Female(Pat ) LaysEggs(Whale) Bird(Whale)

9 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Truth in First Order Logic

Key Ideas Relations are (possibly innite) sets of tuples R(Term1 , . . . , Termn ) is true iff Term1 , . . . , Termn R Example Given the relation: SquareRoot = { 1, 1 , 4, 2 , 9, 3 , . . .}

10 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Truth in First Order Logic

Key Ideas Relations are (possibly innite) sets of tuples R(Term1 , . . . , Termn ) is true iff Term1 , . . . , Termn R Example Given the relation: SquareRoot = { 1, 1 , 4, 2 , 9, 3 , . . .} Then SquareRoot(4, 2) is

10 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Truth in First Order Logic

Key Ideas Relations are (possibly innite) sets of tuples R(Term1 , . . . , Termn ) is true iff Term1 , . . . , Termn R Example Given the relation: SquareRoot = { 1, 1 , 4, 2 , 9, 3 , . . .} Then SquareRoot(4, 2) is true because 4, 2 SquareRoot

10 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Truth in First Order Logic

Key Ideas Relations are (possibly innite) sets of tuples R(Term1 , . . . , Termn ) is true iff Term1 , . . . , Termn R Example Given the relation: SquareRoot = { 1, 1 , 4, 2 , 9, 3 , . . .} Then SquareRoot(4, 2) is true because 4, 2 SquareRoot And SquareRoot(2, 2) is

10 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Truth in First Order Logic

Key Ideas Relations are (possibly innite) sets of tuples R(Term1 , . . . , Termn ) is true iff Term1 , . . . , Termn R Example Given the relation: SquareRoot = { 1, 1 , 4, 2 , 9, 3 , . . .} Then SquareRoot(4, 2) is true because 4, 2 SquareRoot And SquareRoot(2, 2) is false because 2, 2 SquareRoot
10 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Quantiers
Predicating over Constants If I know: LaysEggs(Whale) Bird(Whale) What can I say here? LaysEggs(Steve) ?

11 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Quantiers
Predicating over Constants If I know: LaysEggs(Whale) Bird(Whale) What can I say here? LaysEggs(Steve) ? Nothing!

11 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Quantiers
Predicating over Constants If I know: LaysEggs(Whale) Bird(Whale) What can I say here? LaysEggs(Steve) ? Nothing! Quantiers and Variables Quantiers allow statements about classes of objects, e.g. x LaysEggs(x ) Bird(x )
11 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication ()
Denition x P is true in model m iff: P is true when we bind x to each of the objects in m

12 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication ()
Denition x P is true in model m iff: P is true when we bind x to each of the objects in m Example So x Bird(x ) LaysEggs(x ) is true because: Bird(Swallow) LaysEggs(Swallow) is true Bird(Emu) LaysEggs(Emu) is true Bird(Badger) LaysEggs(Badger) is true ...

12 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication ()
Denition x P is true in model m iff: P is true when we bind x to each of the objects in m Example So x Bird(x ) LaysEggs(x ) is true because: Bird(Swallow) LaysEggs(Swallow) is true Bird(Emu) LaysEggs(Emu) is true Bird(Badger) LaysEggs(Badger) is true ... But x LaysEggs(x ) Bird(x ) is false because:
12 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication ()
Denition x P is true in model m iff: P is true when we bind x to each of the objects in m Example So x Bird(x ) LaysEggs(x ) is true because: Bird(Swallow) LaysEggs(Swallow) is true Bird(Emu) LaysEggs(Emu) is true Bird(Badger) LaysEggs(Badger) is true ... But x LaysEggs(x ) Bird(x ) is false because: LaysEggs(Platypus) Bird(Platypus) is false
12 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication in Translation

Common Mistake What does this mean? x Bird(x ) LaysEggs(x )

13 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication in Translation

Common Mistake What does this mean? x Bird(x ) LaysEggs(x ) Answer: Everything is a bird and everything lays eggs Intended statement: x Bird(x ) LaysEggs(x )

13 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Universal Quantication in Translation

Common Mistake What does this mean? x Bird(x ) LaysEggs(x ) Answer: Everything is a bird and everything lays eggs Intended statement: x Bird(x ) LaysEggs(x ) Rule of Thumb Use implication () with universal quantication ()

13 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication
Denition x P is true in model m iff: P is true when we bind x to any of the objects in m

14 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication
Denition x P is true in model m iff: P is true when we bind x to any of the objects in m Example So x Mammal(x ) LaysEggs(x ) is true because:

14 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication
Denition x P is true in model m iff: P is true when we bind x to any of the objects in m Example So x Mammal(x ) LaysEggs(x ) is true because: Mammal(Platypus) LaysEggs(Platypus) is true

14 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication
Denition x P is true in model m iff: P is true when we bind x to any of the objects in m Example So x Mammal(x ) LaysEggs(x ) is true because: Mammal(Platypus) LaysEggs(Platypus) is true But x Mammal(x ) Animal(x ) is false because:

14 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication
Denition x P is true in model m iff: P is true when we bind x to any of the objects in m Example So x Mammal(x ) LaysEggs(x ) is true because: Mammal(Platypus) LaysEggs(Platypus) is true But x Mammal(x ) Animal(x ) is false because: Mammal(Person) Animal(Person) is false Mammal(Platypus) Animal(Platypus) is false Mammal(Spam) Animal(Spam) is false ...
14 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication in Translation

Common Mistake What does this mean? x Mammal(x ) LaysEggs(x )

15 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication in Translation

Common Mistake What does this mean? x Mammal(x ) LaysEggs(x ) Answer: There is something that is not a mammal or lays eggs Intended statement: x Mammal(x ) LaysEggs(x )

15 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Existential Quantication in Translation

Common Mistake What does this mean? x Mammal(x ) LaysEggs(x ) Answer: There is something that is not a mammal or lays eggs Intended statement: x Mammal(x ) LaysEggs(x ) Rule of Thumb Use conjunction () with existential quantication ()

15 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Quantier Properties
Nesting Quantiers Mixed quantiers cannot be exchanged: x y Loves(x , y ) everyone loves someone x y Loves(x , y ) one person is loved by everyone

16 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Quantier Properties
Nesting Quantiers Mixed quantiers cannot be exchanged: x y Loves(x , y ) everyone loves someone x y Loves(x , y ) one person is loved by everyone Relation between and Conversion is roughly like DeMorgans: x Enjoys(x , AI) x Enjoys(x , AI) x Enjoys(x , DB) x Enjoys(x , DB)

16 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Equality Relations
Problem Whats wrong with this denition? x , y Sibling(x , y ) p Parent(p, x ) Parent(p, y )

17 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Equality Relations
Problem Whats wrong with this denition? x , y Sibling(x , y ) p Parent(p, x ) Parent(p, y ) Both x and y can be the same thing! Sibling(Steve, Steve)

17 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Motivation Core Components Quantiers

Equality Relations
Problem Whats wrong with this denition? x , y Sibling(x , y ) p Parent(p, x ) Parent(p, y ) Both x and y can be the same thing! Sibling(Steve, Steve) Solution: Equality Specify when two variables refer to the same objects: x , y Sibling(x , y ) x = y p Parent(p, x ) Parent(p, y )
17 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Outline
1

First Order Logic Motivation Core Components Quantiers Example Translations Animal Kingdom Wumpus World Harry Potter First-Order Logic Inference Propositionalization Unication Inference Algorithms Forward Chaining Backward Chaining Prolog Resolution
18 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x )

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x )

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x )

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x )

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x ) Animals that y have wings

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x ) Animals that y have wings x Animal(x ) Flies(x ) HasWings(x )

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x ) Animals that y have wings x Animal(x ) Flies(x ) HasWings(x ) Not all swimming animals have ns

19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x ) Animals that y have wings x Animal(x ) Flies(x ) HasWings(x ) Not all swimming animals have ns x Animal(x ) Swim(x ) HasFins(x )
19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

All horses are mammals x Horse(x ) Mammal(x ) All birds have wings x Bird(x ) HasWings(x ) Some mammals lay eggs x Mammal(x ) LaysEggs(x ) Some birds dont y x Bird(x ) Flies(x ) Animals that y have wings x Animal(x ) Flies(x ) HasWings(x ) Not all swimming animals have ns x Animal(x ) Swim(x ) HasFins(x ) x Animal(x ) Swim(x ) HasFins(x )
19 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

An animal gives birth to animals of the same species

20 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

An animal gives birth to animals of the same species x , y Animal(x ) GivesBirth(x , y ) Animal(y ) Species(x ) = Species(y ) x = y

20 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

An animal gives birth to animals of the same species x , y Animal(x ) GivesBirth(x , y ) Animal(y ) Species(x ) = Species(y ) x = y Bats have exactly two wings

20 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Animal Kingdom Translations

An animal gives birth to animals of the same species x , y Animal(x ) GivesBirth(x , y ) Animal(y ) Species(x ) = Species(y ) x = y Bats have exactly two wings x Bat(x ) y , z HasWing(x , y ) HasWing(x , z ) y = z w HasWing(x , w ) w = y w = z

20 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1]

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1])

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2]

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2] Home(Wumpus) = [2, 2]

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2] Home(Wumpus) = [2, 2] If you are in the Wumpuss square, he eats you

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2] Home(Wumpus) = [2, 2] If you are in the Wumpuss square, he eats you t Location(Agent, Home(Wumpus), t ) HasEaten(Wumpus, Agent, t )

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2] Home(Wumpus) = [2, 2] If you are in the Wumpuss square, he eats you t Location(Agent, Home(Wumpus), t ) HasEaten(Wumpus, Agent, t ) You should grab the gold when you are in its square

21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

There is a breeze in [3, 1] Breezy([3, 1]) The Wumpus is lives in [2, 2] Home(Wumpus) = [2, 2] If you are in the Wumpuss square, he eats you t Location(Agent, Home(Wumpus), t ) HasEaten(Wumpus, Agent, t ) You should grab the gold when you are in its square s, t HasGold(s) Location(Agent, s, t ) BestAction(Grab, Agent, t )
21 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

Diagnostic Rules From effect, determine cause: y Breezy(y ) (x Pit(x ) Adjacent(x , y ))

22 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

Diagnostic Rules From effect, determine cause: y Breezy(y ) (x Pit(x ) Adjacent(x , y )) Causal Rules From cause, determine effect: x , y (Pit(x ) Adjacent(x , y )) Breezy(y )

22 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Wumpus World Translations

Diagnostic Rules From effect, determine cause: y Breezy(y ) (x Pit(x ) Adjacent(x , y )) Causal Rules From cause, determine effect: x , y (Pit(x ) Adjacent(x , y )) Breezy(y ) Denition Rules Bidirectional: y Breezy(y ) (x Pit(x ) Adjacent(x , y ))
22 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Harry Potters 7 Potions Puzzle

Danger lies before you, while safety lies behind, Two of us will help you, whichever you would nd. One among us seven will let you move ahead, Another will transport the drinker back instead. Two among our number hold only nettle wine, Three of us are killers, waiting hidden in line. Choose, unless you wish to stay here forevermore, To help you in your choice, we give you these clues four: First, however slyly the poison tries to hide You will always nd some on nettle wines left side; Second, different are those who stand at either end, But if you would move forward, niether is your friend; Third, as you see clearly, all are different size, Neither dwarf nor giant holds death in their insides; Fourth, the second left and second on the right Are twins once you taste them, though different at rst sight.
23 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

One Harry Potters 7 Potions Solution

p Potions(p) Permutation(p, [Forward, Backward, Wine, Wine, Poison, Poison, Poison]) PoisonIsLeftOfWine(p) EndsAreDifferent(p) EndsAreNotForward(p) SmallestIsNotPoison(p) LargestIsNotPoison(p) SecondsAreTheSame(p) ...

24 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

One Harry Potters 7 Potions Solution

p Potions(p) Permutation(p, [Forward, Backward, Wine, Wine, Poison, Poison, Poison]) PoisonIsLeftOfWine(p) EndsAreDifferent(p) EndsAreNotForward(p) SmallestIsNotPoison(p) LargestIsNotPoison(p) SecondsAreTheSame(p) ... p EndsAreDifferent(p) p1 , p2 , . . . , p7 p = [p1 , p2 , p3 , p4 , p5 , p6 , p7 ] p1 = p7 ...

24 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

One Harry Potters 7 Potions Solution

p Potions(p) Permutation(p, [Forward, Backward, Wine, Wine, Poison, Poison, Poison]) PoisonIsLeftOfWine(p) EndsAreDifferent(p) EndsAreNotForward(p) SmallestIsNotPoison(p) LargestIsNotPoison(p) SecondsAreTheSame(p) ... p EndsAreDifferent(p) p1 , p2 , . . . , p7 p = [p1 , p2 , p3 , p4 , p5 , p6 , p7 ] p1 = p7 ... p LargestIsNotPoison(p) pi Largest(p, pi ) pi = Poison
24 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Animal Kingdom Wumpus World Harry Potter

Prolog Demo

25 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Outline
1

First Order Logic Motivation Core Components Quantiers Example Translations Animal Kingdom Wumpus World Harry Potter First-Order Logic Inference Propositionalization Unication Inference Algorithms Forward Chaining Backward Chaining Prolog Resolution
26 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Universal Instantiation
Key Idea If we know x P (x ), then we can conclude: P (Badger) P (Spam) ...

27 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Universal Instantiation
Key Idea If we know x P (x ), then we can conclude: P (Badger) P (Spam) ... Formal Rule Given a ground term g : v S UBST({v /g }, )
27 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Existential Instantiation
Key Idea If we know x P (x ), then we can just give a name to x : P (ThingThatPIsTrueFor) This works as long as the name isnt already in use

28 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Existential Instantiation
Key Idea If we know x P (x ), then we can just give a name to x : P (ThingThatPIsTrueFor) This works as long as the name isnt already in use Formal Rule Given a constant k that is not in the knowledge base: v S UBST({v /k }, ) The constant k is called a Skolem constant
28 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile)

29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile) Propositional Logic

29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile) Propositional Logic Mammal(EggLayer) LaysEggs(EggLayer)

29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile) Propositional Logic Mammal(EggLayer) LaysEggs(EggLayer) Mammal(Platypus) WarmBlooded(Platypus) Mammal(Crocodile) WarmBlooded(Crocodile)

29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile) Propositional Logic Mammal(EggLayer) LaysEggs(EggLayer) Mammal(Platypus) WarmBlooded(Platypus) Mammal(Crocodile) WarmBlooded(Crocodile) Mammal(Platypus)
29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Reduction to Propositional Logic

First-Order Logic x Mammal(x ) LaysEggs(x ) x Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Crocodile) Propositional Logic Mammal(EggLayer) LaysEggs(EggLayer) Mammal(Platypus) WarmBlooded(Platypus) Mammal(Crocodile) WarmBlooded(Crocodile) Mammal(Platypus) WarmBlooded(Crocodile)
29 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Simple Approach Remove and Treat all rst-order terms as simple symbols Solve using resolution for propositional logic

30 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Simple Approach Remove and Treat all rst-order terms as simple symbols Solve using resolution for propositional logic Example: WarmBlooded(Platypus)? WarmBlooded(Platypus) Mammal(Platypus) WarmBlooded(Platypus) Mammal(Platypus) Mammal(Platypus) false
30 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Problem: Innite Terms Mammal(Steve) Mammal(Mother(Steve)) Mammal(Mother(Mother(Steve))) ...

31 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Problem: Innite Terms Mammal(Steve) Mammal(Mother(Steve)) Mammal(Mother(Mother(Steve))) ... Solution: Iterative Deepening Try proof with terms up to depth 1 Try proof with terms up to depth 2 ...

31 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Problem: Innite Terms Mammal(Steve) Mammal(Mother(Steve)) Mammal(Mother(Mother(Steve))) ... Solution: Iterative Deepening Try proof with terms up to depth 1 Try proof with terms up to depth 2 ... Proof found if exists
31 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Problem: Innite Terms Mammal(Steve) Mammal(Mother(Steve)) Mammal(Mother(Mother(Steve))) ... Solution: Iterative Deepening Try proof with terms up to depth 1 Try proof with terms up to depth 2 ... Proof found if exists, else innite loop
31 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Simple First-Order Inference

Problem: Innite Terms Mammal(Steve) Mammal(Mother(Steve)) Mammal(Mother(Mother(Steve))) ... Solution: Iterative Deepening Try proof with terms up to depth 1 Try proof with terms up to depth 2 ... Proof found if exists, else innite loop (semidecidable)
31 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Problems with Propositionalization

Prove: WarmBlooded(Scooby) Dog(Scooby) Dog(Scrappy) x Dog(x ) Mammal(x ) y Mammal(y ) WarmBlooded(y ) Problem: Many Irrelevant Facts Produced Dog(Scrappy) Dog(Scrappy) Mammal(Scrappy) Mammal(Scrappy) WarmBlooded(Scrappy)
32 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q )

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves)

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves) {y =Leaves}

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves) {y =Leaves} Eats(Panda, y ) Eats(x , Pizza)

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves) {y =Leaves} Eats(Panda, y ) Eats(x , Pizza) {x =Panda, y =Pizza}

33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves) {y =Leaves} Eats(Panda, y ) Eats(x , Pizza) {x =Panda, y =Pizza} Eats(Panda, y ) Eats(x , FavFood(x ))
33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Propositionalization Unication

Unication
Key Idea Assign variables to make two expressions look the same Formally U NIFY(p, q ) = where S UBST(, p) = S UBST(, q ) Example: Eats(Panda, y )?
p q Eats(Panda, y ) Eats(Panda, Leaves) {y =Leaves} Eats(Panda, y ) Eats(x , Pizza) {x =Panda, y =Pizza} Eats(Panda, y ) Eats(x , FavFood(x )) {x =Panda, y =FavFood(Panda)}
33 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Outline
1

First Order Logic Motivation Core Components Quantiers Example Translations Animal Kingdom Wumpus World Harry Potter First-Order Logic Inference Propositionalization Unication Inference Algorithms Forward Chaining Backward Chaining Prolog Resolution
34 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Generalized Modus Ponens

Denition p1 p2 ... pn p1 p2 . . . pn q U NIFY(p1 , p1 ) = U NIFY(p2 , p2 ) = ... U NIFY(pn , pn ) = S UBST(, q )
35 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Generalized Modus Ponens

Denition p1 p2 ... pn p1 p2 . . . pn q U NIFY(p1 , p1 ) = U NIFY(p2 , p2 ) = ... U NIFY(pn , pn ) = S UBST(, q ) Example Odd(17) x Odd(x ) Mod(x , 2, 1) U NIFY(Odd(17), Odd(x )) = {x = 17} Mod(17, 2, 1)

35 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining
Key Ideas Repeatedly apply Generalized Modus Ponens Stop when nothing new can be inferred

36 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining
Key Ideas Repeatedly apply Generalized Modus Ponens Stop when nothing new can be inferred Details KB must be only rst-order denite clauses, one of: Atomic clauses, e.g. Mammal(Platypus) Implications like p1 p2 . . . pn q

36 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Code

def forward_chaining(knowledge_base, query):

37 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Code

def forward_chaining(knowledge_base, query): # keep adding to the KB until no new sentences are generated new = True while sentences: new = set() for sentence in knowledge_base:

37 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Code

def forward_chaining(knowledge_base, query): # keep adding to the KB until no new sentences are generated new = True while sentences: new = set() for sentence in knowledge_base: # find something that unifies with the sentence body n = len([Link]) for subset in all_subsets(knowledge_base, n): assignment = unify(subset, [Link]) if assignment is not None:

37 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Code

def forward_chaining(knowledge_base, query): # keep adding to the KB until no new sentences are generated new = True while sentences: new = set() for sentence in knowledge_base: # find something that unifies with the sentence body n = len([Link]) for subset in all_subsets(knowledge_base, n): assignment = unify(subset, [Link]) if assignment is not None: # conclude the sentence head head = [Link]([Link]) if head not in knowledge_base + new: [Link](head)

37 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Code

def forward_chaining(knowledge_base, query): # keep adding to the KB until no new sentences are generated new = True while sentences: new = set() for sentence in knowledge_base: # find something that unifies with the sentence body n = len([Link]) for subset in all_subsets(knowledge_base, n): assignment = unify(subset, [Link]) if assignment is not None: # conclude the sentence head head = [Link]([Link]) if head not in knowledge_base + new: [Link](head) # return if the query is concluded result = unify(head, query) if result is not None: return result knowledge_base.update(new)
37 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Example

If youre rich and someone sells something you want, you buy it Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) If youre hot, you want ice cream Hot(x ) IceCream(y ) Wants(x , y ) Glacier sells all kinds of ice cream IceCream(y ) Sells(Glacier, y ) One avor of ice cream is mint IceCream(Mint) Bill is rich Rich(Bill) Bill is hot Hot(Bill)
38 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Example

Hot(Bill) IceCream(Mint) Hot(x ) IceCream(y ) Wants(x , y ) Wants(Bill, Mint)

39 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Example

Hot(Bill) IceCream(Mint) Hot(x ) IceCream(y ) Wants(x , y ) Wants(Bill, Mint) IceCream(Mint) IceCream(y ) Sells(Glacier, y ) Sells(Glacier, Mint)

39 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Example

Hot(Bill) IceCream(Mint) Hot(x ) IceCream(y ) Wants(x , y ) Wants(Bill, Mint) IceCream(Mint) IceCream(y ) Sells(Glacier, y ) Sells(Glacier, Mint) Rich(Bill) Wants(Bill, Mint) Sells(Glacier, Mint) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Buys(Bill, Mint)
39 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate:

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts:

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts: pnk

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts: pnk Maximum Iterations:

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts: pnk Maximum Iterations: pnk

40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts: pnk Maximum Iterations: pnk With functions:
40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Forward Chaining Properties

Basic Properties Sound - uses Generalized Modus Ponens Complete - proof similar to propositional logic Works only with denite clauses Termination With no functions, p predicates, n constants, and at most k arguments per predicate: Maximum Facts: pnk Maximum Iterations: pnk With functions: may never terminate
40 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Optimizing Forward Chaining

Indexing Treat facts like database relations Index by predicate + arguments Can get O (1) fact retrieval Standard time/space tradeoffs

41 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Optimizing Forward Chaining

Indexing Treat facts like database relations Index by predicate + arguments Can get O (1) fact retrieval Standard time/space tradeoffs Rule Checking Dont check all rules on each iteration Check rules when new part of premise is satised

41 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining
Key Ideas Start with the terms in the query Look for sentences that can conclude those terms using Generalized Modus Ponens Recurse as necessary to nd simple terms Details KB must be only rst-order denite clauses

42 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment):

43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment): # if all goals have been resolved, generate the assignment if not goals: yield assignment

43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment): # if all goals have been resolved, generate the assignment if not goals: yield assignment # otherwise, check the first goal and then recurse else: term = [Link](goals[0]) for sentence in knowledge_base:

43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment): # if all goals have been resolved, generate the assignment if not goals: yield assignment # otherwise, check the first goal and then recurse else: term = [Link](goals[0]) for sentence in knowledge_base: # try to unify the sentence with the first goal new_assignment = unify([Link], term) if new_assignment is None: continue

43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment): # if all goals have been resolved, generate the assignment if not goals: yield assignment # otherwise, check the first goal and then recurse else: term = [Link](goals[0]) for sentence in knowledge_base: # try to unify the sentence with the first goal new_assignment = unify([Link], term) if new_assignment is None: continue # add the sentences premise to the remaining goals new_goals = list([Link]) new_goals.extend(goals[1:]) new_assignment = new_assignment.compose(assignment)

43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Code

def backward_chaining(knowledge_base, goals, assignment): # if all goals have been resolved, generate the assignment if not goals: yield assignment # otherwise, check the first goal and then recurse else: term = [Link](goals[0]) for sentence in knowledge_base: # try to unify the sentence with the first goal new_assignment = unify([Link], term) if new_assignment is None: continue # add the sentences premise to the remaining goals new_goals = list([Link]) new_goals.extend(goals[1:]) new_assignment = new_assignment.compose(assignment) # recursively search for the remaining goals args = knowledge_base, new_goals, new_assignment for result in backward_chaining(*args): yield result
43 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Given: Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Hot(x ) IceCream(y ) Wants(x , y ) IceCream(y ) Sells(Glacier, y ) IceCream(Mint) Rich(Bill) Hot(Bill) Query: Buys(x , y )

44 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals Assignment

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] Assignment {}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals Assignment [Buys(x , y )] {} [Rich(x ), Wants(x , y ), Sells(z , y )] {}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] Assignment {} {} {x =Bill}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] [Hot(x ), IceCream(y ), Sells(z , y )] Assignment {} {} {x =Bill} {x =Bill}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] [Hot(x ), IceCream(y ), Sells(z , y )] [IceCream(y ), Sells(z , y )] Assignment {} {} {x =Bill} {x =Bill} {x =Bill}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] [Hot(x ), IceCream(y ), Sells(z , y )] [IceCream(y ), Sells(z , y )] [Sells(z , y )] Assignment {} {} {x =Bill} {x =Bill} {x =Bill} {x =Bill, y =Mint}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] [Hot(x ), IceCream(y ), Sells(z , y )] [IceCream(y ), Sells(z , y )] [Sells(z , y )] [IceCream(y )] Assignment {} {} {x =Bill} {x =Bill} {x =Bill} {x =Bill, y =Mint} {x =Bill, y =Mint, z=Glacier}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Example

Goals [Buys(x , y )] [Rich(x ), Wants(x , y ), Sells(z , y )] [Wants(x , y ), Sells(z , y )] [Hot(x ), IceCream(y ), Sells(z , y )] [IceCream(y ), Sells(z , y )] [Sells(z , y )] [IceCream(y )] [] Assignment {} {} {x =Bill} {x =Bill} {x =Bill} {x =Bill, y =Mint} {x =Bill, y =Mint, z=Glacier} {x =Bill, y =Mint, z=Glacier}

45 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Yes, uses Generalized Modus Ponens

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Complete Yes, uses Generalized Modus Ponens

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Yes, uses Generalized Modus Ponens Complete No, could hit innite loops

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Yes, uses Generalized Modus Ponens Complete No, could hit innite loops x by keeping track of goals already seen

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Yes, uses Generalized Modus Ponens Complete No, could hit innite loops x by keeping track of goals already seen Space

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backward Chaining Properties

Properties Sound Yes, uses Generalized Modus Ponens Complete No, could hit innite loops x by keeping track of goals already seen Space Linear in size of proof (depth-rst search)

46 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Prolog
Prolog Overview Backward chaining + many optimizations Millions of logical inferences per second

47 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Prolog
Prolog Overview Backward chaining + many optimizations Millions of logical inferences per second Prolog Syntax Head rst, then body Predicates lowercase, variables uppercase Comma for , semicolon for
factorial(1, 1). factorial(N, _) :- N =< 0, fail. factorial(N, F) :- N > 1, N1 is N - 1, factorial(N1, F1), F is F1 * N.
47 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Prolog Examples

48 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, F ) fail

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, y ) Connected(y , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, y ) Edge(A, B ) Connected(y , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , y ) Connected(y , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , y ) Edge(B , C )
49 / 56

Connected(y , F )

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , C ) Edge(B , C )
49 / 56

Connected(C , F )

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , C ) Edge(B , C ) Connected(C , F ) . . . fail . . .
49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , y ) Connected(y , F )

49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , y ) Edge(B , D )
49 / 56

Connected(y , F )

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , D ) Edge(B , D )
49 / 56

Connected(D , F )

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Backwards Chaining Backtracking

Prove: Connected(A, F ) Given: x , z Edge(x , z ) Connected(x , z ) x , y , z Edge(x , y ) Connected(y , z ) Connected(x , z ) Edge(A, B ) Edge(B , C ) Edge(B , D ) Edge(D , F ) Connected(A, F ) Edge(A, B ) Edge(A, B ) Connected(B , F ) Edge(B , D ) Edge(B , D ) Connected(D , F ) Edge(D , F )
49 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Prolog Example

50 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution
Denition p1 . . . pn q1 . . . qm U NIFY(pi , qj ) = S UBST(, p1 . . . pi 1 pi +1 . . . pn q1 . . . qj 1 qj +1 . . . qm )

51 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution
Denition p1 . . . pn q1 . . . qm U NIFY(pi , qj ) = S UBST(, p1 . . . pi 1 pi +1 . . . pn q1 . . . qj 1 qj +1 . . . qm ) Example Mammal(x ) WarmBlooded(x ) Mammal(Platypus) WarmBlooded(Platypus)
51 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution
Resolution Procedure
1 2 3 4

Convert knowledge base to CNF Convert query to CNF Assume query Apply resolution until false is concluded

52 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution
Resolution Procedure
1 2 3 4

Convert knowledge base to CNF Convert query to CNF Assume query Apply resolution until false is concluded

CNF Complications Negations moved through and All quantiers must have different variable names Quantier scopes handled through skolemization
52 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Given: Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Hot(x ) IceCream(y ) Wants(x , y ) IceCream(y ) Sells(Glacier, y ) IceCream(Mint) Rich(Bill) Hot(Bill) Prove: Buys(x , y )

53 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill)

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y ) Hot(Bill) IceCream(y )

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y ) Hot(Bill) IceCream(y ) IceCream(Mint)

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y ) Hot(Bill) IceCream(y ) IceCream(Mint) Hot(Bill)

54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y ) Hot(Bill) IceCream(y ) IceCream(Mint) Hot(Bill) Hot(Bill)
54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Example
Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Buys(x , y ) Rich(x ) Wants(x , y ) Sells(z , y ) Rich(Bill) Wants(Bill, y ) Sells(z , y ) Hot(x ) IceCream(y ) Wants(x , y ) Hot(Bill) IceCream(y ) Sells(z , y ) IceCream(y ) Sells(Glacier, y ) Hot(Bill) IceCream(y ) IceCream(Mint) Hot(Bill) Hot(Bill) false
54 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Chaining Properties

Properties Sound

55 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Chaining Properties

Properties Sound Yes, uses Resolution

55 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Chaining Properties

Properties Yes, uses Resolution Sound Complete

55 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Chaining Properties

Properties Yes, uses Resolution Sound Complete No, if only binary resolution is used Yes, with factoring to combine uniable literals

55 / 56

First Order Logic Example Translations First-Order Logic Inference Inference Algorithms

Forward Chaining Backward Chaining Prolog Resolution

Resolution Chaining Properties

Properties Yes, uses Resolution Sound Complete No, if only binary resolution is used Yes, with factoring to combine uniable literals Other Properties Requires extra work to retrieve substitutions Can produce useless answers for existential goals

55 / 56

Key Ideas
Translating First-Order Logic Identify objects (terms) and relations (predicates) Generally, use with and with Use inequality to specify unique objects First-Order Logic Inference Forward chaining on denite clauses is sound and complete Backward chaining on denite clauses is sound Resolution is sound and complete
56 / 56