Document

鬼はどこですか？
• Propositional logic (cont…)
命題論理
• Reasoning where is wumpus
鬼がいる場所を推理する
1
limination
introduction
negation
resolution
complex
atomic
conjunction
disjunction
time-dependent
2
elimination
削除
introduction
導入
negation
否定
resolution 解決
atomic
原子の
referent
指示物
conjunction
disjunction
連結
分離
dependent 従属関係の
3
命題論理: 意味論
• 論理積
A∧B
AかつB
• 論理和
A∨B
AまたはB
• 否定
￢A
Aでない
• 含意
A⇒B
AならばBを意味する
• 同等
A⇔B
(AならばB)かつ(BならばA)
S1 is true,
then S2 is true.
S1 is false,
then S2 is either true or false
S1
S2
S1  S2
white  false
S1
S2
S1  S2
S1 is true,
then S2 is true.
S1 is false,
then S2 is false
white  false
4
This relation between sentences is called entailment.
A |= B
This relation between sentences is called implication.
A B
AならばB」(A→B)は、Aが真ならばBが真のときだけ真、A
が偽ならばBの真偽にかかわらず真となります。
A is true,
then B is true.
A is false,
then B is either true or false
5
課題：真偽値の計算
p = T, q = F, r = Tのとき
p = T, q = F, r = Fのとき
(p  q)  r
(p  q)  r
p = F, q = F, r = Tのとき
p = F, q = F, r = Fのとき
(p  q)  r
(p  q)  r
Seven inference rules for propositional Logic
• Modus Ponens
• And-Elimination
  , 

1  2 … n
i
• And-Introduction
1, 2, …, n
1  2 … n
• Or-Introduction
i
1  2  …  n
• Double-Negation Elimination
• Unit Resolution
• Logic connectives:


  ,  

  ,    

(α または β , not β ) → α
(α または β , not β または γ ) →
α または γ である
7
The knowledge base
Percept sentences:
there is no smell in the square [1,1]  S1,1
there is no breeze in the square [1,1]  B1,1
there is no smell in the square [2,1]  S2,1
there is breeze in the square [2,1]  B2,1
there is smell in the square [1,2]
 S1,2
there is no breeze in the square [1,2]  B1,2
s
w
p
s b
g
s
A
p
b
b
p
b
8
The knowledge base
knowledge sentences:
If a square has no smell, then neither the square nor any of its adjacent squares can house
a wumpus.
R1: S1,1  W1,1  W1,2  W2,1
R2: S2,1  W1,1  W2,1  W2,2  W3,1
If
there is smell in [1,2], then there must be a wumpus in [1,2] or in one or more of the
neighboring squares.
R3: S1,2  W1,3  W1,2  W2,2  W1,1
If a square has no breeze, then neither the square nor any of its
adjacent squares can have a pit.
s
p
R4: B1,1  P1,1  P1,2  P2,1
R5: B1,2  P1,1  P1,2 P2,2  P1,3
If
there is breeze in [2,1], then there must be a pit in [2,1] or in
one or more of the neighboring squares.
R6: B2,1  P3,1  P2,1  P2,2  P1,1
w
s b
g
s
A
p
b
b
b
p
9
Inferring knowledge using propositional logic
Concerning with the 6 squares, [1,1], [2,1], [1,2], [3,1], [2,2], [1,3], there are 12
symbols,
S1,1, S2,1, S1,2, B1,1, B2,1, B1,2, W1,1, W1,2, W2,1, W2,2, W3,1, W1,3
The process of finding a wumpus in [1,3] as follows:
1  2 … n
1. Apply R1 to S1,1, we obtain
i
W1,1  W1,2  W2,1
  ,  

2. Apply And-Elimination, we obtain
W1,1
W1,2
W2,1
3. Apply R2 and And-Elimination to S2,1, we obtain
W1,1 W2,2
W2,1
W3,1
R4: S1,2  W1,3  W1,2  W2,2  W1,1
4. Apply R3 and the unit resolution to S1,2, we obtain ( is W1,3W1,2 W2,2 and  is W1,1 )
W1,3  W1,2  W2,2
5. Apply the unit resolution again, we obtain ( is W1,3 W1,2 and  is W2,2 )
W1,3  W1,2
6. Apply the unit resolution again, we obtain ( is W1,3 and  is W1,2 )
W1,3
Here is the answer: the wumpus is in [1,3], that is, W1,3 is true.
s
w
p
s b
g
s
A
p
b
b
10
p
b
Problem with propositional logic
• Too many propositions 
too many rules to define a competent agent
• The world is changing, propositions are changing with time. 
do not know how many time-dependent propositions we will need
have to go back and rewrite time-dependent version of each rule.
The problem with proposition logic is that it only has one
representational device: the proposition!!!
The solutions to the problem is to introduce other logic
first-order logic
That can represent objects and relations between objects in addition to
propositions.
11

Download Report