数理論理学第2回

数理論理学第4回
茨城大学工学部情報工学科
佐々木稔
前回までのあらすじ
 命題論理式の解釈
 恒真式（トートロジー）
 論理式の標準形
 決定問題
 配布資料は以下からダウンロードできます
http://sas.cis.ibaraki.ac.jp/logic/
前回の問題1
 意味の木を利用して、恒真式かどうか判定
P ⇒ (Q ∨ ～R)
P ⇒ (Q ∨ ～R)
～P
P
T ⇒ (Q ∨ ～R)
= Q ∨ ～R
F ⇒ (Q ∨ ～R)
=T
～Q
Q
T ∨ ～R = T
R
～T = F
F ∨ ～R = ～R
～R
～F = T
意味木より、トートロジーではない
前回の問題1
 意味の木を利用して、恒真式かどうか判定
(P ∧ (P ⇒ Q)) ⇒ Q
(P ∧ (P ⇒ Q)) ⇒ Q
P
(T ∧ (T ⇒ Q)) ⇒ Q
=Q⇒Q=T
～P
(F ∧ (F ⇒ Q)) ⇒ Q
=F⇒Q=T
意味木より、トートロジーである
今週のお題




命題論理の公理系
形式的証明
演繹定理
完全性定理
命題論理の公理系
 論理式の性質を調べる
 意味論的な調べ方
 命題変数の真偽から論理式の真偽を解釈
 構文論的な調べ方
 少数の公理から推論規則を用いて論理式を導く
 定理
 公理から導き出される論理式
B. Russellの公理系
 P, Q, R は任意の論理式
P ⇒ (Q ⇒ P)
(P ⇒ (Q ⇒ R))
⇒((P ⇒ Q) ⇒ (P ⇒ R))
 公理3． (P ⇒ Q) ⇒ ((P ⇒ ～Q) ⇒ ～P)
 推論規則．P ⇒ Q と P から Q を導出できる
 公理1．
 公理2．
定理の導出例1
A⇒A
 公理2 (P⇒(Q⇒R))⇒((P⇒Q)⇒(P⇒R)) で、
P = A、Q = A ⇒ A、R = A とおくと、
 (A⇒((A⇒A) ⇒A))
⇒((A⇒ (A⇒A))⇒(A⇒A))
 A ⇒ ((A ⇒ A) ⇒ A) は公理1より成り立つ
 A⇒ (A⇒A) も公理1より成り立つ
A ⇒ A の証明
 公理1より、
 A ⇒ ((A ⇒ A) ⇒ A) ・・・ ①
 A ⇒ (A ⇒ A) ・・・ ②
 公理2より、
 (A ⇒ ((A ⇒ A) ⇒ A))
⇒((A ⇒ (A ⇒ A)) ⇒ (A ⇒ A)) ・・・ ③
 ①と③から推論規則を適用して、
 (A ⇒ (A ⇒ A)) ⇒ (A ⇒ A)
・・・ ④
 ②と④から推論規則を適用して、
 A⇒A
形式的証明
 形式的証明
 公理系から推論規則を用いた定理の証明
 記述方法
 P1, P2,・・・, Pn├ P (P : 証明された論理式)
 ├ : 演繹可能を示す記号
 例
 ├A⇒A
 A, A ⇒ B, B ⇒ C ├ C
定理の導出例2
 ～P ⇒ (Q ⇒ R), ～P, Q├ R
 ～P ⇒ (Q ⇒ R), ～P から推論規則より、
Q⇒R
 Q ⇒ R, Q から推論規則より、
R (証明終わり)
定理の導出例3
 ～P ⇒ ～～Q, ～～～P├ Q
 2重否定～～P=P より、
～～～P = ～P
 ～P、～P ⇒ ～～Q より、
～～Q
 2重否定～～Q=Q より、
Q (証明終わり)
演繹定理
 A, B が論理式、
 Γは論理式の有限の列ならば、
Γ, A├ B ならば、Γ├ A ⇒ B
 逆も成り立つ
演繹定理の例1
 P∨Q, ～Q├ P
 演繹定理より、
P∨Q├ ～Q ⇒ P
 P∨Q = ～(～Q) ∨ P
= ～Q ⇒ P
演繹定理の例2
 P├ (P ⇒ Q) ⇒ Q
 演繹定理より、
P, (P ⇒ Q)├ Q
 P, (P ⇒ Q) から推論規則より、
Q
完全性定理
 Russellの公理系
 3つの公理はすべて恒真式
 推論規則も恒真式
 公理系から導出したすべての定理
 恒真式
 任意の恒真式は定理
 完全性定理
 意味論的立場と構文的立場は同等

Download Report