命題論理

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