形式論理と計算可能性/蓮尾一郎/浅田和之

蓮尾一郎浅田和之
丸善出版
東京大学工学教程 情報工学
ISBN：4621310143/9784621310144
発売日:2024年09月

---

【内容紹介】
本書は、基本的なトピックの中からさらに取捨選択を行い、直観や動機付けを重視しつつ技術的細部を積み上げていく、理論のユーザーとしての視点に徹したコンパクトな教科書である.
読者がいくつかの結果や証明のアイデアを身につけ、自らの専門分野に応用できるよう、理論展開全体のストーリー構成がなされている.

第I部「形式論理」は証明論とモデル理論の初歩に相当し、命題論理や述語論理を扱う.
本書の特徴に、「論理体系のショウケース」として最初に等式論理を用いた点が挙げられる.
ここでの議論や証明の本質的な部分が、より複雑な命題論理、述語論理において用いられる.

第II部「計算可能性」の第8章までが再帰理論の入門に相当する.
帰納的関数とwhileプログラムを計算モデルとして計算可能性の理論を導入する.
最後に、数学基礎論の全分野と結びつく重要な結果であるGodelの不完全性定理の簡単なバリエーションの証明の概略を与える.