命題論理

人工知能論理と推論（１）
知識を組み合わせて知識を生み出す
命題論理
(Propositional Logic)
人工知能と論理
命題論理の構文
命題論理の意味
節形式
なぜ人工知能で論理を学ぶのか
なぜ人工知能で論理 (LOGIC)を学ぶのか．
言
語としての論理 ⇒ 構文，意味
アルゴリズムとしての論理 ⇒ 推論
知識ベース
知識
TELL, ASK
知識
知識
知識表現言語 (=LOGIC)
推論
アルゴリズム
(= LOGIC)
いろいろな論理と推論がある
完全な知識に基づく数学的な推論
命題論理：命題（文）を１つの記号で表現
述語論理：オブジェクトとその関係を記号で表現
不確実な知識に基づく推論
ファジィ推論：あいまいで主観的な知識を扱う
確率推論：観測事実から命題が真である確率を計算
知識が欠けているときの推論
帰納推論：多数の観測事実から一般法則を導く
仮説推論：観測事実を説明できる仮説や信念を導く
就職試験に見る命題論理（１）
次の①～③はいずれも事実であるとする．
①お風呂が好きな人は，きれい好きである．
②歯みがきが好きな人は，お風呂が好きである．
③お酒が好きな人は，タバコが好きであり，しかも歯みがきが好
きである．
このとき，次のア～オの中で確実にいえることをすべて選べ．
ア．歯みがきが好きな人は，タバコが好きである．
イ．お酒が好きな人は，歯みがきが好きである．
ウ．タバコが好きな人は，きれい好きである．
エ．タバコが好きでない人は，お風呂が好きでない．
オ．きれい好きでない人は，お酒が好きでない．
就職試験に見る命題論理（２）論理式
知識を記号を使った論理式で簡潔に表現する
①お風呂→きれい
②歯みがき→お風呂
③お酒→タバコ∧歯みがき
ア．歯みがき→タバコ
イ．お酒→歯みがき
ウ．タバコ→きれい
エ．タバコ→お風呂
オ．きれい→お酒
就職試験に見る命題論理（３）推論規則
P→Q
対偶
Q→P
P→Q
Q→R
三段論法
P→R
P→Q∧R
P→Q
P→R
P→Q
P
モーダスポネンス
Q
就職試験に見る命題論理（４）推論
お風呂
歯みがき
お酒
きれい
タバコ
ア．歯みがき→タバコ
イ．お酒→歯みがき
ウ．タバコ→きれい
エ．タバコ→お風呂
オ．きれい→お酒
命題論理の構文（１）構文要素
構文要素を一定の規則で並べると論理式となる．
命題論理の構文要素
論理定数： true と false
命題記号：それ以上分解できない命題（原始命題）
を表す記号．p, q, r など．
論理記号：命題を結合して複合した命題を作る記号．





AND
かつ
連言
OR
または
選言
NOT
でない
否定
IMPLY
ならば
含意
EQUIV
等しい
同値
命題論理の構文（２）論理式
論理式：原始命題を論理記号でつないだ文．
論理式
論理定数は論理式である．
true false
命題記号は論理式である．
P
P が論理式ならば， (P ) は論理式である．
P が論理式ならば，以下の４つも論理式である．
( P  Q) ( P  Q) ( P  Q) ( P  Q)
例
p  ((q  (r )))
p  (q(r ))
は論理式である．
は論理式でない．
命題論理の構文（３）論理式（続き）
リテラル
命題記号はリテラルである．
 命題記号
はリテラルである．
p
p
正リテラル
負リテラル
カッコの省略ルール
論理記号の優先順位
∧と∨の結合則の利用
例
    
(( p  q)  r )  p  q  r
((p)  (((q  r ))  s)) のカッコを省略すると
p  (q  r )  s
命題論理の意味（１）：解釈の概念
解釈：論理式を真偽に対応付ける写像
論理式
（構文領域）
true
false
p
q
p
pq
真偽値
（意味領域）
解釈
T (真)
F (偽)
命題変数 p,q,.. の解釈だけは
自由に決められる．.
命題論理の意味（２）：論理式の解釈
命題変数
p,q,.. の解釈を決めると，他の論理式の解釈は：
true の値はT（真）， false の値はF（偽）
(P ) の値は P の値の逆．
( P  Q) ( P  Q) ( P  Q) ( P  Q)
の値は，以下の真理値表に基づいて決める．
P
Q
P∧Q
P∨Q
P→Q
P Q
T
T
T
T
T
T
T
F
F
T
F
F
F
T
F
T
T
F
F
F
F
F
T
T
命題論理の意味（３）：論理式の解釈
例
p  T , q  F, r  T
p  T, q  T, r  F
のとき
のとき
( p  q)  r
 (T  F )  T
 F T
T
( p  q)  r
 (T  T )  F
T  F
F
命題論理の意味（４）：恒真
恒真どんな解釈をしても真
p  p
例
( p  q)  (p  q)
￢p ￢p∨q (p→q)(￢p∨q)
p q
p→q
T T
T
F
T
T
T F
F
F
F
T
F T
T
T
T
T
F F
T
T
T
T
命題論理の意味（５）：充足不能と充足可能
充足不能どんな解釈をしても偽
例
p  p
充足可能ある解釈のもとで真
例
pq
充足不能
充足可能
p  p
pq
恒真
p  p
命題論理の意味（６）：論理的帰結
論理的帰結
P1, P2 ,
, Pn
のすべてが真となるどんな解釈によっても
Q
が真のとき，
Q
は
P1, P2 ,
, Pn
の論理的帰結
であるといい，つぎのように書く．
P1, P2 ,
例
P  Q, Q  R
, Pn
Q
PR
節形式（１）：節形式への変換
節：リテラルの選言．
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) 分配則
節形式（２）：節形式への変換
例
p   (q  r )
 p   ( q  r )
  p   ( q  r )
  p  ( q   r )
  p  (q   r )
 ( p  q )  ( p   r )
節形式
したがって，つぎの２つの節が得られる．
節集合
 pq
 p  r
節形式（３）：節形式と if-then ルール
節は if-then ルールに対応する．
負リテラル＝条件の AND
 pq 
 p  q  r 
p  q (if p then q)
p  q  r (if p & q then r )
節形式（4）：節形式と if-then ルール（特殊ケース）
正リテラル＝結論の OR
 p  q  r  s

pq rs
p  q  true  p  q
 p  q 
p  q  false
 true  false
空節
矛盾

Download Report