数理論理学
第9回
論理的帰結
© 加藤，高田，新出
3.3節(p. 66)
述語論理の論理
式の等価性
演習課題 8 List を用いた和集合
リスト同士の和集合を求める cup (∪) を定義せよ。
二つのリストをそれぞれ List1=[Head|Tail], List2 とする。
(1) List1=[]のとき、答えは List2
(2) Head がList2のmemberかつ、TailとList2の和集合がW
ならば、List1とList2の和集合はWである。
(3) Head がList2のmemberではなく、かつ、TailとList2の
和集合がWならば、List1とList2の和集合はWの前に
Headをつけてできるリストである。
(1) List1=[]のとき、答えは List2
(2) Head がList2のmemberかつ、TailとList2の和集合がW
ならば、List1とList2の和集合はWである。
(3) Head がList2のmemberではなく、かつ、TailとList2の
和集合がWならば、List1とList2の和集合はWの前に
Headをつけてできるリストである。
(1) List1=[]のとき、答えは List2
(2) Head がList2のmemberかつ、TailとList2の和集合がW
ならば、List1とList2の和集合はWである。
(3) Head がList2のmemberではなく、かつ、TailとList2の
和集合がWならば、List1とList2の和集合はWの前に
Headをつけてできるリストである。
mother(X,Y) :- parent(X,Y), female(X).
：
：
parent(sumire, maruko).
：
female(sumire).
：
?- mother(sumire, maruko).
true
prologプログラム
の動作原理である
導出演繹の準備
∀X,Y (parent(X,Y) ∧ female(X)
⊃ (mother(X,Y))
∧mother(sumire, maruko).
A(parent)(sumire, maruko)=T
：
A(female)(sumire)=T
：
この解釈の元で、
この式が T (真)となるか
人間の知的作業による証明 (p. 64)
計算機では
ちょっと無理
∀X,Y (parent(X,Y) ∧ female(X)
⊃ (mother(X,Y))
mother(X,Y) ∨ ￢parent(X,Y)∨￢ female(X)
計算機などで自動的に上のような
式の真偽をチェックするためには、
任意の論理式を標準形(節集合)に変換する必要がある。
導出
原理
変換
∀X,Y (parent(X,Y) ∧ female(X)
⊃ (mother(X,Y))
計算機などで自動的に上のような
式の真偽をチェックするためには、
任意の論理式を標準形(節集合)に変換する必要がある。
導出
原理
変換
mother(X,Y) :- parent(X,Y), female(X).
今日
論理式 E を論理式F に変換するとき、どの
ような条件が満たされれば変換してよいか?
E= ∀X,Y (parent(X,Y) ∧ female(X)
⊃ (mother(X,Y))
F= mother(X,Y) :- parent(X,Y), female(X).
次回
論理式 E を論理式 F へ変換する手順
定理 3.1
:
:
定義 3.19
閉論理式 E と F に対して、
F が E の論理的帰結 （E F）
E
I1
I2
Im
のモデル全体
のモデルでもある。
F
I1'
EのモデルではないFのモデル
p. 54 定義3.13
定義 3.20
閉論理式 E と F に対して、
E とFが論理的に等価 (E ≡ F)
E F
F E
かつ
定理3.1
閉論理式 E と F に対して、
E ≡ F iff 任意の解釈 I に対して I(E)=I(F)
E
I1
I2
Im
のすべてのモデル
のモデルでもある。
F
I
I
I
I
I
I
重要な等価論理式 (pp. 74-75 1～24式)
例3.10
重要な等価論理式 (pp. 74-75 1～24式)
1～24の規則を使って、任意の論理式を
導出原理で扱える節形式へと変換できる
重要な等価論理式 (pp. 74-75 1～24式)
演習課題 9 定理3.1の証明
E と F が論理的に等価 (E ≡ F) である
iff ( if and only if)
任意の解釈 I に対して I(E) = I(F)
を証明せよ
甲 iff 乙
を証明するためには、
(1)甲が成り立つことを仮定し、甲が成り立つための条件を
利用して、乙が成り立つことを示す (甲 ⇒ 乙)
(2)乙が成り立つことを仮定し甲が成り立つことを示す
(甲 乙)
⇒
演習課題 9 定理3.1の証明
E と F が論理的に等価 (E ≡ F) である
iff ( if and only if)
任意の解釈 I に対して I(E) = I(F)
を証明せよ
E と F が等価であること (E ≡ F) を仮定する。
定義3.20より、F は E の論理的帰結である。よって、
定義3.19より I(E)=Tとなる任意の解釈 I に対して、
I (F)=Tである。
さらに E は F の論理的帰結なので、 I (F)= T
となる任意の解釈 I に対して、I(E)=Tである。
以上より、任意の解釈 I に対して、 I(E)= I(F)となる。
演習課題 9 定理3.1の証明
E と F が論理的に等価 (E ≡ F) である
iff ( if and only if)
任意の解釈 I に対して I(E) = I(F)
を証明せよ
(2) の証明：
任意の解釈 I に対して、 I(E)= I(F)
を仮定する。このとき I(E)= T
となる任意の解釈 I に対して、I (F)= T
である。従って、定義3.19より
F はE の論理的帰結
となり、かつ、同様に E も F の論理的帰結
となる。よって定義 3.20
より、E と F は 論理的に等価 である。
(a)
(b)
(c)
(d)
(f)
(e)
(d)
⇒