數(shù)理邏輯（第2版）

第0章　集合基礎　1
第1章　命題邏輯　8
1.0　閑話形式語言　8
1.1　命題邏輯的語言　9
1.2　真值指派　14
1.2.1　真值表　17
1.2.2　典型的重言式　19
習題　19
1.3　解析算法　21
1.3.1　解析算法　22
1.3.2　波蘭記法　23
1.3.3　省略括號　23
習題　24
1.4　歸納與遞歸　24
1.4.1　歸納　24
1.4.2　遞歸　27
習題　32
1.5　命題聯(lián)結詞　32
1.5.1　0元聯(lián)結詞　37
1.5.2　一元聯(lián)結詞　37
1.5.3　二元聯(lián)結詞　37
1.5.4　三元聯(lián)結詞　37
習題　38
1.6　交換電路　39
習題　42
1.7　緊致性和能行性　43
1.7.1　緊致性　43
1.7.2　能行性及可計算性　44
習題　47
第2章　一階邏輯　49
2.0　預備知識　49
2.1　一階語言　50
2.1.1　公式　53
2.1.2　自由變量　55
2.1.3　符號　56
習題　57
2.2　真值與模型　58
2.2.1　邏輯蘊涵　64
2.2.2　結構中的可定義性　65
2.2.3　結構類的可定義性　67
2.2.4　同態(tài)　68
習題　72
2.3　解析算法　75
2.3.1　項的解析　76
2.3.2　公式的解析　77
習題　78
2.4　演繹計算　78
2.4.1　形式演繹　79
2.4.2　替換　80
2.4.3　重言式　82
2.4.4　演繹與元定理　83
2.4.5　策略　86
2.4.6　字母變換式　90
2.4.7　相等　92
2.4.8　注記　93
習題　93
2.5　可靠性與完備性理論　94
2.6　理論的模型　107
2.6.1　有限模型　107
2.6.2　模型的大小　110
2.6.3　理論　113
2.6.4　前束范式　117
2.6.5　注記　118
習題　119
2.7　理論之間的解釋　119
2.7.1　定義函數(shù)　120
2.7.2　解釋　121
2.7.3　語法翻譯　124
習題　126
2.8　非標準分析　126
2.8.1　*R的構造　127
2.8.2　代數(shù)性質　129
2.8.3　收斂性　131
習題　133
第3章　不可判定性　134
3.0　數(shù)論　134
3.1　有后繼數(shù)的自然數(shù)　138
習題　142
3.2　數(shù)論的其他歸約模型　142
習題　149
3.3　數(shù)論的子理論　149
3.3.1　公理集AE　149
3.3.2　可表示關系　151
3.3.3　丘奇論題　153
3.3.4　按數(shù)字確定的公式　155
3.3.5　可表示函數(shù)　156
3.3.6　編目　161
習題　166
3.4　語法的算術化　167
習題　175
3.5　不完全性和不可判定性　175
3.5.1　遞歸可枚舉性　178
3.5.2　弱可表示性　180
3.5.3　算術分層　181
習題　183
3.6　遞歸函數(shù)　184
3.6.1　范式　185
3.6.2　部分遞歸函數(shù)　187
3.6.3　判定問題的歸約　193
3.6.4　帶寄存的計算器　195
習題　197
3.7　第二不完全性定理　198
3.7.1　集合論的應用　202
3.7.2　集合論中的哥德爾第二不完全性
定理　204
習題　205
3.8　冪乘運算的表示　206
3.8.1　配對函數(shù)　207
3.8.2　哥德爾β函數(shù)　208
習題　209
第4章　二階邏輯　211
4.1　二階語言　211
習題　214
4.2　斯科倫函數(shù)　214
習題　219
4.3　多類邏輯　220
4.4　廣義結構　222
4.4.1　多類語言　223
4.4.2　二階語言的廣義結構　224
4.4.3　解析模型　226
附錄A　推薦讀物　228
附錄B　符號列表　229
索引　231