演習問題 (PDF)

論理学
第 14 回いろいろな論理
萩野達也
慶應義塾大学
環境情報学部
LOGIC14 (1/17)
これまで扱った論理
古典論理学
命題論理
真偽が確定している命題について取り扱う
論理結合子: 論理積・論理和・含意・否定
一階述語論理
ものの性質を表す述語を取り扱う
量化記号: 全称記号・存在記号
ペアノの自然数論
一階述語論理を用いた自然数に関する理論
ゲーデルの不完全性定理
直観主義論理学
背理法や排中律を用いない
存在性の証明には，実際に存在を示さなくてはならない
構成的数学
証明=プログラム
LOGIC14 (2/17)
自然演繹
自然演繹 (natural deduction) 体系 NJ
sequent 計算ではなく，より日常的に行なう論理推論に近い推論体系
⊃, ∧, ∨ の導入 (introduction) 規則と除去 (elimination) 規則からなる
(⊃ I)
(∧I)
(∨I)
(⊥)
[A]
.
.
.
B
(⊃ E)
A⊃B
A
B
A∧B
A
A∨B
⊥
A
(∧E)
B
A∨B
(∨E)
A
A⊃B
B
A∧B
A∧B
A
B
A∨B
[A]
.
.
.
C
[B]
.
.
.
C
C
LOGIC14 (3/17)
自然演繹における証
明例
(p ⊃ (q ⊃ r)) ⊃ ((p ∧ q) ⊃ r)
(1)
p∧q
q
(1)
p∧q
p
(2)
p ⊃ (q ⊃ r)
q⊃r
r
(1)
(p ∧ q) ⊃ r
(2)
(p ⊃ (q ⊃ r)) ⊃ ((p ∧ q) ⊃ r)
(⊃ I) および (∨E) では仮定とした論理式を取り除いて良い (取り除かなくても良い，
同じなら複数を取り除いても良い)
NJ では，¬A は A ⊃ ⊥ の省略形と考える．
定理: 任意の論理式 A に対して，A が NJ で証明可能であるときまたそのときに限り
LJ(直観主義命題論理) で証明可能である．
LOGIC14 (4/17)
述語論理の自然演繹
体系
NJ を述語論理に拡張するときには，次の 4 つの規則を加える．
(∀I)
(∃I)
A[z/x]
∀xA
A[t/x]
∃xA
(∀E)
(∃E)
∀xA
A[t/x]
∃xA
[A[z/x]]
.
.
.
B
B
LOGIC14 (5/17)
古典論理の自然演繹
体系
古典論理の自然演繹体系 NK にするには，背理法 (reductio ad absurdum) の規則を
追加する
(RAA)
[¬A]
.
.
.
⊥
A
¬¬A ⊃ A の NK における証明
(2)
(1)
¬A
¬¬A
⊥
(1)
A
(2)
¬¬A ⊃ A
定理: 任意の論理式 A に対して，A が NK で証明可能であるときまたそのときに限り
A は LK で証明可能である．
LOGIC14 (6/17)
様相論理
様相論理 (modal logic)
日常のもの事は状況や場面において真偽が変わる，
「三角形の内角の和は 180◦ である」は状況や場面に関わらず真である．
「エレベータは 3 階にある」は，現在エレベータがどこにあるかの状況によって
変わり，将来的にも真偽値は変わるかも知れない．
ある文が事実として正しいことと，それが必然的に正しいことを区別する
様相論理の論理式
A
必然的に A である
¬A
A は必然的ではない
¬A
A でないことは必然的である (A である可能性はない)
¬¬A
A である可能性がある
♦A と省略して書く
LOGIC14 (7/17)
様相論理の体系
体系 K
古典命題論理の sequent 計算の体系 LK に次の推論規則を追加した体系
Γ→A
Γ → A
K において次の式は証明可能である
A ∧ B → (A ∧ B)
(A ∧ B) → A ∧ B
A ∨ B → (A ∨ B)
(A ⊃ B) → A ⊃ B
LOGIC14 (8/17)
様相論理の公理型
様相論理では，いくつかの公理として始式として加える．
D: A ⊃ ♦A
T: A ⊃ A
4: A ⊃ A
B: A ⊃ ♦A
5: ♦A ⊃ ♦A
様相論理 S4
体系 K に公理 T と 4 を加えたもの
様相論理 S5
体系 K に公理 T と 5 を加えたもの
公理型間の関係
KB4 と KB5 は同じ様相論理である
KDB4 と KDB5 と S5 は同じ様相論理である
LOGIC14 (9/17)
様相演算に対する意味
づけ
A の時間の流れにおける解釈
A が「いつも」正しい時に，A は正しい
「いつも」の解釈が「未来はいつも」のとき
公理型 T: A ⊃ A は成り立たない (現在 A は成り立たないから)
「いつも」の解釈が「現在および未来はいつも」のとき
公理型 T: A ⊃ A は正しい
公理型 4: A ⊃ A も正しい
公理型 5: ♦A ⊃ ♦A は成り立たない
「いつも」の解釈が「過去，現在および未来はいつも」のとき
公理型 5: ♦A ⊃ ♦A は正しい
様相論理のセマンティクス (クリプキのセマンティックス)
可能世界の集合とその到達可能性の関係を用いて，可能世界ごとの真偽定める
A が可能世界 a で真であるとは，a から到達可能な世界 b すべてで A が真で
あるという意味
LOGIC14 (10/17)
直観主義論理と様相論
理の関係
ゲーデル変換あるいはマッキンゼイ・タルスキ変換 T
T (p) = p
T (A ∧ B) = T (A) ∧ T (B)
T (A ∨ B) = T (A) ∨ T (B)
T (A ⊃ B) = (T (A) ⊃ T (B))
T (¬A) = ¬T (A)
ゲーデル・マッキンゼイ・タルスキの定理
命題論理の論理式のからなる式 Γ → A が直観主義論理 LJ で証明可能となる必
要十分条件は T (Γ) → T (A) は様相論理 S4 で証明可能となることである．
LOGIC14 (11/17)
時制論理
時制論理 (tense logic) または時間論理 (temporal logic)
時間的な意味における様相論理のをさらに細かく分解
[P ]A =「過去においていつも A」
[F ]A =「未来においていつも A」
hP iA = ¬[P ]¬A
hF iA = ¬[F ]¬A
A = [P ]A ∧ A ∧ [F ]A
♦A = hP iA ∨ A ∨ hF iA
体系 Kt
A ⊃ [P ]hF iA
[P ]A ⊃ [P ][P ]A
Γ→A
[P ]Γ → [P ]A
A ⊃ [F ]hP iA
[F ]A ⊃ [F ][F ]A
Γ→A
[F ]Γ → [F ]A
追加の様相演算
A =「つぎの時点で A」
AU B =「B になるまでは A」
LOGIC14 (12/17)
内包論理
内包論理 (intensional logic)
A を「必然的に A」と解釈してきたが，それ以外のいろいろな解釈
義務論理 (deontic logic)
A を「A である義務がある」と解釈する
♦A は「A であることは許される」と解釈する
KD を用い，A ⊃ ♦A は「A である義務があるなら A である可能性がある」
は成り立つと考える
T の A ⊃ A は「A である義務があるなら A である」は一般には導かれないと
考える
知識と信念の論理 (logic of knowledge, logic of belief)
A を「A であることを知っている」と解釈する
証明可能性の論理 (provability logic)
A を「A が証明可能である」と解釈する
ゲーデルの第二不完全性定理「無矛盾であれば，無矛盾であることは証明できな
LOGIC14 (13/17)
い」¬⊥ ⊃ ¬¬⊥
ダイナミック論理
ダイナミック論理 (dynamic logic)
プログラムの仕様記述や正当性の検証で用いる
プログラム Π に対して [Π]A は「プログラム Π の実行後において A が成り立
つ」ことを表す．
Π1 ; Π2 を Π1 の後で Π2 を実行，Π∗ を Π を有限回繰り返し実行を意味するとする
[Π1 ; Π2 ]A ≡ [Π1 ][Π2 ]A
[Π∗ ]A ⊃ (A ∧ [Π][Π∗ ]A)
[Π∗ ](A ⊃ [Π]A) ⊃ (A ⊃ [Π∗ ]A)
LOGIC14 (14/17)
資源の論理
資源の論理 (resource logic)
直観主義論理体系 LJ の推論規則の weakining と contraction を許さない体系
(weakening 左)
Γ→B
A, Γ → B
(contraction 左)
A, A, Γ → B
A, Γ → B
(weakening 右)
Γ→
Γ→A
論理記号 A ⊗ B を導入
⊗左
Γ1 , A, B, Γ2 → C
Γ1 , A ⊗ B, Γ2 → C
⊗右
Γ1 → A
Γ2 → B
Γ1 , Γ2 → A ⊗ B
例: A =「500 円を支払う」, B =「文庫本 1 冊が買える」,
C =「コーヒー 1 杯が飲める」
A → B と A → C から，A ⊗ A → B ⊗ C が証明可能
A → B ⊗ C は証明可能ではない
A → B ∧ C は証明可能
LOGIC14 (15/17)
その他の論理の話題
二階述語論理および高階述語論理
一階述語論理では量化記号は対象領域を動く変数に対してのみ用いることがで
きた
二階述語論理では量化記号を述語 (対象領域の部分集合) の変数にも用いること
ができる
三階述語論理では対象領域の部分集合全体の集合の部分集合を動く変数に対して
量化記号を用いることができる
一般に n 階述語論理を定義することができ，すべての総称が高階述語論理
3 値論理とファジー論理
真と偽の 2 値ではなく，その真中の値を考えた論理が 3 値論理
真と偽の間が連続であり，付値を 0 から 1 の連続関数と考えるのがファジー論理
非単調論理 (non-monotonic logic)
単調性: 新しい知識が増えることで，すでに存在する知識が減ることはない
「鳥は一般に飛ぶことはできる」しかし「ペンギンは飛ぶことができない」
LOGIC14 (16/17)
まとめ
論理学
命題論理と一階述語論理
証明と定理
論理体系の健全性と完全性
LOGIC14 (17/17)

Download Report