情報理論のための数理論理学 （数学のかんどころ 31）
高等学校や大学の初学年で数理論理学を学習するが、
多くの場合、命題論理・述語論理の初等的な学習までに留められてしまい、
この分野にどういった応用例があるかを学べる機会は限られている。
ただ、命題論理・述語論理の応用などを学びたい・知りたいと思った場合でも、
現状では、数学基礎論寄りの非常に高度な専門書に取り掛かるほかない。
本書では、そのような「初等的な数理論理学の『その少し先』を学びたい」という意欲ある読者が、高度な専門書に取りかかれるまでの足掛かりとなる基礎知識を提供する。
↑ちょうど良さそうだmiyamonz.icon
目次
§ 表紙
§ はじめに
§ 目次
§ 第1章 命題論理
§ 1.1 標準形
§ 1.1.1 基本性質
§ 1.1.2 基本性質の一般化
§ 1.1.3 論理和標準形，論理積標準形
§ 1.2 論理関数と論理回路
§ 1.2.1 重要な論理関数
§ 1.2.2 論理関数の簡単化
§ 1.3 コンパクト性定理
§ 1.4 健全性，完全性，決定可能性
§ 第2章 述語論理
§ 2.1 冠頭標準形，スコーレム標準形
§ 2.1.1 論理式の解釈，モデル
§ 2.1.2 ド・モルガンの法則，およびその他の論理的同値な論理式
§ 2.1.3 冠頭標準形
§ 2.1.4 スコーレム標準形
§ 2.2 ∀∃と∃∀の違い：連続性と一様連続性
§ 2.3 述語論理の完全性
§ 第3章 計算可能性とチューリング機械
§ 3.1 チューリング機械の定義
§ 3.1.1 万能チューリング機械
§ 3.1.2 チューリング機械は可算個しかない
§ 3.1.3 チューリング機械の停止問題
§ 3.1.4 チャーチ・チューリングの提言
§ 3.1.5 チューリング・テスト
§ 3.2 晩年のチューリングの業績
§ 3.2.1 発生生物学
§ 3.2.2 リーマン予想
§ 第4章 命題論理の充足可能性問題
§ 4.1 SAT問題のNP完全性
§ 4.2 DPLLアルゴリズム
§ 4.3 Wangのアルゴリズム
§ 第5章 述語論理の決定不能性
§ 5.1 述語論理式の証明可能性判定問題
§ 5.1.1 チャーチの定理
§ 5.1.2 チューリングの定理
§ 5.2 エルブランの定理
§ 5.2.1 エルブラン充足可能性の判定について
§ 第6章 ブール代数
§ 6.1 ハンティントンの公理系
§ 6.2 基本性質
§ 6.3 いろいろな演算，半順序
§ 6.4 ストーン表現定理
§ 6.5 部分ブール代数，ブール代数の直積
§ 6.6 ブール束，ブール環
§ 6.6.1 ブール束
§ 6.6.2 ブール環
§ 6.7 可算ブール代数
§ 6.8 ロビン（Robbins）の予想
§ 6.8.1 ハンティントン代数はブール代数である
§ 第7章 形式手法と数理論理学
§ 7.1 形式手法とは
§ 7.1.1 移行システム，オートマトン
§ 7.1.2 自動定理証明とブール代数
§ 7.2 様相論理，時相論理
§ 7.2.1 命題様相論理
§ 7.2.2 クリプキ意味論
§ 7.2.3 様相に関係する2つの推論
§ 7.2.4 恒真ではない論理式
§ 7.2.5 基本性質
§ 7.2.6 命題時相論理
§ 問題解答
§ 関連図書
§ 索引
§ 奥付