情報工学形式論理と計算可能性

東京大学工学教程

書籍

オンデマンド版

大活字版

書籍

雑誌

電子版

読み上げ可能電子版

オーディオブック

編：東京大学工学教程編纂委員会

著：蓮尾　一郎

著：浅田　和之

出版社：丸善出版

同一作品の他版

アクセシブルブック

内容紹介

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

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

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

はじめに

第1章　集合論の基礎
1.1　集合上の基本的な構成
1.2　関数
1.3　二項関係

第I部　形式論理

第2章　等式論理――形式論理のショウケースとして
2.1　最初の例
2.2　項
2.3　構文論
2.4　導出
2.5　意味論
2.6　構文論 vs. 意味論
2.7　形式論理とは？

第3章　命題論理
3.1　論理式
3.2　導出規則
3.3　意味論
3.4　構文論 vs. 意味論

第4章　述語論理
4.1　項と論理式
4.2　導出規則
4.3　意味論
4.4　構文論 vs. 意味論

第5章　命題論理および述語論理の諸性質
5.1　カット除去
5.2　理論とコンパクト性
5.3　構造のクラスの公理化可能性：コンパクト性の帰結として

第II部　計算可能性

第6章　帰納的関数
6.1　原始帰納的関数
6.2　帰納的関数

第7章　帰納的関数とwhileプログラム
7.1　Whileプログラム
7.2　Churchの提唱

第8章　帰納的関数の性質
8.1　普遍帰納的関数
8.2　停止問題の決定不可能性
8.3　再帰定理
8.4　帰納的枚挙可能述語

第9章　Gödelの不完全性定理
9.1　述語論理における理論
9.2　不完全性とは？
9.3　理論の複雑さ
9.4　自然数構造における恒真性の決定不可能性

参考文献
記号一覧
索引

ISBN：9784621310144
出版社：丸善出版
判型：A5
ページ数：208ページ
定価：2400円（本体）
発行年月日：2024年09月
発売日：2024年09月28日
国際分類コード【Thema（シーマ）】１：UB。

※同一作品の他版、アクセシブルブックにはAIにより推定されたものが含まれる場合があります。

ご購入はこちら

情報工学 形式論理と計算可能性

内容紹介

目次

情報工学形式論理と計算可能性