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
© Copyright 2024 ExpyDoc