論理と推論

命題論理



推論




構文と意味 → 同値関係と標準形（節形式）
決定問題と意味木
推論規則
推論の妥当性：論理的帰結
形式的証明
命題論理体系の健全性と完全性
©2008 Ikuo Tahara
1
論理による問題解決


論理式による知識の表現
証明（推論）による解決
知識
結論（答）
（論理式の集合）
推論規則
©2008 Ikuo Tahara
2
論理による問題解決
太郎は花子の父である．
次郎は太郎の父である．
父の父は祖父である．
推論規則
F (Taro, Hanako)
F ( Jiro, Taro)
xyz.[ F ( x, y )  F ( y, z )  G ( x, z )]
©2008 Ikuo Tahara
w.G( w, Hanako)
3
命題論理：構文

論理式
原子式，論理記号
( p  q )  r
論理記号
選言(disjunction)



含意(implication)

否定(negation)
連言(conjunction)

整式（well-formed formula wff)
（１）
（２）
（３）
原子式は整式である．
 は整式である ⇒   は整式である．
 ，  は整式である
⇒    ,    ,    は整式である．
（４） 以上（１），（２），（３） より整式とわかるものだけが整式である．
©2008 Ikuo Tahara
4
命題論理：意味


解釈： 原子式への真(T),偽(F)の割り当て
I ( ) {T, F}
 原子式  と解釈 I ：
論理記号の意味（真理表）
 

T T
F
T F
 
 
 
T
T
T
F
F
T
F
F T
T
F
T
T
F F
T
F
F
T
©2008 Ikuo Tahara
5
論理式の解釈
  (p  q)  r
p q r
T T F
p
q
r

T
T
T
T
T
T
F
F
T
F
T
T
TF
T
F
F
T
F
T
T
T
F
F
T
F
F
F
F
T
F
F
F
F
F
  (T  T)  F
 (F  T)  F
©2008 Ikuo Tahara
6
同値関係








二重否定の法則(law of double negation)： ( )  
  
べき等律（idempotent law)：     
相補律（complementary law）：     F （矛盾律）
    T （排中律）
    
交換律（commutative law）：       
結合律（associative law）： (  )      (   )
(   )      (   )
分配律（distributive law）：   (   )  (  )  (   )
  (   )  (   )  (   )
ド・モルガンの法則（De Morgan’s law）： (  )    
(   )    
      
 T    F  F   T  T   F 
©2008 Ikuo Tahara
7
標準形

節形式（clausal form)
(連言標準形（conjunctive normal form CNF))



リテラル（literal)： 原子式またはその否定形
節(clause)： リテラルの選言
節形式： 節の連言
( p  q  r )  (p  q)  r
リテラル
節
©2008 Ikuo Tahara
8
節形式への変換
（１）含意記号を除去する．
      
（２）否定記号を原子式の直前に移動する．
( )  
(  )    
(   )    
（３）分配律を適用する．
  (   )  (   )  (   )
©2008 Ikuo Tahara
9
恒真式と恒偽式
論理式全体
恒真式
充足可能
恒偽式
充足不能
©2008 Ikuo Tahara
10
決定問題

決定問題（decision problem)
所与の論理式が恒真か否かを決定する問題
→ 命題論理式の場合，有限時間で決定可能

意味木（semantic tree）
[ p1 , p2 , , pn ]
p1  T
p1  F
[T, p2 , , pn ] [F, p2 , , pn ]
©2008 Ikuo Tahara
11
意味木
  ( p  ( p  q))  q
pF
pT
(T  (T  q))  q
 (T  q)  q
qT
qF
(F  (F  q))  q
Fq
T
(T  T)  T
(T  F)  F
TT
FT
T
T
p
T
T
F
F
©2008 Ikuo Tahara
q
T
F
T
F

T
T
T
T
12
推論

推論（inference, reasoning)
前提（premise）から結論（conclusion）を導くこと
前提① 鳥は卵を産む．
前提① 鳥は卵を産む．
前提② 鶏は鳥である．
前提② 猫は鳥である．
結論
結論
鶏は卵を産む．
前提①
健全（sound）な推論
前提②
結論
QR
PQ
PR
©2008 Ikuo Tahara
猫は卵を産む．
妥当（valid）な推論
13
推論の形式（推論規則）

肯定式（modus ponendo ponens)
（前提）
 


否定式（modus tollend tollens）
（前提）
 


（結論）

（結論）

三段論法（syllogism）
（前提）
    
（結論）

©2008 Ikuo Tahara
14
推論の妥当性

論理的帰結（logical consequence）
（前提）
  {1 ,
（結論）
, n }

前提   {1 ,2 , ,n } が真となる任意の解釈において
結論  も真となる．
‘ 
©2008 Ikuo Tahara
15
論理的帰結
{1 ,2 ,
, n } ‘ 
(1  2 
 n ) 
：恒真
((1  2 
 n )  )
：恒偽
 (1  2 
 n )  
：充足不能
©2008 Ikuo Tahara
16
推論規則と恒真式
推論規則
前件肯定規則
前提   
結論 

恒真式
前件肯定式
((  )   ) 
対偶法
前提   
結論   
対偶律
選言除去規則（Dilemma規則）
前提         
結論 
選言除去式
選言三段論法
前提   
結論 
選言三段論法式

仮言三段論法
前提      
結論   
(   )  (   )
((   )  (   )  (   ))  
((   )   ) 
推移律
((  )  (   ))  (   )
©2008 Ikuo Tahara
17
形式的証明

恒真式の集合
演繹体系
公理系
(A1)   (    )
(A2) (  (    ))  ((   )  (   ))
(A3) (   )  (   )
定理
推論規則
(MP)  ,  
恒真式
 
妥当な推論
©2008 Ikuo Tahara
18
証明可能

形式的証明
公理系＋推論規則 → 


演繹定理
  {}     
仮説からの演繹
公理＋仮説  ＋推論規則 → 
 
©2008 Ikuo Tahara
19
命題論理体系の性質

公理系の無矛盾性（consistency）
いかなる論理式  についても  と   が
ともに証明可能となることはない．

健全性（soundness）
    ‘ 

完全性（completeness）
 ‘    
©2008 Ikuo Tahara
20

人工知能の基礎知識

No1