Introduction to
Artificial Intelligence
with Python
Knowledge
knowledge-based agents
agents that reason by operating on internal representations of knowledge
If it didn’t rain, Harry visited Hagrid today.
Harry visited Hagrid or Dumbledore today, but not both. Harry visited Dumbledore today.
Harry did not visit Hagrid today. It rained today.
Logic
sentence
an assertion about the world
in a knowledge representation language
Propositional Logic
Proposition Symbols
PQR
Logical Connectives
¬
not
∧∨
and or
→↔
implication biconditional
Not (¬)
P
¬P
false
true
true
false
And (∧)
P
Q
P∧Q
false
false
false
false
true
false
true
false
false
true
true
true
Or (∨)
P
Q
P∨Q
false
false
false
false
true
true
true
false
true
true
true
true
Implication (→)
P
Q
P→Q
false
false
true
false
true
true
true
false
false
true
true
true
Biconditional (↔)
P
Q
P↔Q
false
false
true
false
true
false
true
false
false
true
true
true
model
assignment of a truth value to every propositional symbol (a “possible world”)
model
P: It is raining.
Q: It is a Tuesday.
{P = true, Q = false}
knowledge base
a set of sentences known by a knowledge-based agent
Entailment
α⊨β
In every model in which sentence α is true, sentence β is also true.
If it didn’t rain, Harry visited Hagrid today.
Harry visited Hagrid or Dumbledore today, but not both. Harry visited Dumbledore today.
Harry did not visit Hagrid today. It rained today.
inference
the process of deriving new sentences from old ones
P: It is a Tuesday.
Q: It is raining.
R: Harry will go for a run.
KB: (P ∧ ¬Q) → R P ¬Q
R
Inference:
Inference Algorithms
Does
KB ⊨ α ?
Model Checking
Model Checking
•
Enumerate all possible models.
If in every model where KB is true, α is true, then KB entails α.
•
To determine if KB ⊨ α:
• •
Otherwise, KB does not entail α.
P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P∧¬Q)→R P ¬Q
R
Query:
P
Q
R
KB
false
false
false
false
false
true
false
true
false
false
true
true
true
false
false
true
false
true
true
true
false
true
true
true
P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P∧¬Q)→R P ¬Q
R
Query:
P
Q
R
KB
false
false
false
false
false
false
true
false
false
true
false
false
false
true
true
false
true
false
false
false
true
false
true
true
true
true
false
false
true
true
true
false
P: It is a Tuesday. Q: It is raining. R: Harry will go for a run. KB: (P∧¬Q)→R P ¬Q
R
Query:
P
Q
R
KB
false
false
false
false
false
false
true
false
false
true
false
false
false
true
true
false
true
false
false
false
true
false
true
true
true
true
false
false
true
true
true
false
Knowledge Engineering
Clue
Clue People
Col. Mustard Prof. Plum Ms. Scarlet
Rooms
Ballroom Kitchen Library
Weapons
Knife Revolver Wrench
Clue People
Col. Mustard Prof. Plum Ms. Scarlet
Rooms
Ballroom Kitchen Library
Weapons
Knife Revolver Wrench
Clue People
Prof. Plum
Ms. Scarlet Col. Mustard
Rooms
Library Kitchen Ballroom
Weapons
Wrench Knife Revolver
People
Prof. Plum
Ms. Scarlet Col. Mustard
Rooms
Library Kitchen Ballroom
Weapons
Wrench Knife Revolver
People
Rooms
Library Kitchen
Weapons
Wrench
Ms. Scarlet Col. Mustard
Revolver
PKronfi.fPelum Ballroom
Clue
Propositional Symbols
mustard plum scarlet
ballroom kitchen library
knife revolver wrench
Clue
(mustard ∨ plum ∨ scarlet) (ballroom ∨ kitchen ∨ library) (knife ∨ revolver ∨ wrench)
¬plum
¬mustard ∨ ¬library ∨ ¬revolver
Logic Puzzles
•
• • •
Gilderoy, Minerva, Pomona and Horace each belong to a different one of the four houses: Gryffindor, Hufflepuff, Ravenclaw, and Slytherin House.
Gilderoy belongs to Gryffindor or Ravenclaw. Pomona does not belong in Slytherin. Minerva belongs to Gryffindor.
Logic Puzzles Propositional Symbols
GilderoyGryffindor GilderoyHufflepuff GilderoyRavenclaw GilderoySlytherin
PomonaGryffindor PomonaHufflepuff PomonaRavenclaw PomonaSlytherin
MinervaGryffindor MinervaHufflepuff MinervaRavenclaw MinervaSlytherin
HoraceGryffindor HoraceHufflepuff HoraceRavenclaw HoraceSlytherin
Logic Puzzles
(PomonaSlytherin → ¬PomonaHufflepuff) (MinervaRavenclaw → ¬GilderoyRavenclaw)
(GilderoyGryffindor ∨ GilderoyRavenclaw)
Mastermind
2 0 4
Inference Rules
Modus Ponens
If it is raining, then Harry is inside.
It is raining. Harry is inside.
Modus Ponens
α→β α
β
And Elimination
Harry is friends with Ron and Hermione.
Harry is friends with Hermione.
And Elimination
α∧β α
Double Negation Elimination
It is not true that Harry did not pass the test.
Harry passed the test.
Double Negation Elimination
¬(¬α) α
Implication Elimination
If it is raining, then Harry is inside.
It is not raining or Harry is inside.
Implication Elimination
α→β ¬α ∨ β
Biconditional Elimination
It is raining if and only if Harry is inside.
If it is raining, then Harry is inside, and if Harry is inside, then it is raining.
Biconditional Elimination
α↔β
(α→ β)∧(β→α)
De Morgan’s Law
It is not true that both Harry and Ron passed the test.
Harry did not pass the test or Ron did not pass the test.
De Morgan’s Law
¬(α ∧ β) ¬α ∨ ¬β
De Morgan’s Law
It is not true that
Harry or Ron passed the test.
Harry did not pass the test and Ron did not pass the test.
De Morgan’s Law
¬(α ∨ β) ¬α ∧ ¬β
Distributive Property
(α ∧ (β ∨ γ)) (α∧β)∨ (α∧γ)
Distributive Property
(α ∨ (β ∧ γ)) (α ∨ β) ∧ (α ∨ γ)
Search Problems
• • • • •
initial state actions transition model goal test
path cost function
Theorem Proving
• • • • •
initial state: starting knowledge base
actions: inference rules
transition model: new knowledge base after inference goal test: check statement we’re trying to prove
path cost function: number of steps in proof
Resolution
(Ron is in the Great Hall) ∨ (Hermione is in the library) Ron is not in the Great Hall
Hermione is in the library
P∨Q ¬P
Q
P∨Q1 ∨Q2 ∨…∨Qn ¬P
Q1 ∨Q2 ∨…∨Qn
(Ron is in the Great Hall) ∨ (Hermione is in the library) (Ron is not in the Great Hall) ∨ (Harry is sleeping)
(Hermione is in the library) ∨ (Harry is sleeping)
P∨Q ¬P ∨ R
Q∨R
P∨Q1 ∨Q2 ∨…∨Qn ¬P∨R1 ∨R2 ∨…∨Rm
Q1 ∨Q2 ∨…∨Qn∨R1 ∨R2 ∨…∨Rm
clause
a disjunction of literals e.g. P ∨ Q ∨ R
conjunctive normal form
logical sentence that is a conjunction of clauses
e.g. (A ∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F ∨ G)
Conversion to CNF
•
turn(α↔ β)into(α→ β)∧(β→α)
Eliminate biconditionals
•
Eliminate implications
•
turn(α→ β)into¬α∨β
•
Move ¬ inwards using De Morgan’s Laws
•
e.g. turn ¬(α ∧ β) into ¬α ∨ ¬β
•
•
Use distributive law to distribute ∨ wherever possible
Conversion to CNF
(P ∨ Q) → R ¬(P ∨ Q) ∨ R (¬P ∧ ¬Q) ∨ R
(¬P∨R)∧ (¬Q∨R)
eliminate implication
De Morgan’s Law distributive law
Inference by Resolution
P∨Q ¬P ∨ R
(Q ∨ R)
P∨Q∨S ¬P ∨ R ∨ S
(Q ∨ S ∨ R ∨ S)
P∨Q∨S ¬P ∨ R ∨ S
(Q ∨ R ∨ S)
P
¬P ()
Inference by Resolution
•
Check if (KB ∧ ¬α) is a contradiction?
To determine if KB ⊨ α:
•
If so, then KB ⊨ α.
• •
Otherwise, no entailment.
Inference by Resolution
•
Convert (KB ∧ ¬α) to Conjunctive Normal Form.
To determine if KB ⊨ α:
•
•
If ever we produce the empty clause (equivalent
Keep checking to see if we can use resolution to produce a new clause.
•
to False), we have a contradiction, and KB ⊨ α.
•
Otherwise, if we can’t add new clauses, no entailment.
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B) (A)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B) (A)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B) (A)
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B) (A) ( )
Inference by Resolution
Does (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) entail A? (A ∨ B) ∧ (¬B ∨ C) ∧ (¬C) ∧ (¬A)
(A∨B) (¬B∨C) (¬C) (¬A)
(¬B) (A) ( )
First-Order Logic
Propositional Logic
Propositional Symbols
MinervaGryffindor MinervaHufflepuff MinervaRavenclaw MinervaSlytherin …
First-Order Logic
Constant Symbol
Minerva Pomona Horace Gilderoy Gryffindor Hufflepuff Ravenclaw Slytherin
Predicate Symbol
Person House BelongsTo
First-Order Logic
Person(Minerva) House(Gryffindor) ¬House(Minerva)
Minerva is a person. Gryffindor is a house. Minerva is not a house.
BelongsTo(Minerva, Gryffindor)
Minerva belongs to Gryffindor.
Universal Quantification
Universal Quantification
∀x. BelongsTo(x, Gryffindor) → ¬BelongsTo(x, Hufflepuff)
For all objects x, if x belongs to Gryffindor, then x does not belong to Hufflepuff.
Anyone in Gryffindor is not in Hufflepuff.
Existential Quantification
Existential Quantification
∃x. House(x) ∧ BelongsTo(Minerva, x)
There exists an object x such that
x is a house and Minerva belongs to x. Minerva belongs to a house.
Existential Quantification
∀x. Person(x) → (∃y. House(y) ∧ BelongsTo(x, y))
For all objects x, if x is a person, then there exists an object y such that y is a house and x belongs to y.
Every person belongs to a house.
Knowledge
Introduction to
Artificial Intelligence
with Python