命題論理

人工知能 論理と推論(2)
知識を組み合わせて知識を生み出す
融合原理
(resolution)
論理的帰結
節形式
融合原理
論理的帰結(1):論理的帰結の定義
論理的帰結 (logical consequence)
P1, P2 ,
, Pn
が真となるどんな解釈によっても
Q
が真のとき,
Q
は
P1, P2 ,
, Pn
の論理的帰結
であるといい,つぎのように書く.
P1, P2 ,
, Pn
Q
P1, P2 , , Pn という前提が成り立つときには,
Q という結論も成り立つことが確実に言えるということ.
論理的帰結(2):真理値表による論理的帰結の判定
例
P  Q, P  Q
Q
解釈
前提
結論
P
Q
P→Q
P∨Q
Q
T
T
T
T
T
T
F
F
F
T
T
T
T
F
F
F
前提が真となるすべての解釈 のもとで結論も真
論理的帰結(3):演習問題
前提1 暑くて湿度が高ければ,雨が降るだろう.
PQ  R
前提2 湿度が高いのに暑くないということはあり得ない.
Q  P
前提3
いま,湿度が高い.
Q
論理的帰結
雨が降るだろう.
R
ヒント:解釈は8通りあるが,QがFである解釈は考える必要なし.
残りの4通りを考察する.
論理的帰結(4):論理的帰結と充足不能の関係
背理法
Q
は
P1, P2 ,
, Pn
の論理的帰結
同値
P1  P2 
 Pn  Q
は充足不能(矛盾)
論理的帰結(5):例
P  Q, P  Q
例
Q
同値
 P  Q   P  Q  Q は充足不能
解釈
前提
結論の否定
P
Q
P→Q
P∨Q
¬Q
T
T
T
T
F
T
F
F
T
T
F
T
T
T
F
F
F
T
F
T
復習 節形式(1):節形式への変換
節: リテラルの選言.
p  q  r
節形式: 節の連言.
( p  q)  ( p  q)  r
どんな論理式も以下の変換ルール(左辺を右辺に書換え)で
等価な節形式に変換できる.
節形式への変換
1
2
3
4
5
6
P  Q  ( P  Q)  (Q  P)
P  Q  P  Q
P  P
( P  Q)  (P)  (Q)
( P  Q)  (P)  (Q) ド・モルガンの法則
( P  Q)  R  ( P  R)  (Q  R) 分配則
復習 節形式(2) :節形式への変換
例
p   (q  r )
 p   ( q  r )
  p   ( q  r )
  p  ( q   r )
  p  (q   r )
 ( p  q )  ( p   r )
節形式
したがって,つぎの2つの節が得られる.
節集合
 pq
 p  r
融合原理(1)
融合原理
つぎの (1) (2) 式より (3) を導出する推論規則
P  節C
P  節D
節C  節D
(1)
(2)
(3)
融合節
符号の異なるリテラルを1個ずつキャンセルし,
残りのリテラルを結合する.
融合原理(2):例
例
モーダス・ポネンス(Modus Ponens)
P
P  Q
Q
例
対偶
Q
P  Q
P
P
PQ
Q
Q
PQ
P
融合原理(3):例
例 三段論法
PQ
QR
PR
P  Q
Q  R
P  R
例
PQ
P  Q
Q
例
P
P
空節(矛盾)
融合原理(4):導出と導出可能性
導出と導出可能性
節集合 {P1, P2 ,
, Pn }に次々と融合原理を適用し,
節の系列
P1, P2 ,
, Pn , R1, R2 ,
, Rk , Q
が得られるとき,
という.
P1, P2 ,
また, P1, P2 ,
とかく.
, Pn から Q が導き出される
, Pn から Q へ導出可能といい,
P1, P2 ,
, Pn
Q
融合原理(5):健全性
定理
任意の2つの節 C1,C2 の融合節 C は
C1,C2 の論理的帰結になっている.
証明
C1  P  C1 C2  P  C2 C  C1  C2
C1,C2 を T とする解釈を考える.
P = Fの場合:
P = Tの場合:
C1  T
C2  T
C1  C2  T
健全性:導出したものは論理的帰結になっている.
P1, P2 , , Pn
Q ならば P1, P2 , , Pn
Q
融合原理(6):完全性
健全性の別な言い方:
節集合 S から空節 □ が導き出されれば,
S は充足不能である.
逆
完全性
節集合 S が充足不能ならば
S から空節 □ を導き出すことができる.
融合原理(7):融合原理を用いた証明
Q
は
P1, P2 ,
, Pn
の論理的帰結
同値
P1  P2 
P1, P2 ,
, Pn
 Pn  Q
は充足不能
同値
節集合
S  C1,
, Ck 
は充足不能
同値
S  C1,
, Ck 
から空節を導出可能
融合原理(8):例題
例
P  Q, P  Q
Q
同値
 P  Q   P  Q  Q は充足不能
P  Q P  Q Q
Q
融合原理(9):例題
前提1 暑くて湿度が高ければ,
雨が降るだろう.
PQ  R
  P  Q  R
 P  Q  R
前提2 湿度が高いのに暑くない
ということはあり得ない.
前提3
いま,湿度が高い.
  Q  P 
 Q  P
Q
否定
論理的帰結
雨が降るだろう.
R
R
融合原理(10):例題
前提
P  Q  R
結論の否定
Q  P
Q  R
R
Q
R