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

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