出版社内容情報
論理と計算の概念は、いまでは計算機科学の基盤となっている。本書は、命題論理や述語論理、そして様相論理など形式論理の基礎を学んだあと、ゲーデル不完全性定理を通して「計算」の意味を理解する。さらに計算モデルの典型であるラムダ計算について学習し、論理と計算の関係だけでなく、両者をつなぐ「仕組み」を理解する。
【目次】
はしがき
学習の手引
１ 集合と関係
1.1 集 合
(a)集 合
(b)空集合
(c)部分集合
(d)結びと交わり
(e)直積と直和
(f)関数空間とベキ集合
(g)集合族
(h)? と ∑
1.2 関 係
(a)二項関係
(b)合成と閉包
(c)順 序
(d)束
(e)同値関係
２ 命題論理と述語論理
2.1 命題論理
(a)命 題
(b)論理記号
(c)構文論
(d)意味論
(e)コンパクト性
(f)ヒルベルト流
(g)シーケント計算
(h)導出原理
2.2 一階述語論理
(a)構文論
(b)意味論
(c)エルブランの定理
(d)ヒルベルト流
(e)シーケント計算
(f)導出原理
(g)等号付き一階述語論理
2.3 高階述語論理とその部分体系
(a)二階述語論理
(b)後継者のみの単項二階論理
(c)高階述語論理
３ 様相論理と直観主義論理
3.1 命題様相論理
(a)構文論
(b)意味論
(c)シーケント計算
(d)有限モデル性
(e)さまざまな様相論理
3.2 多重様相論理
(a)構文論
(b)意味論
(c)多重様相論理の例
(d)反射推移閉包
3.3 時相論理
(a)分岐時間時相論理
(b)線形時間時相論理
(c)線形時間vs.分岐時間
(d)様相μ計算
(e)モデル検査
3.4 命題直観主義論理
(a)構文論
(b)意味論
(c)直観主義論理の真偽値
(d)シーケント計算
４ 計算可能性
4.1 チューリング機械
(a)チューリング機械
(b)計算可能関数
4.2 帰納的関数
(a)原始帰納的関数
(b)部分帰納的関数
(c)停止問題
(d)帰納的集合
(e)算術的階層
4.3 不完全性定理
(a)算 術
(b)表現可能性
(c)符号化
(d)ゲーデルの不完全性定理
(e)第二不完全性定理
4.4 プレスバーガ算術
(a)構文論と意味論
(b)限定子除去
4.5 述語論理の決定不能性と決定可能な部分体系
(a)一階述語論理の決定不能性
(b)単項一階述語論理
(c)等号付き単項一階述語論理
(d)一階述語論理
内容説明
論理と計算の概念は、いまでは計算機科学の基盤となっている。本書は、命題論理や述語論理、そして様相論理など形式論理の基礎を学んだあと、ゲーデル不完全性定理を通して「計算」の意味を理解する。さらに計算モデルの典型であるラムダ計算について学習し、論理と計算の関係だけでなく、両者をつなぐ「しくみ」を理解する。
目次
１ 集合と関係（集合；関係）
２ 命題論理と述語論理（命題論理；一階述語論理；高階述語論理とその部分体系）
３ 様相論理と直観主義論理（命題様相論理；多重様相論理；時相論理；命題直観主義論理）
４ 計算可能性（チューリング機械；帰納的関数；不完全性定理；プレスバーガ算術；述語論理の決定不能性と決定可能な部分体系）
５ ＆＃９５５
計算（＆＃９５５；項；簡約；型付き＆＃９５５；計算）
章末問題解答
著者等紹介
萩谷昌己［ハギヤマサミ］
１９５７年生まれ。１９８０年東京大学理学部情報科学科卒。東京大学大学院情報理工学系研究科教授を経て、東京大学名誉教授。理学博士。専門は、計算機科学
西崎真也［ニシザキシンヤ］
１９６７年生まれ。１９９４年京都大学大学院理学研究科博士課程了。現在、東京科学大学情報基盤センター教授。博士（理学）。専門は、計算機科学（本データはこの書籍が刊行された当時に掲載されていたものです）
※書籍に掲載されている著者及び編者、訳者、監修者、イラストレーターなどの紹介情報です。
