Transcript Agent that reason logically

Agent that reason logically
지식표현
Knowledge Base
A set of representations of facts about the world
Knowledge representation language
 tell : what has been told to the knowledge base
previously
 ask : a question and the answer
Inference : what follows from what the KB has been
Telled
Background knowledge : a knowledge base which
may initially contained
Sentence : individual representation of a fact
Agent that reason logically
2
Knowledge base
The knowledge level :: saying what it knows
to KB  “Golden Gates Bridge links San
Francisco and Marin Country
The logical level :: the knowledge is encoding
into sentences  Links(GGBridge, SF, Marin)
The implementation level :: the level that
runs on the agent architecture (data
structures to represent knowledge or facts)
Agent that reason logically
3
Knowledge
declarative/procedural


love(john, mary).
can_fly(X) :- bird(X), not(can_fly(X)), !.
learning : general knowledge about the
environment given a series of percepts
Commonsense knowledge
Agent that reason logically
4
Specifying the environment
Figure 6.2 A typical wumpus world
Agent that reason logically
5
Domain specific knowledge
Domain specific knowledge

In the squares directly adjacent to a pit, the
agent will perceive a breeze
Commonsense knowledge



logical reasoning
stench(1,2) & ~setnch(2,1)  ~wumpus(2,2)
wumpus(1,3) 
stench(2,1) & stench(2,3) & stench(1,4)
Agent that reason logically
6
Inference in Wumpus world(I)
1,4
2,4
3,4
4,4
1,3
2,3
3,3
4,3
1,2
2,2
3,2
4,2
A = Agent
B = Breeze
G = Glitter, Gold
OK = Safe square
P = Pit
S = Stench
V = Visited
W = Wumpus
1,4
2,4
3,4
4,4
1,3
2,3
3,3
4,3
1,2
2,2
3,2
4,2
3,1
4,1
P?
OK
1,1
A
OK
2,1
3,1
4,1
1,1
OK
V
OK
2,1 A
B
OK
Figure 6.3 The first step taken by the agent in the wumpus world.
(a) The initial situation, after percept [None, None, None, None, None].
(b) After one move, with percept [None, Breeze, None, None, None].
Agent that reason logically
7
Inference in Wumpus
world(II)
1,4
2,4
1,3
3,4
4,4
2,3
3,3
4,3
2,2
3,2
4,2
3,1
4,1
W!
1,2
A
OK
1,1
V
OK
OK
2,1 B
V
OK
A = Agent
B = Breeze
G = Glitter, Gold
OK = Safe square
P = Pit
S = Stench
V = Visited
W = Wumpus
1,4
2,4
3,4
4,4
P?
1,3
W ! 2,3 A 3,3P ?
S G
B
1,2 S
2,2
3,2
V
V
OK
OK
1,1
2,1 B
3,1
V
V
P!
OK
OK
4,3
4,2
4,1
Figure 6.4 Two later stages in the progress of the agent.
(a) After the third move, with percept [Stench, None, None, None, None].
(b) After the fifth move, with percept [Stench, Breeze, Glitter, None, None].
Agent that reason logically
8
Representation, Reasoning,
and Logic
Syntax : the possible configurations that
constitute sentences
Semantics : the facts in the world to
which the sentences refer
Agent that reason logically
9
The logical reasoning
Aentences
World
Facts
Follows
Semantics
Semantics
Representation
Entails
Sentence
Fact
Figure 6.5 The connection between sentences and facts is provided by the semantics
of the language. The property of one fact following from some other facts is mirrored by
the property of one sentence being entailed by some other sentences. Logical inference
generates new sentences that are entailed by existing sentences.
Agent that reason logically
10
Inference I
Entailment ::
generation of new sentences that
are necessarily true, given that the old sentences are
true
Soundness, truth-preserving ::
An
inference procedure that generates only entailed
sentences  modus ponens <-> abduction
KB├i ,  is derived from KB by I
Proof :: a sound inference procedure
Agent that reason logically
11
Inference II
Completeness ::
an inference procedure that can find a
proof for any sentence that is entailed
Proof :: specifying the reasoning steps that are sound
Valid :: if and only if all possible interpretations in all
possible worlds
Tautologies, analytic sentences :: valid sentences
Satisfiable :: if and only if there is some interpretation in
some world for which it is true
Unsatisfiable ::
a sentence that is not satisfiable
Agent that reason logically
12
Logics
Boolean logic


Symbols represent whole propositions (facts)
Boolean connectives
First-order logic


objects, predicates
connectives, quantifiers
Agent that reason logically
13
Wrong logical reasoning
FIRST VILLAGER: We have found a witch. May we burn her?
ALL: A witch! Burn her!
BEDEVERE: Why do you think she is a witch?
SECOND VILLAGER: She turned me into a newt.
BEDEVERE: A newt?
SECOND VILLAGER (after looking at himself for some time): I got better.
ALL: Burn her anyway.
BEDEVERE: Quiet! Quiet! There are ways of telling whether she is a witch.
BEDEVERE: Tell me … What do you do with witches?
ALL: Burn them.
BEDEVERE: And what do you burn, apart from witches?
FOURTH VILLAGER: … Wood?
BEDEVERE: So why do witches burn?
SECOND VILLAGER: (pianissimo) Because they’re made of wood?
BEDEVERE: Good.
ALL: I see. Yes, of course.
BEDEVERE: So how can we tell if she is made of wood?
FIRST VILLAGER: Make a bridge out of her.
BEDEVERE: Ah … but can you not also make bridges out of stone?
ALL: Yes, of course … um … er …
BEDEVERE: Does wood sink in water?
ALL: No, no, it floats. Throw her in the pond.
BEDEVERE: Wait. Wait … tell me, what also floats on water?
ALL: Bread? No, no no. Apples … gravy … very small rocks …
BEDEVERE: No, no no.
KING ARTHUR: A duck!
(They all turn and look at ARTHUR. BEDEVERE looks up very impressed.)
BEDEVERE: Exactly. So … logically …
FIRST VILLAGER (beginning to pick up the thread): If she .. Weight the same as a duck … she’s made of wood.
BEDEVERE: And therefore?
Agent that reason logically
ALL: A witch!
14
Ontological and
epistemological commitments
Ontological commitments :: to do with the
nature of reality
 Propositional logic(true/false), Predicate
logic, Temporal logic
Epistemological commitments :: to do with
the possible states of knowledge an agent
can have using various types of logic


degree of belief
fuzzy logic
Agent that reason logically
15
Commitments
Formal languages and their and ontological and
epistemological commitments
Language
Ontological Commitment
(What exists in the world)
Epistemological Commitment
(What an agent believes
about facts)
Propositional logic
First-order logic
Temporal logic
Probability theory
Fuzzy logic
facts
facts, objects, relations
times
facts
degree of truth
true/false/unknown
true/false/unknown
true/false/unknown
degree of belief 0…1
degree of belief 0…1
Agent that reason logically
16
Propositional Logic
logical constant : true/false
propositional symbols : P, Q
parentheses : (P & Q)
logical connectives : &(conjuction),
v(disjunction), ->(implication),
<>(equivalence), ~(negation)
Agent that reason logically
17
Grammar
Sentence  AtomicSentence | ComplexSentence
AtomicSentence  True | False
| P|Q|R|…
ComplexSentence  ( Sentence )
| Sentence Connective Sentence
| Sentence
Connective   |  |  | 
Figure 6.8 A BNF (Backus-Naur Form) grammar of sentences in propositional logic.
Agent that reason logically
18
Semantics
Truth table showing validity of a complex sentence
P
H
PH
(P  H) ┐H
((P  H)  ┐H)P
False
False
True
True
False
True
False
True
False
True
True
True
False
False
True
False
True
True
True
True
Agent that reason logically
19
Validity and Inference
Truth tables for five logical connectives
P
Q
┐P
PQ
PQ
PQ PQ
False
False
True
True
False
True
False
True
True
True
False
False
False
False
False
True
False
True
True
True
True
True
False
True
Agent that reason logically
True
False
False
True
20
Models
Any world in which a sentence is true
under a particular interpretation
Entailment :: a sentence  is entailed by a
knowledge base KB if the models of the KB
are all models of 
The set of models of P & Q is the
intersection of the models of P and the
models of Q
Agent that reason logically
21
Inference Rules for propositional logic

Modus Ponens or Implication-Elimination: (From an
 => , 
implication and the premise of the implication, you can infer the

conclusion.)

And-Elimination: (From a conjunction, you can infer any of the
conjuncts.)

And-Introduction: (From a list of sentences, you can infer their

with anything else at all.)
1  2  …  n
Double-Negation Elimination: (From a doubly negated


Unit Resolution: (From a disjunction, if one of the disjuncts is
false, then you can infer the other one is true.)

i
Or-Introduction: (From a sentence, you can infer its disjunction
sentence, you can infer a positive sentence.)

i
1, 2, …, n
 1  2  …  n
conjunction.)

1  2  …  n
  ,  

Resolution: (This is the most difficult. Because  cannot be both true and false,
one of the other disjucts must be true in one of the premises. Or equivalently,
implication is transitive.)
  ,    

or equivalently
  => ,  => 
  => 
Figure 6.13 Seven inference for propositional logic. The unit resolution rule is a special case of the resolution
rule, which in turn is a special case of the
full resolution
rule for
first-order logic discussed in Chapter 9. 22
Agent
that reason
logically
Complexity of propositional
inference
NP-complete
Monotonicity

If KB1╞  then (KB1 ∪ KB2) ╞ 
Horn clause logic


polynomial time complexity
P1∧P2∧….∧Pn ⇒ Q
Agent that reason logically
23
Wumpus world
Initial state
~S1,1
~S2,1
S1,2
~B1,1
B2,1
~B1,2
Rule
R1:
R2:
R3:
R4:
~S1,1
~S2,1
~S1,2
S1,2
-> ~W1,1 & ~W1,2 & ~W2,1
-> ~W1,1 & ~W2,1 & ~W2,2 & ~W3,1
-> ~W1,1 & ~W1,2 & ~W2,2 & ~W1,3
-> W1,3 V W1,2 V W2,2 V W1,2
Agent that reason logically
24
Finding the wumpus
Inference process




Modus ponens :
~S1,1 and R1  ~W1,1 & ~W1,2 & ~W2,1
And-Elimination
~W1,1 ~W1,2 ~W2,1
Modus ponens and And-Elimination:
~W2,2 ~W2,1 ~W3,1
Modus ponens
S1,2 and R4  W1,3 V W1,2 V W2,2 V W1,1
Agent that reason logically
25
Inference process(cont.)

unit resolution
~W1,1 and W1,3 V W1,2 V W2,2 V W1,1
 W1,3 V W1,2 V W2,2

unit resolution
~W2,2 and W1,3 V W1,2 V W2,2
 W1,3 V W1,2

unit resolution
~W1,2 and W1,3 V W1,2  W1,3
Agent that reason logically
26
Translating knowledge into
action
A1,1 & EastA & W2,1 -> ~Forward
EastA :: facing east
Propositional logic is not powerful
enough to solve the wumpus problem
easily
Agent that reason logically
27
숙제
6.3, 6.6, 6.7, 6.9, 6.10, 6.12, 6.15,
6.16
Agent that reason logically
28
First-order Logic
Limitation of propositional
logic
A very limited ontology
 to need to the representation power
 first-order logic
Agent that reason logically
30
First-order logic
A stronger set of ontological commitments
A world in FOL consists of objects, properties,
relations, functions
Objects  people, houses, number, colors, Bill
Clinton
Relations  brother of, bigger than, owns, love
Properties  red, round, bogus, prime
Functions father of, best friend, third inning of
Agent that reason logically
31
Examples
“One plus two equals three”
 objects :: one, two, three, one plus two
 Relation :: equal
 Function :: plus
“Squares neighboring the wumpus are smelly



Objects :: wumpus, square
Property :: smelly
Relation :: neighboring
Agent that reason logically
32
First order logics
Objects와 relations
시간, 사건, 카테고리 등은 고려하지 않음
영역에 따라 자유로운 표현이 가능함 
‘king’은 사람의 property도 될 수 있고, 사람과
국가를 연결하는 relation이 될 수도 있다
일차술어논리는 잘 알려져 있고, 잘 연구된
수학적 모형임
Agent that reason logically
33
Syntax and Semantics
Sentence  AtomicSentence
| Sentence Connective Sentence
| Auantifier Variable,…Sentence
| Sentence
| (Sentence)
AtomicSentence  Predicate(Term,…) | Term=Term
Term Function (Term,…)
| Constant
| Variable
Connective   |  |  | 
Quantifier   | 
Constant  A | X1 | John | …
Variable  a | x | s | …
Predicate  Before | HanColor | Raining | …
Function  Mother | LeftLegOf | …
Figure 7.1 The syntax of first-order logic (with equality) in BNF (Backus-Naur Form).
Agent that reason logically
34
예
Constant symbols :: A, B, John,
Predicate symbols :: Round, Brother
Function symbols :: Cosine, FatherOf
Terms :: King John, Richard’s left leg
Atomic sentences :: Brother(Richard,John),
Married(FatherOf(Richard), MotherOf(John))
Complex sentences ::
Older(John,30)=>~younger(John,30)
Agent that reason logically
35
Quantifiers
World = {a, b, c}
Universal quantifier (∀)
∀x Cat(x) => Mammal(x) 
Cat(a) => Mammal(a) &
Cat(a) => Mammal(a) &
Cat(a) => Mammal(a)
Existential quantifier (∃)
∃x Sister(x, Sopt) & Cat(x)
Agent that reason logically
36
Nested quantifiers
∀x,y Parent(x,y) => Child(y,x)
∀x,y Brother(x,y) => Sibling(y,x)
∀x∃y Loves(x,y)
∃y∀x Loves(x,y)
Agent that reason logically
37
De Morgan’s Rule
∀x ~P  ~∃x P
~P&~Q  ~(P v Q)
~∀x P  ∃x ~P
~(P&Q)  ~P v ~Q
∀x P  ~∃x ~P
P&Q  ~(~P v ~ Q)
∃x P  ~∀x ~P
P v Q  ~(~P&~Q)
Agent that reason logically
38
Equality
Identity relation
Father(John) = Henry
∃x,y Sister(Spot,x) & Sister(Spot,y)
& ~(x=y)
≠ ∃x,y Sister(Spot,x) & Sister(Spot,y)
Agent that reason logically
39
Higher-order logic
∀x,y (x=y)  (∀p p(x)  p(y))
∀
∀f,g (f=g)  (∀x f(x) g(x))
Agent that reason logically
40
-expression
x,y x2 – y2
-expression can be applied to
arguments to yield a logical term in the
same way that a function can be
(x,y x2 – y2)(25,24) = 252-242 = 49
x,y Gender(x) ≠Gender(y) & Address(x) =
Address(y)
Agent that reason logically
41
∃! (The uniqueness quantifier)
∃!x King(x)
∃x King(x) & ∀y King(y) => x=y
world를 고려하여 보여주면 => object가 1, 2, 3개일 때
{a} w0  king={}, w1  king={a}  w1만 model
{a,b} w0  king={}, w1  king={a},
w2 {b}, w3  {a,b}  w1, w2만 model
Agent that reason logically
42
Representation of sentences
by FOPL
One’s mother is one’s female parent
∀m,c Mother(c)=m  Female(m) & Parent(m)
One’s husband is one’s male spouse
∀w,h Husband(h,w)  Male(h) & Spouse(h,w)
Male and female are disjoint categories
∀x Male(x)  ~Female(x)
A grandparent is a parent of one’s parent
∀g,c Grandparent(g,c)  ∃p parent(g,p) & parent(p,g)
Agent that reason logically
43
Representation of sentences
by FOPL
A sibling is another child of one’s parents ∀x,y
Sibling(x,y)  x≠y & ∃p Parent(p,x) &
Parent(p,y)
Symmetric relations
∀x,y Sibling(x,y)  Sibling(y,x)
Agent that reason logically
44
The domain of sets (I)
The only sets are the empty set and those made by adjoining
something to a set :
∀s Set(s)  (s=EmptySet) v (∃x,s2 Set(s2) & s=Adjoin(x,s2))
The empty set has no elements adjoined into it.
~∃x,s Adjoin(x,s)=EmptySet
Adjoining an element already in the set has no effect
∀x,s Member(x,s)  s=Adjoin(x,s)
The only members of a set are the elements that were adjoined
into it
∀x,s Member(x,s) 
∃y,s2 (s=Adjoin(y,s2) & (x=y v Member(x,s)))
Agent that reason logically
45
The domain of sets (II)
A set is a subset of another if and only if all of the
first set’s are members of the second set :
∀s1,s2 Subset(s1,s2) 
(∀x Member(x,s1) => member(x,s2))
Two sets are equal if and only if each is a subset of
the other:
∀s1,s2 (s1=s2)  (Subset(s1,s2) & Subset(s2,s1))
Agent that reason logically
46
The domain of sets (III)
An object is a member of the intersection of two sets
if and only if it is a member of each of sets :
∀x,s1,s2 Member(x,Intersection(s1,s2)) 
Member(x,s1) & Member(x,s2)
An object is a member of the union of two sets if and
only if it is a member of either set :
∀x,s1,s2 Member(x,Union(s1,s2)) 
Member(x,s1) v Member(x,s2)
Agent that reason logically
47
Asking questions and getting
answers
Tell(KB, (∀m,c Mother(c)=m  Female(m) & Parent(m,c)))
……
Tell(KB, (Female(Maxi) & Parent(Maxi,Spot) &
Parent(Spot,Boots)))
Ask(KB,Grandparent(Maxi,Boots)
Ask(KB, ∃x Child(x, Spot))
Ask(KB, ∃x Mother(x)=Maxi)
Substitution, unification, {x/Boots}
Agent that reason logically
48