命題論理のメモ3
大変長らくお待たせいたしました、改稿終了です。
変更内容:二章「命題論理の文法編」から記号の大幅変更、定義定理の追加、エピソードの削除変更など。
お手数おかけしますが、二章「命題論理の文法編」から読み直しを推奨いたします。
○エルフの村-エーリルの家
エーリル
「ところでド・モルガンって黒魔法なのかな」
ディアナ
「黒魔法はよくわかりませんね。
でも魔法じゃないと思いますよ、ド・モルガン」
■thm0.0(⇒の反射性)
{} |- (φ⇒φ)
proof
1 φ [ax]
2 (φ⇒φ) [⇒in 1 el 1]
■
エーリル
「はー！ その手があったか！」
ディアナ
「thm0.0ってことは最初に証明したんですよね」
エーリル
「そうそう。最初は5行くらいの証明だったのよね。
⇒in elが演繹定理だから、演繹定理が壊れ定理ってことが証明されてしまった」
ディアナ
「……壊れ定理？」
■thm0.25(⇒の推移性/三段論法)
{(φ⇒ψ),(ψ⇒ρ)} |- (φ⇒ρ)
proof
1 φ [ax]
2 (φ⇒ψ) [ax]
3 ψ [⇒el 1,2]
4 (ψ⇒ρ) [ax]
5 ρ [⇒el 3,4]
6 (φ⇒ρ) [⇒in 5 el 1]
■
エーリル
「三段……魔法？」
ディアナ
「そう書いてるんですか？
論理式以外読めないのでわかりませんけど、信用できませんね」
エーリル
「えぇ……」
■thm0.26(⇔の反射性)
{} |- (φ⇔φ)
proof
1 (φ⇒φ) [⇒の反射性]
2 (φ⇔φ) [⇔in 1,1]
■
ディアナ
「⇔も⇒と似てるんですね」
エーリル
「今なら⇔の推移性も証明できる気がする。
【黒魔法ド・モルガン】！」
■thm0.27(⇔の推移性)
{(φ⇔ψ),(ψ⇔ρ)} |- (φ⇔ρ)
proof
1 (φ⇔ψ) [ax]
2 (ψ⇔ρ) [ax]
3 φ [ax]
4 ψ [⇔elL 3,1]
5 ρ [⇔elL 4,2]
6 (φ⇒ρ) [⇒in 5 el 3]
7 ρ [ax]
8 ψ [⇔elR 2,7]
9 φ [⇔elR 1,8]
10 (ρ⇒φ) [⇒in 9 el 7]
11 (φ⇔ρ) [⇔in 6,10]
■
ディアナ
「ド・モルガン関係ないですね」
エーリル
「おかしいな。ド・モルガンが来ると思ったんだけど」
ディアナ
「今は必要ないので」
エーリル
「えぇ……」
■thm0.28(⇔の可換性)
{(φ⇔ψ)} |- (ψ⇔φ)
proof
1 (φ⇔ψ) [ax]
2 ψ [ax]
3 φ [⇔elR 1,2]
4 (ψ⇒φ) [⇒in 3,2]
5 φ [ax]
6 ψ [⇔elL 5,1]
7 (φ⇒ψ) [⇒in 6,5]
8 (ψ⇔φ) [⇔in 4,7]
■
ディアナ
「⇔、∧、∨は可換性があるんですね」
エーリル
「⇒は……無理そうな気がする。
なんで無理かはわからない」
ディアナ
「天々城さんに聞いてみてはいかがですか？」
エーリル
「ナイス。ちょっと草食べてくる」
■ここまでの参考文献と読書案内
[1]菊池誠, 不完全性定理, 共立出版, 2014.
作者が主に参考にしている本です。
Hibert流の命題論理から議論をしています。
タイトルは不完全性定理ですが、論理学の入門書としてもオススメです。
[2]鹿島亮, 数理論理学, 朝倉書店, 2010.
こちらは自然演繹で議論を進めています。
数学の証明をキチンと書けるようになりたいならオススメです。
[3]結城浩, 数学ガール ゲーデルの不完全性定理, ソフトバンククリエイティブ, 2011.
文章キレッキレで萌えるストーリー構成。
不完全性定理は誤用が多い定理なんですが、この本が出版されたあたりから流れ変わったなと感じるくらいの内容です。
