情報理論のための数理論理学

書籍情報
シリーズ名数学のかんどころ 【31】巻
ISBN978-4-320-11072-4
判型A5 
ページ数214ページ
発売予定2017年08月28日
本体価格1,900円
情報理論のための数理論理学 書影
情報理論のための数理論理学

新刊

 高等学校や大学の初学年で数理論理学を学習するが,多くの場合,命題論理・述語論理の初等的な学習までに留められてしまい,この分野にどういった応用例があるかを学べる機会は限られている。
ただ,命題論理・述語論理の応用などを学びたい・知りたいと思った場合でも,現状では,数学基礎論寄りの非常に高度な専門書に取り掛かるほかない。
 本書では,そのような「初等的な数理論理学の『その少し先』を学びたい」という意欲ある読者が,高度な専門書に取りかかれるまでの足掛かりとなる基礎知識を提供する。

 命題・述語論理,真理値表の書き方,量化記号(∀,∃)の意味などを学んだあとには,「形式的証明・形式手法」について学ぶ必要がある.本書では,命題論理の形式的証明について,ヒルベルト流の体系を用いて通常の入門書よりやや詳しく解説する。
 また,ブール代数についてもかなり詳しく解説している。「ブール代数を定式化するために,一体いくつの公理が必要か」ということについては,長い研究の歴史がある。特に自動証明による手法は,人工知能による数学問題の証明という面からも興味深い内容となっている。

 これらは,数理論理に興味がある学部生・修士のほか,計算機科学を学ぶ読者にも知っておいてほしい知識であると考えている。

目次

第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 命題時相論理

関連図書/問題解答/索引