2015年度 情報論理学 第 1回講義

2015 年度 情報論理学 第 1 回講義
2015 年 4 月 14 日 (火)
青戸等人 (東北大学 電気通信研究所)
目次
-
講義の情報
はじ めに ∼論理と は∼
論理学概観 ∼論理学の歴史を 振り 返り ながら ∼
講義概要
1
情報論理学 講義情報 (1)
講義の進め方
プリ ン ト 教材あり .
講義ホームページよ り ダウ ン ロ ード 可能.
演習問題あり .
講義と 間を おかずに復習する のが望ま し い. 期末試験
は演習問題を 解いて おけば解ける 程度の難易度.
教科書・ 参考書
教科書: なし
参考書:
前原昭二著「 記号論理入門」 (日本評論社)
小野寛晰著「 情報科学における 論理」 (日本評論社)
2
そ の他の (英語の) 参考書
定評のある 参考書は前出の小野先生の本の最後を 参照.
• 講義の内容に近い参考書: Dirk van Dalen, Logic and
Structure (3rd ed.), Springer-Verlag, 1991.
• ト ピ ッ ク も 広く 書き 方も 非常に 優れた参考書 (ただ
し , 数学書の読み方に慣れて いないと 難し い ): Herbert B.
Enderton, A Mathematical Introduction to Logic (3rd
ed.), Academic Press, 2001.
• プロ グラ ムを 使っ て 説明し て いる 本 (プロ グラ ム好き の
人には良いかも ): John Harrison, Handbook of Practical
Logic and Automated Reasoning, Cambridge University
Press, 2009.
3
情報論理学 講義情報 (2)
ホームページ
http://www.nue.riec.tohoku.ac.jp/
user/aoto/lecture/15Logic/
(講義資料や連絡など . 随時更新予定)
オ フ ィ スア ワ ー
[email protected] ま でメ ールで予約.
成績評価の方法
主に期末試験の結果によ っ て 評価する . ノ ート ・ 資料・ 参
考書持ち 込み可 (iPad,PC 等は不可), 再試験は行わない.
出席確認や復習問題の解答提出を 課し た場合, 出席点と
し て 評価する .
4
目次
-
講義の情報
はじ めに ∼論理と は∼
論理学概観 ∼論理学の歴史を 振り 返り ながら ∼
講義概要
論理学と は
論理学は「 推論の方法と そ の正し さ 」 について の学問.
「 真な論理式と は, 論理的な推論に従っ て 導かれる 論理
式のこ と である .」
ど のよ う に論理的な推論に従っ て 導かれたかを 示すも の
を 証明と よ ぶ.
こ こ でいう 論理, こ の講義で学習する 論理は, よ り 厳密
には数理論理学と よ ばれる も の. よ り 幅広い論理学の文脈
では, 論理的な推論は演繹的推論と よ ばれる .
5
社会現象
自然現象
理論
数学
論理
6
+---------+
| "理論" |
+----+---------+----+
|
数学
|
+-----+-------------------+------+
|
論理学
|
-----+--------------------------------+----さ ま ざま な場面で , 理論的な解析を 使う こ と があ る が,
そ の道具は数学. 数学のど のよ う な分野を 用いる かはいろ
いろ だが (ある いは, “数学” に は通常含ま れて ないよ う な
分野かも し れない. オ ート マ ト ン , ア ルゴリ ズム , プロ グ
ラ ム意味論, etc.), 数学を き ち んと 使いこ なすには, 数学
の基礎と なる 論理学 (論理的な推論の理解と やり 方, 数学の
仕組み・ 証明の仕方) を 身につける 必要がある .
7
論理的な推論 (Logical Reasoning) と は
何か物事が正し いと 判断する ま でには, いろ いろ な理由
がある .
• 両親や先生から 教え ら れた
• 観察・ 分析の結果
• さ ま ざま な科学的な実験結果と の整合性がと れて いる
8
9
10
論理的な推論と は
• 推論方法の『 根本』 に焦点
• 絶対確実な推論のみ
• 後に正し く なく なる よ う なこ と がある も のは対象外
11
論理的な推論と は
論理的な推論の例:
「 すべて の人は死ぬ.
ソ ク ラ テスは人である .
従っ て , ソ ク ラ テスは死ぬ.」
「 すべて の鳥は嘴を も つ.
ペン ギン は鳥である .
従っ て , ペン ギン は嘴を も つ.」
こ れら の, 2 つの前提から 1 つの結論を 導いて いる 際に
使っ て いる 推論が論理的な推論の例.
12
論理的な推論と は
こ れら の推論はど れも
「 すべて の X は Y である .
a は X である .
従っ て , a は Y である .」
のよ う な一般形を も つ.
論理的な推論と は, 個々 の言明の内容ではなく , 言明の
一般的な形に基づく 推論
13
論理的な推論
論理的な推論ではない例:
「 すべて の人は死ぬ.
ソ ク ラ テスはギリ シ ャ 人である .
従っ て , ソ ク ラ テスは死ぬ.」
導かれて いる 結論は正し いが, 論理的な推論で はない.
なぜなら , 結論の正し さ は,『 ソ ク ラ テス』 や『 死ぬ』 と いっ
た内容に依存し て いる から .
14
論理的な推論
「 すべて の人は死ぬ.
ソ ク ラ テスはギリ シ ャ 人である .
従っ て , ソ ク ラ テスは死ぬ.」
こ の場合は, 少し 推論ステッ プを 補足する こ と で正し い
論理的な推論にする こ と が出来る .
「 すべて の人は死ぬ.
すべて のギリ シ ャ 人は人である .
ソ ク ラ テスはギリ シ ャ 人である .
従っ て , ソ ク ラ テスは死ぬ.」
数学のすべて の命題は, こ のよ う な正し い論理的な推論
によ っ て 得ら れる .
15
「
「
「
「
有限個の開集合の共通部分は開集合である 」
ラ ムダ計算は合流性を も つ」
集合 A と B が可算であればそ の直積も 可算である 」
任意の帰納的部分順序集合は極大元を も つ」
こ れら は現代的な数学で意味のある 命題. ほと んど の人
には, こ れら の命題のほと んど はおま じ ないのよ う に意味
を も たないかも し れない.
さ ま ざま な用語の定義はそ の分野を 勉強し ないと わから
ないが, 用いる 論理的な推論はす べて 共通. ど のよ う な命
題も 論理的な推論ステッ プを 1 つ 1 つ辿る こ と で示せる .
16
日本の初等教育で論理的な推論を 鍛え る 代表選手は, 中
学の幾何の問題.
A
D
O
B
C
|AB| = |DC| かつ |AC| = |DB| と する と き ,
(1) △ABC と △DCB が合同である こ と を 示せ.
(2) △ABO と △DCO が合同である こ と を 示せ.
17
三角形の合同条件:
(a) 3 辺の長さ がそ れぞれ等し い.
(b) 2 辺の長さ と そ の間の角がそ れぞれ等し い.
(c) 1 辺の長さ と そ の両端の角がそ れぞれ等し い.
つま り , 以下のよ う な推論が正し い
「 3 辺の長さ がそ れぞれ等し い ⇒ 2 つの三角形は合同」
「 2 辺の長さ と そ の間の角がそ れぞれ等し い ⇒ 2 つの三角
形は合同」
「 1 辺の長さ と そ の両端の角がそ れぞれ等し い ⇒ 2 つの三
角形は合同」
18
推論ステッ プを 1 つ 1 つ辿る こ と で示せる .
(仮定よ り ) |AB| = |DC| かつ |AC| = |DB| (1)
(等号の性質よ り ) |BC| = |BC| (2)
((1),(2) と 合同条件 (a) よ り ) △ABC と △DCB が合同 (3)
((3) と 合同性の性質よ り ) |AB| = |DC| (4)
((3) と 合同性の性質よ り ) ∠OAB = ∠ODC (5)
((3) と 合同性の性質よ り ) ∠ABC = ∠DCB (6)
((3) と 合同性の性質よ り ) ∠ACB = ∠DBC (7)
((6),(7) と 減算の性質よ り )
∠ABO = ∠ABC − ∠DBC
= ∠DCB − ∠ACB = ∠DCO (8)
((5),(6),(8) と 合同条件 (c) よ り ) △ABO と △DCO が合同
19
20
「 言葉と ルールがある 」
※ ルールを 知ら ないと き ち んと ゲームはでき ない.
※ ゲームで使われる 言葉を 知ら ないと ルールは理解でき な
い.
21
「 言葉と ルールがある 」
※ ルールを 知ら ないと き ち んと ゲームはでき ない.
※ ゲームで使われる 言葉を 知ら ないと ルールは理解でき な
い.
「 数学的な考え 方を 身につければ数学は出来る .」
「 論理学は数学の言葉であり ルールである 」
※ 「 証明ができ る よ う になる には数学的な考え 方がわかれ
ばよ い」 かも し れないが, 論理学の言葉と ルールを き ち ん
と 知れば数学の証明が*き ち んと *出来る .
「 意見や 見解の相違」 に 終わっ て し ま う 議論で はなく ,
「 何が正し く (証明がある ), 何が正し く なく (反例がある ),
何が未解決問題なのか」 の白黒がつく のが, 理論.
22
なぜ論理学を 学ぶのか
「 知っ て いる 」
———————
• 人が言っ て いる か
ら ...
• 教科書に書いて あ
る から ...
• 先生が言う から ...
≪
「 知っ て いる 」
———————
• そ の結論が出て く る
ま で の, 仮定と 推論過
程を 辿る こ と ができ る
• 実験事実と 理論的な
仮定の区別ができ る
• 実験事実や 理論的な
仮定と , (ま だわかっ て
いない ) 真実と の区別が
でき る
23
目次
-
講義の情報
はじ めに ∼論理と は∼
論理学概観 ∼論理学の歴史を 振り 返り ながら ∼
講義概要
(お断り ) 以下で紹介する 歴史の話は, 講義内容を 俯瞰する ための参考に紹介する
も のであり , 史実の確かさ について 保証す る も のではあり ま せん.
23
ア リ スト テレ ス論理学
論理学の始ま り と いわれて いる のはギリ シ ャ のア リ スト
テレ ス (Aristotle, B.C.384–322).
「 すべて の人は死ぬ.
ソ ク ラ テスは人である .
従っ て , ソ ク ラ テスは死ぬ.」
ア リ スト テレ ス論理学はそ の後 17 世紀ま で論理学の基礎
であっ た.
24
ア リ スト テレ ス論理学
ア リ スト テレ スは, 以下の 4 つのタ イ プの言明について ,
syllogism と よ ばれる 推論がど のよ う な場合に 正し いか議
論し た.
All X is Y
No X is Y
Some X is Y
Some X is not Y
25
ア リ スト テレ ス論理学
以下は正し い論理的な推論か?
(1) All X is Y
Therefore, All non-Y is non-X
(2) All X is Y
No Z is Y
Therefore, No Z is X
(3) All X is Y
Some Z is Y
Therefore, Some Z is non-X
26
Venn Diagrams ベン 図
(Venn, 1881) 論理的な推論はベン 図を 使う と 考え やす
い.
A
27
Venn Diagrams ベン 図
B
28
A と B の積 (共通部分)
A∩B
29
A と B の和 (合併)
A∪B
30
A の反転
A◦
31
B の反転
B◦
32
ド ・ モルガン の法則 (1)
(A ∪ B)◦ = A◦ ∩ B ◦
33
ド ・ モルガン の法則 (2)
(A ∩ B)◦ = A◦ ∪ B ◦
34
部分集合 (A ⊆ B)
B
A
A⊆B ⇔A∩B =A⇔A∪B =B
⇔ A ∩ B ◦ = 0 ⇔ A◦ ∪ B = 1
(こ こ で, 0 は空集合, 1 は全体集合を 表す. )
35
ア リ スト テレ ス論理学 (再)
前の推論 (2) を ベン 図を 使っ て 考え て みる と ?
All X is Y
No Y is Z
Therefore, No X is Z
X⊆Y
Y ∩Z =0
Therefore, X ∩ Z = 0
こ の推論にはど んな法則が使われて いる だろ う か?
36
Algebra ’al-jabr’
Algebra(代数) と いう と 現在で は抽象代数を 指す が, 語
源はア ラ ビ ア 語の’al-jabr’:
式の変形によ っ て 等式の解を 得る 方法
1+x=3−x
⇒ 2x = 3 − 1
⇒ 2x = 3 − 1
⇒ x=1
37
Algebra ’al-jabr’
Algebra(代数) と いう と 現在で は抽象代数を 指す が, 語
源はア ラ ビ ア 語の’al-jabr’:
式の変形によ っ て 等式の解を 得る 方法
1+x=3−x
⇒ 2x = 3 − 1
⇒ 2x = 3 − 1
⇒ x=1
論理推論を 式変形のよ う に簡単にでき ないか.
37
X⊆Y
(1)
Y ∩Z =0
(2)
Therefore, X ∩ Z = 0
By
By
By
By
By
By
By
(1)
(3)
(2)
(4),(5)
(6)
(7)
(8)
X ∩Y◦ =0
X ∩Y◦∩Z =0
X ∩Y ∩Z =0
(X ∩ Y ∩ Z) ∪ (X ∩ Y ◦ ∩ Z) = 0
(X ∩ Z) ∩ (Y ∪ Y ◦) = 0
(X ∩ Z) ∩ 1 = 0
X ∩Z =0
(3)
(4)
(5)
(6)
(7)
(8)
38
ジョ ージ ・ ブ ール
(George Boole, 1815-1864)
(画像はウ ィ キ ペディ ア よ り 引用)
39
ブ ール代数
式変形にも と づく 論理推論, “論理の代数”
A. De Morgan (Formal Logic, 1874), George Boole
(Calculus of Thought, 1854), C.S. Pierce, Ernst
Schr¨
oder (The Algebra of Logic, 1890), W.S.Jevons
(Pure Logic, 1864; Elementary Lessons in Logic, 1870).
1.
2.
3.
4.
5.
6.
X
X
X
X
X
X
∪X =X
∩X =X
∪Y =Y ∪X
∩Y =Y ∩X
∪ (Y ∪ Z) = (X ∪ Y ) ∪ X
∩ (Y ∩ Z) = (X ∩ Y ) ∩ X
40
7. X ∩ (X ∪ Y ) = X
8. X ∪ (X ∩ Y ) = X
9. X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z)
10. X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z)
11. X ∪ X ◦ = 1
12. X ∩ X ◦ = 0
13. (X ◦)◦ = X
14. X ∪ 1 = 1
15. X ∩ 1 = X
16. X ∪ 0 = X
17. X ∩ 0 = 0
18. (X ∪ Y )◦ = X ◦ ∩ Y ◦
19. (X ∩ Y )◦ = X ◦ ∪ Y ◦
41
数学のおける 公理化
19 世紀後半になっ て 数学のさ ま ざま な概念に厳密な定義
が取り 入れら れる よ う になっ て き た.
非ユーク リ ッ ド 幾何学 (ロ バチェ フ ス キ ー (1829 年), ボー
ヤ イ (1832)) と ユーク リ ッ ド 幾何学・ 非ユーク リ ッ ド 幾何
学の公理化
直線上の点は「 互いに触れ合う 2 片の境界」 によ り 確定さ れ
る (ア リ スト テレ ス )
⇒ 切断によ る 実数の定義 (Dedekind, 1872)
⇒ 有理数のコ ーシ ー列によ る 実数の定義 (Cantor, 1883)
集合にも と づく 自然数論の公理化 (Dedekind, 1888)
ユーク リ ッ ド 幾何の公理 ⇒ ヒ ルベルト の公理 (Hilbert,1899)
42
記号の導入と 命題の形式化
Peano によ る Formulario mathematico プロ ジェ ク ト :
「 論理学や数学に記号を 取り いれ, すべて の知ら れて い
る 数式や定理を 記述でき る 標準的な数学の書式を 作ろ う .」
• ∩, ∪, ∈, ⊆ など の記号を 導入.
• Formulario mathematico (1895 に初版を 出版, 1908
に第 5 版を 出版)
’al-jabr’ のプリ ン シ プルを 数学のも っ と 広い範囲へ
43
ジュ ゼッ ペ・ ペア ノ
(Giuseppe Peano, 1858–1932)
(画像はウ ィ キ ペディ ア よ り 引用)
44
フ レ ーゲによ る 論理学の刷新
1884 年 『 算術の基礎』
1893 年 『 算術の基本法則』 第 1 巻
1903 年 『 算術の基本法則』 第 2 巻
「 論理に基づいて ど こ ま で数学が展開でき る のだろ う か」
多く
•
•
•
•
の革新的なア イ デア で現代の論理学の基礎を 構築
真理値 (真と 偽) の導入
関数と 引数に分解し た命題の導入
論理変数と 量化子の導入
証明体系の導入
45
ア リ スト テレ ス論理学を 一般化
「 すべて の人は死ぬ.
ソ ク ラ テスは人である .
従っ て , ソ ク ラ テスは死ぬ.」
「 ∀x (P x → Q x) ⇒ P a ⇒ Q a」
当時の数学を 展開でき る 論理の体系を 与え たよ う に見え
たが, そ の体系には矛盾がある こ と が判明 (ラ ッ セルのパラ
ド ッ ク ス ).
ア イ デア も 記法も 非常に難解であっ たため, そ の仕事は
なかなか知ら れる こ と がなかっ た.
46
ゴッ ト ロ ープ・ フ レ ーゲ
(Gottlob Frege, 1848 − 1925)
(画像はウ ィ キ ペディ ア よ り 引用)
47
ラ ッ セルのパラ ド ッ ク ス
”Hardly anything more unfortunate can befall a scientific writer than to
have one of the foundations of his edifice shaken after the work is finished. This
was the position I was placed in by a letter of Mr. Bertrand Russell, just when
the printing of this volume was nearing its completion.”
「 学問的著作に携わる も のにと っ て ..., 自ら の仕事を 完
遂し た後に, そ れが土台から 揺る がさ れる 事態に逢着す る
こ と ほど 望ま ら し から ぬこ と はない. こ の巻の印刷が終わ
ろ う と し て いたそ のと き に, バート ラ ン ド ・ ラ ッ セル氏か
ら 送ら れて き た手紙によ っ て 私が立たさ れる こ と になっ た
のが, ま さ にそ う し た状況であっ た.」 (フ レ ーゲ,『 算術の基
本法則』 第 2 巻, あと がき )
48
バート ラ ン ド ・ ラ ッ セル
(Bertrand Russel, 1872-1970)
(画像はウ ィ キ ペディ ア よ り 引用)
49
ラ ッ セルのパラ ド ッ ク ス (集合論バージョ ン )
集合は対象の集ま り ですが, 対象と し て 集合そ のも のを 考え て よ い.
こ のと き , 普通, 集合そ のも のは, そ れ自体の要素にはなっ て いま
せん. つま り , X ∈ X は成立し て いま せん. け れど も , 集合全部の集
合, など を 考え る と , 集合全部の集合は集合ですから , そ れ自身の要素
になっ て いま す.
今, A と し て 自分自身を 含ま ない集合を 全部集めた集合を と り ま す.
つま り , A と いう のは, X ∈
/ X が成立し て いる よ う な X を 集めた集合
です. こ のと き , A ∈ A か考え て みま す. A ∈ A と する と , 集合 A の定
義から , A ∈
/ A と なっ て いる はずで, こ れは矛盾です から , A ∈ A は
成立し て いま せん. 一方, A ∈
/ A と する と , 集合 A の定義から , A は集
合 A に含ま れる はずです. つま り , A ∈ A と なっ て し ま い, やはり 矛盾
なので, A ∈
/ A も 成立し て いま せん. 従っ て , A ∈ A でも A ∈
/ A でも
ないこ と になっ て し ま いま す (? ).
50
パラ ド ッ ク スの回避
自己言及的な構成を 許すこ と が問題
型の理論 (theory of types)
(Bertrand Russel, 1903)
個体を タ イ プ 0 と する .
タ イ プ 0 の個体に対する 述語を タ イ プ 1 と する .
タ イ プ 1 の述語に対する 述語を タ イ プ 2 と する .
...
51
プリ ン キ ピ ア ・ マテマティ カ
(Alfred North Whitehead and Bertrand Russell, 1910,
1912, and 1913)
「 数学で発展さ せら れた全て のア イ デア と 推論ステッ プ
を 論理に基づいて 厳密に再現し よ う . 」
フ レ ーゲのア イ デア と 仕事がこ れで知ら れる よ う になり ,
数学に大き なイ ン パク ト を 与え る こ と になっ た.
52
短縮版の表紙
(画像はウ ィ キ ペディ ア よ り 引用)
53
プリ ン キ ピ ア の証明体系 (命題論理断片)
公理:
(1)
(2)
(3)
(4)
(5)
(P ∨ P ) → P
Q → (P ∨ Q)
(P ∨ Q) → (Q ∨ P )
(P ∨ (Q ∨ R)) → (Q ∨ (P ∨ R))
(Q → R) → ((P ∨ Q) → (P ∨ R))
推論規則:
A→B
B
A
A θ: 命題変数の具体化
Aθ
“公理から 推論規則を 繰り 返し 使っ て 得ら え る も のだけ
が正し い命題”
54
真理値と 真理値表
真理値: 命題は真 (True) か偽 (False) の真理値を 持つ.
真理値表: Wittgenstein, Emil Leon Post
命題論理断片で は, 証明体系に も と づく 証明可能性は,
真理値 (真・ 偽) と 真理値表によ っ て 説明でき る . (命題論理
の完全性)
(Emil Leon Post, 1921)
プリ ン キ ピ ア の命題論理断片の証明シ ステムと
真理値表で真になる こ と が対応する .
55
エミ ール・ レ オ ン ・ ポスト
(Emil Leon Post, 1897-1954)
(画像はウ ィ キ ペディ ア よ り 引用)
56
ヒ ルベルト の計画
フ レ ーゲ∼プリ ン キ ピ ア ・ マテマティ カ への批判: 型の
理論に基づく ため, 従来行われて いたよ う な数学の証明が
し づら い.
1904: 「 論理学と 算術の基礎」 (国際数学者会議での講演)
集合論や自然数論を 形式化し , そ の無矛盾性を 証明すべ
き.
1. プリ ン キ ピ ア の公理から 本当に矛盾が導かれないか?
2. 数学のど んな定理の証明にも 十分な証明体系は?
57
第一階述語論理
『 数理論理学の基礎』 (Hilbert and Ackermann, 1928)
第一階述語論理, 第二階述語論理, ... と いう 形で, 述語論
理を 見通し よ く 整理.
公理:
(1) A → (B → A)
(2) (A → B) → ((A → (B → C)) → (A → C))
(3) A → (B → (A ∧ B))
(4) A ∧ B → A
(4’) A ∧ B → B
(5) A → A ∨ B
(5’) B → A ∨ B
(6) (A → C) → ((B → C) → (A ∨ B → C))
58
(7) (A → B) → ((A → ¬B) → ¬A)
(8) ¬¬A → A
(9) A(t) → ∃xA(x)
(10) ∀xA(x) → A(t)
推論規則:
A→B
B
A
A(a) → C
C → A(a)
∃xA(x) → C C → ∀xA(x)
ただし , a は C に出現し ない.
Hilbert の問題提起
• 証明体系の無矛盾問題. (ど う やっ て 体系から 矛盾が
導かれないと いう こ と が示せる のか? )
• 証明体系の完全性問題. (正し い論理式は必ず証明体
系を つかっ て 示せる のだろ う か? )
59
第一階述語論理の完全性
(Kurt, G¨
odel, 1930)
第一階述語論理の証明体系と 意味論が対応する .
従っ て , 第一階述語論理の証明体系は無矛盾.
60
社会現象
自然現象
理論
数学
論理
61
理論
数学
論理
数学の理論は, 論理を 対象と する こ と も でき る .
62
意味論
数学
論理
数学の理論は, 論理を 対象と する こ と も でき る .
63
意味論
数学
論理
構文論
64
意味論と 証明論
意味論: 数学の概念を 使っ て 論理を 調べる .
「 真な論理式と は, すべて の数学的なモデル上で成り 立
つ論理式のこ と である .」
構文論: 論理の立脚点. 数学の基礎付け.
「 真な論理式と は, 論理的な推論に従っ て 導かれる 論理
式のこ と である .」
意味論と 構文論における 真の概念は等価なのか?
「 意味論と 証明論は論理学の両輪」
65
自然演繹法 (Natural Deduction)
(Gerhard Gentzen, 1935)
プ リ ン キ ピ ア の証明体系や Hilbert&Ackermann の証明
体系 (ヒ ルベルト 流の体系) は, 実際の数学で使われる 証明
のやり 方と はかけはなれて いる .
⇒ 実際の数学の推論に即し た証明体系の発明
66
証明図
自然演繹法では証明図を 作る こ と によ っ て 証明を 行う .
「 すべて の x について P x なら ば Q x である .
P a である .
従っ て , Q a である .」
証明図
[∀x(P (x) → Q(x)]
P (a) → Q(a)
Q(a)
[P (a)]
(いく つかの) 推論規則を 用いて 証明図を 記述.
横棒は 1 つの推論ステッ プを , [ ] は前提である こ と を 示す.
67
ゲルン ハルド ・ ゲェ ン ツ ェ ン
(Gerhard Gentzen, 1909–1945)
(画像はウ ィ キ ペディ ア よ り 引用)
68
目次
-
講義の情報
はじ めに ∼論理と は∼
論理学概観 ∼論理学の歴史を 振り 返り ながら ∼
講義概要
情報論理学 講義概要 (1)
講義の目的 (シ ラ バスよ り )
数理論理学は, 情報科学分野全般における 数学的・ 理
論的な思考技術の基本と し て , 更にま た, ソ フ ト ウェ ア 科学
におけ る 形式的技法の基礎と し て 重要である . こ のよ う な
観点から , 数理論理学の基礎を 修得する こ と を 目的と する .
講義の概要 (シ ラ バスよ り )
数理論理学の基本である 命題論理およ び述語論理につ
いて , 命題の形式化, 命題の解釈法, ト ート ロ ジ ー, 論理
的同値性, 形式的推論法, 意味論, 健全性と 完全性など に
ついて 講義する .
68
情報論理学 講義概要 (2)
達成目標 (シ ラ バスよ り )
・ 自然言語で与え ら れた命題を 論理式を 用いて 形式化す る
能力の習得.
・ 推論の形式化について の理解.
・ 数学的論証の過程を 理解し , 明示する 能力の習得.
・ 基礎的な数学的構造において , 与え ら れたモ デル上にお
ける 命題の真偽を 議論する 能力の習得.
・ 証明可能性と 恒真性の同等性について の理解.
69
情報論理学 講義概要 (3)
• 命題論理の意味論
• 帰納的定義
• 命題論理の構文論 (自然演繹法)
• 第一階述語論理の意味論
• 第一階述語論理の構文論 (自然演繹法)
• 健全性と 完全性 (意味論と 構文論の対応)
最も 応用範囲が広く , 最も 基本的な数理論理学の基礎を 身につける . 構
文論では, 主要な体系と し て , ヒ ルベルト 流の体系/自然演繹法/シ ー
ケ ン ト 計算がある が, こ の講義では自然演繹法に焦点を し ぼる .
70
(補足) 論理学は先端的な研究で応用さ れて いないの?
いく つかの主要な応用を 挙げる :
(1) 対話的証明器
数学の証明を 形式的に記述する ソ フ ト ウ ェ ア. 今ま で人
間の手で書かれて いた証明では大幅に省略さ れる が, こ れ
を 計算機上で厳密に (プロ グ ラ ム のよ う に ) 記述. バグ のな
い証明が可能になる ばかり でなく , 推論シ ス テム の出力検
証やユーザー本位の定理証明への応用など .
(2) SAT/SMT ソ ルバー
計算困難な論理式の充足可能性を 高速に解く ソ フ ト ウ ェ
ア. 高速に 解け る と は限ら ないが, 実は, 人間が解き たい
問題はかなり 高速に解ける こ と が多い. さ ま ざま な問題を71,
論理式等でエン コ ード し て , SAT/SMT ソ ルバーを 用いる
こ と で, 解を 高速に発見する こ と ができ る .
(3) モデルチェッ カ ー
ソ フ ト ウ ェ ア のバグを 見つける のにさ ま ざま な入力を 試
す のではなく , ど のよ う に動作し て 欲し いか (仕様) を 論理
を 用いて 記述し , プロ グ ラ ム の入力や実行を 抽象化す る こ
と でモ デルを 構築し , モ デルが仕様を 満たす かを 検査す る
こ と で, あら ゆる 入力や動作で (そ の仕様について ) 問題が
ないかど う かを 判定する .
情報 + 論理 を 背景と し たア プ ロ ーチ は, Logic in
Computer Science と よ ばれて おり , 情報科学/情報工学
の基本的な分野の重要な柱の 1 つ.
72