slide 1: Unit III: Logic and Reasoning
Reference:
Artificial Intelligence by Stuart Russell and
Peter Norvig
slide 2: 7/31/2018 KNOWLEDGE REASONING AND PLANNING 2
Knowledge Based Reasoning:
Logic and Inferences:
Knowledge Representation
Index
slide 3: Knowledge Representation and
Reasoning
Intelligent agents should have capacity for:
Perceiving: that is acquiring information from
environment
Knowledge Representation: that is representing its
understanding of the world
Reasoning: that is inferring the implications of what
it knows and of the choices it has and
Acting: that is choosing what it want to do and carry
it out.
3 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 4: Knowledge bases
The central component of a knowledge-based agent is its
knowledge base or KB.
Informally a knowledge base is a set of sentences.
Here "sentence" is used as a technical term. It is related but
is not identical to the sentences of English and other
natural languages.
Each sentence is expressed in a language called a
knowledge representation language and represents some
assertion about the world.
5 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 5: Knowledge bases
The agent maintains a knowledge base KB
KNOWLEDGE which may initially contain some
background knowledge.
Each time the agent program is called it does three things.
First it TELLS the knowledge base what it perceives.
Second it ASKS the knowledge base what action it should
perform.
Third the agent records its choice with TELL and executes the
action.
The second TELL is necessary to let the knowledge base know
that the hypothetical action has actually been executed.
6 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 6: A simple knowledge-based agent
The agent must be able to:
Percept
Represent
Reasoning
Action.
7 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 7: Wumpus World
Performance Measure
• Gold +1000 Death – 1000
• Step -1 Use arrow -10
Environment
• Square adjacent to the Wumpus are smelly
• Squares adjacent to the pit are breezy
• Glitter iff gold is in the same square
• Shooting kills Wumpus if you are facing it
• Shooting uses up the only arrow
• Grabbing picks up the gold if in the same square
Actuators
• Left turn right turn forward grab release shoot
Sensors
• Breeze glitter and smell
9 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 8: Wumpus World
Characterization of Wumpus World
Observable
• partial only local perception
Deterministic
• Yes outcomes are specified
Episodic
• No sequential at the level of actions
Static
• Yes Wumpus and pits do not move
Discrete
• Yes
Single Agent
• Yes
10 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 9: Logic in general
Logics are formal languages for representing information
such that conclusions can be drawn
Syntax defines the sentences in the language
Semantics define the "meaning" of sentences
i.e. define truth of a sentence in a world
E.g. the language of arithmetic
x+2 ≥ y is a sentence x2+y is not a sentence
x+2 ≥ y is true iff the number x+2 is no less than the number y
x+2 ≥ y is true in a world where x 7 y 1
x+2 ≥ y is false in a world where x 0 y 6
20 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 10: Reasoning
process of constructing new configurations sentences
from old ones
proper reasoning ensures that the new configurations
represent facts that actually follow from the facts that the
old configurations represent
this relationship is called entailment and can be
expressed as
KB | alpha
knowledge base KB entails the sentence alpha
21 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 11: Inference Methods
an inference procedure can do one of two things:
given a knowledge base KB it can derive new sentences that are
supposedly entailed by KB
KB |- KB |
given a knowledge base KB and another sentence alpha it can report
whether or not alpha is entailed by KB
KB KB |
an inference procedure that generates only entailed
sentences is called sound or truth-preserving
the record of operation of a sound inference procedure is
called a proof
an inference procedure is complete if it can find a proof for
any sentence that is entailed
22 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 12: Big Ideas
Logic is a great knowledge representation language for
many AI problems
Propositional logic is the simple foundation and fine for
some AI problems
First order logic FOL is much more expressive as a KR
language and more commonly used in AI
23 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 13: Propositional logic
Logical constants: true false
Propositional symbols: P Q... atomic sentences
Wrapping parentheses: …
Sentences are combined by connectives:
and conjunction
or disjunction
implies implication / conditional
is equivalent biconditional
not negation
Literal: atomic sentence or negated atomic sentence P P
24 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 14: Propositional logic: Syntax
Propositional logic is the simplest logic – illustrates basic
ideas
The proposition symbols P
1
P
2
etc are sentences
If S is a sentence S is a sentence negation
If S
1
and S
2
are sentences S
1
S
2
is a sentence conjunction
If S
1
and S
2
are sentences S
1
S
2
is a sentence disjunction
If S
1
and S
2
are sentences S
1
S
2
is a sentence implication
If S
1
and S
2
are sentences S
1
S
2
is a sentence biconditional
25 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 15: Propositional logic: Semantics
Each model specifies true/false for each proposition symbol
E.g. P
12
P
22
P
31
false true false
With these symbols 8 possible models can be enumerated automatically.
S is true iff S is false
S
1
S
2
is true iff S
1
is true and S
2
is true
S
1
S
2
is true iff S
1
is true or S
2
is true
S
1
S
2
is true iff S
1
is false or S
2
is true
i.e. is false iff S
1
is true and S
2
is false
S
1
S
2
is true iff S
1
S
2
is true andS
2
S
1
is true
Simple recursive process evaluates an arbitrary sentence e.g.
P
12
P
22
P
31
true true false true true true
Rules for evaluating truth with respect to a model m:
26 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 16: On the implies connective: P Q
Note that is a logical connective
So P Q is a logical sentence and has a truth value i.e. is
either true or false
If we add this sentence to the KB it can be used by an
inference rule Modes Ponens to derive/infer/prove Q if P
is also in the KB
Given a KB where PTrue and QTrue we can also
derive/infer/prove that P Q is True
27 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 17: P Q
When is P Q true Check all that apply
PQtrue
PQfalse
Ptrue Qfalse
Pfalse Qtrue
28 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 18: P Q
When is P Q true Check all that apply
PQtrue
PQfalse
Ptrue Qfalse
Pfalse Qtrue
We can get this from the truth table for
Note: in FOL it’s much harder to prove that
a conditional true.
✔
✔
✔
29 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 19: Truth tables
Truth tables are used to define logical connectives and to
determine when a complex sentence is true given the values
of the symbols in it
Truth tables for the five logical connectives
30 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 20: 31 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 21: Examples of PL sentences
P Q R
“If it is hot and humid then it is raining”
Q P
“If it is humid then it is hot”
Q
“It is humid.”
We’re free to choose better symbols btw:
Ho “It is hot”
Hu “It is humid”
R “It is raining”
33 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 22: Model for a KB
Let the KB be P Q R Q P Q
What are the possible models Consider all possible
assignments of T|F to P Q and R and check truth tables
FFF: OK
FFT: OK
FTF: NO
FTT: NO
TFF: OK
TFT: OK
TTF: NO
TTT: OK
If KB is P Q R Q P Q then the only model is
TTT
P: it’s hot
Q: it’s humid
R: it’s raining
34 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 23: 35 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 24: Inference
KB ├
i
α sentence α can be derived from KB by procedure
i
Soundness: i is sound if whenever KB ├
i
α it is also true
that KB╞ α
Completeness: i is complete if whenever KB╞ α it is also
true that KB ├
i
α
Preview: we will define a logic first-order logic which is
expressive enough to say almost anything of interest and
for which there exists a sound and complete inference
procedure.
That is the procedure will answer any question whose
answer follows from what is known by the KB.
36 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 25: Inference rules
Logical inference creates new sentences that logically
follow from a set of sentences KB
An inference rule is sound if every sentence X it produces
when operating on a KB logically follows from the KB
i.e. inference rule creates no contradictions
An inference rule is complete if it can produce every
expression that logically follows from is entailed by the
KB.
37 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 26: Resolution
A KB is actually a set of sentences all of which are true i.e.
a conjunction of sentences.
To use resolution put KB into conjunctive normal form
CNF
A sentence expressed as a conjunction of disjunctions of
literals is said to be in conjunctive normal form.
Convertion to CNF by using the following equivalences
1. A ↔ B A-B ∧ B-A
2. A →B ￢A ∨ B
3. ￢A ∧ B ￢A ∨ ￢B
4. ￢A ∨ B ￢A ∧ ￢B
5. ￢￢A A
6. A ∨ B ∧ C A ∨ B ∧ A ∨ C
40 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 27: A→B→C
￢A→B ∨ C 2
￢ ￢A ∨ B ∨ C 3
A ∧ ￢B ∨ C 4
A ∨ C ∧ ￢B ∨ C 6
A→B ∧ C ∧ B ∧ C→A 1
￢A ∨ B ∧ C ∧ ￢B ∧ C ∨ A 2
￢A ∨ B ∧ C ∧ ￢B ∨ ￢C ∨ A 3
￢A ∨ B ∧ ￢A ∨ C ∧ ￢B ∨ ￢C ∨ A 6
A further example follows:
A↔ B ∧ C
For example we will convert A →B→C to CNF:
44 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 28: Horn sentences
A Horn sentence or Horn clause has the form:
P1 P2 P3 ... Pn Qm where n0 m in01
Note: a conjunction of 0 or more symbols to left of
and 0-1 symbols to right
A Horn clause or Horn sentence is a clause that
has at most one positive literal. Hence the
following Horn clause takes the following form:
• A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E
• can be written as:
B ∧ C ∧ D ∧ E→A
• In Prolog: can be written as
A :− B C D E
45 KNOWLEDGE REASONING AND PLANNING 7/31/2018
P Q P Q
slide 29: Horn sentences
• Horn clauses can take three forms:
• Clause with one positive literal and one or more
negative literals is called a rule relation.
A ∨ ￢B ∨ ￢C ∨ ￢D ∨ ￢E
• A clause with no negative literals is called a fact:
A : −
• Finally a clause with no positive literal is called a goal
or a headless clause:
: − B C D E
46 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 30: Artificial Intelligence: First-Order Logic
47 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 31: Contents
• More on Representation
• Syntax and Semantics of First-Order Logic
• Using First Order Logic
• Knowledge Engineering in First-Order Logic
48 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 32: First-Order Logic
• AKA First-Order Predicate Logic
• AKA First-Order Predicate Calculus
• Much more powerful than propositional logic
• Greater expressive power than propositional logic
• Allows for facts objects and relations
• In programming terms allows classes functions and variables
49 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 33: Truth in First-Order Logic
• Sentences are true with respect to a model and an
interpretation
• Model contains 1 object domain elements and
relations among them
• Interpretation specifies referents for
– constant symbols - objects
– predicate symbols - relations
– function symbols - functional relations
• An atomic sentence predicate term
1
…term
n
is true iff the
objects referred to by term
1
…term
n
are in the relation
referred to by predicate
50 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 34: Syntax of First-Order Logic
• Constants KingJohn KingRamA …
• Predicates Brother …
• Functions Sqrt LeftArmOf …
• Variables x y a b …
• Connectives ¬
• Equality
• Quantifiers
51 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 35: Components of First-Order Logic
• Term
– Constant e.g. Red
– Function of constant e.g. ColorBlock1
• Atomic Sentence
– Predicate relating objects no variable
• Brother John Richard
• Married MotherJohn FatherJohn
• Complex Sentences
– Atomic sentences + logical connectives
• Brother John Richard Brother John FatherJohn
• BrotherLeftLegRichard J ohn
• BrotherRichard John A Brother John Richard
• King Richard V King John
• King Richard King John
•
52 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 36: Components of First-Order Logic
• Quantifiers
– Each quantifier defines a variable for the duration of the
following expression and indicates the truth of the
expression…
• Universal quantifier “for all”
– The expression is true for every possible value of the
variable
• Existential quantifier “there exists”
– The expression is true for at least one value of the variable
53 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 37: First-Order Logic Example
54 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 38: Universal Quantification
• variables sentence
• x P is true in a model m iff P with x being each possible
object in the model
• x Kingx Personx is true iff
Kingx Personx
55 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 39: A Common Mistake to Avoid
• variables sentence
• Typically is the main connective with
• Common mistake: using as the main connective with
• x Kingx Personx
• x Kingx Personx
56 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 40: Existential Quantification
• variables sentence
• x P is true in a model m iff P with x being at least one
possible object in the model
• x Crownx A OnHead x John
– Richard the Lionheart is a crown Richard the Lionheart on
Johns head
– King John is a crown King John is on Johns head
– Richards left leg is a crown Richards left leg is on Johns
head
– Johns left leg is a crown Johns left leg is on Johns head
– The crown is a crown the crown is on Johns head.
57 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 41: Another Common Mistake to Avoid
• Typically is the main connective with
• Common mistake: using as the main connective
with
x Crownx A OnHead x John
x Crownx OnHead x John
58 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 42: Examples
• Everyone likes McDonalds
– x likesx McDonalds
• Someone likes McDonalds
– x likesx McDonalds
• All children like McDonalds
– x childx likesx McDonalds
• Everyone likes McDonalds unless they are allergic to it
– x likesx McDonalds allergicx McDonalds
– x allergic x McDonalds likesx McDonalds
59 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 43: Properties of Quantifiers
• x y is the same as y x
– x y Brotherx y Siblingx y.
– x y Siblingx y Sibling yx.
• x y is the same as y x
• x y is not the same as y x
– x y Lovesx y
• “There is a person who loves everyone in the world”
– y x Lovesx y
• “Everyone in the world is loved by at least one person”
60 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 44: Nesting Quantifiers
• Everyone likes some kind of food
y x foodx likesy x
• There is a kind of food that everyone likes
x y foodx likesy x
• Someone likes all kinds of food
y x foodx likesy x
• Every food has someone who likes it
x y foodx likesy x
61 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 45: Fun with Sentences
• One’s mother is one’s female parent
xy Motherxy Femalex Parentxy
• A first cousin is a child of a parent’s sibling
xy FirstCousinxy pps Parentpx
Siblingpsp Parentpsy
62 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 46: Equality
• We allow the usual infix operator
– FatherJohn Henry
– x siblingx y xy
• Example:
– x y Brotherx R ichard A Brothery Richard ¬
xy
63 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 47: Interacting with FOL KBs
• Tell the system assertions
– Facts :
• Tell KB person John
– Rules:
• Tell KB x personx likesx McDonalds
• Ask questions
– Ask KB personJohn
– Ask KB likesJohn McDonalds
– Ask KB likesx McDonalds
64 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 48: Unification
66 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 49: Unification
• We can get the inference immediately if we can find a substitution θ
such that Kingx and Greedyx match KingJohn and Greedyy
θ x/Johny/John works
Unifyαβ θ if αθ βθ
p q θ
KnowsJohnx KnowsJohnJane
KnowsJohnx KnowsyOJ
KnowsJohnx KnowsyMothery
KnowsJohnx KnowsxOJ
Standardizing apart eliminates overlap of variables e.g. Knowsz
17
OJ
67 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 50: Unification
• We can get the inference immediately if we can find a substitution θ
such that Kingx and Greedyx match KingJohn and Greedyy
θ x/Johny/John works
Unifyαβ θ if αθ βθ
p q θ
KnowsJohnx KnowsJohnJane x/Jane
KnowsJohnx KnowsyOJ
KnowsJohnx KnowsyMothery
KnowsJohnx KnowsxOJ
• Standardizing apart eliminates overlap of variables e.g.
Knowsz
17
OJ
68 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 51: Unification
• We can get the inference immediately if we can find a substitution θ
such that Kingx and Greedyx match KingJohn and Greedyy
θ x/Johny/John works
Unifyαβ θ if αθ βθ
p q θ
KnowsJohnx KnowsJohnJane x/Jane
KnowsJohnx KnowsyOJ x/OJy/John
KnowsJohnx KnowsyMothery
KnowsJohnx KnowsxOJ
• Standardizing apart eliminates overlap of variables e.g.
Knowsz
17
OJ
69 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 52: Unification
• finding substitutions that make different logical expressions look
identical
Unifyαβ θ if αθ βθ
p q θ
KnowsJohnx KnowsJohnJane x/Jane
KnowsJohnx KnowsyOJ x/OJy/John
KnowsJohnx KnowsyMothery y/Johnx/MotherJohn
KnowsJohnx KnowsxOJ
• Standardizing apart eliminates overlap of variables e.g.
Knowsz
17
OJ
70 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 53: Unification
• We can get the inference immediately if we can find a substitution θ
such that Kingx and Greedyx match KingJohn and Greedyy
θ x/Johny/John works
Unifyαβ θ if αθ βθ
p q θ
KnowsJohnx KnowsJohnJane x/Jane
KnowsJohnx KnowsyOJ x/OJy/John
KnowsJohnx KnowsyMothery y/Johnx/MotherJohn
KnowsJohnx KnowsxOJ fail
• Standardizing apart eliminates overlap of variables e.g.
Knowsz
17
OJ
71 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 54: Unification
• To unify KnowsJohnx and Knowsyz
θ y/John x/z or θ y/John x/John z/John
• The first unifier is more general than the second.
• There is a single most general unifier MGU that
is unique up to renaming of variables.
MGU y/John x/z
72 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 55: Forward Chaining
Forward Chaining
• Start with atomic sentences in the KB and apply
Modus Ponens in the forward direction adding
new atomic sentences until no further inferences
can be made.
75 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 56: FC: Example Knowledge Base
• The law says that it is a crime for an American to
sell weapons to hostile nations. The country Nono
an enemy America has some missiles and all of
its missiles were sold to it by Col. West who is an
American.
• Prove that Col. West is a criminal.
77 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 57: FC: Example Knowledge
Base
…it is a crime for an American to sell weapons to hostile nations
Americanx Weapony Sellsxyz Hostilez Criminalx
Nono…has some missiles
x OwnsNono x Missilesx
OwnsNono M
1
and MissleM
1
…all of its missiles were sold to it by Col. West
x Misslex OwnsNono x Sells West x Nono
Missiles are weapons
Misslex Weaponx
78 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 58: FC: Example Knowledge
Base
An enemy of America counts as “hostile”
Enemy x America Hostilex
Col. West who is an American
American Col. West
The country Nono an enemy of America
EnemyNono America
79 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 59: FC: Example Knowledge
Base
80 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 60: FC: Example Knowledge
Base
81 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 61: FC: Example Knowledge
Base
82 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 62: Efficient Forward Chaining
Order conjuncts appropriately
◦ E.g. most constrained variable
Don’t generate redundant facts each new fact should depend on at least
one newly generated fact.
◦ Production systems
◦ RETE matching
◦ CLIPS
83 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 63: Forward Chaining Algorithm
84 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 64: Backward chaining
Idea: work backwards from the query q:
Idea: Check whether a particular fact q is true.
Backward Chaining
Given a fact q to be “proven”
1. See if q is already in the KB. If so return TRUE.
2. Find all implications I whose conclusion “matches” q.
3. Recursively establish the premises of all I in I via backward
chaining.
Avoids inferring unrelated facts.
85 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 65: Forward and backward chaining
Horn Form restricted
KB conjunction of Horn clauses
Horn clause
proposition symbol or
conjunction of symbols symbol
E.g. C B A C D B
Modus Ponens for Horn Form: complete for Horn KBs
α
1
… α
n
α
1
… α
n
β
β
Can be used with forward chaining or backward chaining.
These algorithms are very natural and run in linear time.
86 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 66: Forward vs. backward chaining
FC is data-driven automatic unconscious processing
e.g. object recognition routine decisions
May do lots of work that is irrelevant to the goal
BC is goal-driven appropriate for problem-solving
e.g. Where are my keys
Complexity of BC can be much less than linear in size of
KB
87 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 67: Logic Programming
Basis:
• Prolog programs are sets of definite clauses written in a notation
some what different from standard first-order logic.
• Prolog uses uppercase letters for variables and lowercase for
constants.
• Clauses are written with the head preceding the body " : -" is used
for left implication commas separate literals in the body and a
period marks the end of a sentence:
Programming set of clauses
head :- literal1 … literaln
criminalX :- americanX weaponY sellsX Y Z hostileZ
88 KNOWLEDGE REASONING AND PLANNING 7/31/2018
slide 68: Semantic Nets Frames
slide 69: Knowledge Representation as a medium for
human expression
An intelligent system must have KRs that can be interpreted
by humans.
– We need to be able to encode information in the knowledge base
without significant effort.
– We need to be able to understand what the system knows and how it
draws its conclusions.
slide 70: Knowledge Representation
Logic prepositional predicate
Network representation
◦ Semantic nets
Structured representation
◦ Frames
slide 71: Semantic Networks
First introduced by Quillian back in the late-60s
M. Ross Quillian. "Semantic Memories" In M. M. Minsky editor Semantic
Information Processing pages 216-270. Cambridge MA: MIT Press 1968
Semantic network is simple representation scheme which uses
a graph of labeled nodes and labeled directed arcs to encode
knowledge
◦ Nodes – objects concepts events
◦ Arcs – relationships between nodes
Graphical depiction associated with semantic networks is a
big reason for their popularity
slide 72: Inheritance
Inheritance is one of the main kind of
reasoning done in semantic nets
The ISA is a relation is often used to
link a class and its superclass.
Some links e.g. haspart are inherited
along ISA paths
The semantics of a semantic net can be
relatively informal or very formal
◦ Often defined at the implementation level
slide 73: Advantages of Semantic nets
Easy to visualize
Formal definitions of semantic networks have been
developed.
Related knowledge is easily clustered.
Efficient in space requirements
◦ Objects represented only once
◦ Relationships handled by pointers
slide 74: Frames
Frames – semantic net with properties
A frame represents an entity as a set of slots attributes and
associated values
A frame can represent a specific entry or a general concept
Frames are implicitly associated with one another because the value
of a slot can be another frame
Book Frame
Slot Filler
•Title AI. A modern Approach
•Author Russell Norvig
•Year 2003
3 components of a frame
• frame name
• attributes slots
• values fillers: list of values
range string etc.
slide 75: Inheritance
Similar to Object-Oriented
programming paradigm
Hotel Room
•what room
•where hotel
•contains
–hotel chair
–hotel phone
–hotel bed
Hotel Chair
•what chair
•height 20-40cm
•legs 4
Hotel Phone
•what phone
•billing guest
Hotel Bed
•what bed
•size king
•part mattress
Mattress
•price 100