简明数理逻辑
内容简介
《简明数理逻辑》是数理逻辑的入门教材，是作者多年来数理逻辑课程的教学内容和经验总结。本书共有七章。第1章是绪论部分，简要介绍了数理逻辑的发展、形式系统、元语言与元理论以及一些预备知识。第2章介绍初等集合论。第3章、第4章分别详细讲解了命题演算、谓词演算，证明推演定理、可靠性定理，介绍完全性定理及紧致性定理。第5章讲解可计算性理论，主要讲解可判定性、部分可判定性、相对可判定性以及图灵计算的逻辑刻画等。第6章主要讲解哥德尔不完全性定理, 首先介绍皮亚诺算术系统，进而介绍哥德尔编码、元数学的算术化、可表示性等重要概念，这些都是体现数理逻辑思想的重要概念。第7章介绍模型论的初步知识和方法，讲解形式理论的模型论性质。
本书既严谨简洁又深入浅出地讲解了数理逻辑的基本内容和思想，仅需要读者具备高中数学等相关知识，因而适合本科中高年级学生和非数理逻辑专业的硕士研究生学习。希望读者通过本书的学习，能够掌握数理逻辑的基本内容、基本方法和基本思想，同时培养理解问题、分析问题、解决问题的能力，为进一步学习打下必要的基础。
《简明数理逻辑》是中山大学逻辑与认知研究所主持编写的“高等学校逻辑学专业系列教材”之一。中山大学于2007年开办逻辑学本科专业，2021年逻辑学专业入选教育部“双一流专业”计划，是我国目前唯一连续招生的逻辑学本科专业。经过十几年的教学实践和建设，课程体系已经覆盖了逻辑学的各个主要分支领域。这些课程的任课教师是一批具有国际视野、在前沿问题从事研究工作的中青年学者，他们也是这套教材的组要作者。
......(更多)
作者简介
赵希顺，教育部重点研究基地中山大学逻辑与认知研究所教授、博士生导师，《逻辑学研究》副主编，国际杂志Journal on Satisfiability, Boolean Modeling and Computation编委，国际SAT协会 (SAT Association) 指导委员会 (steering committee) 成员 (2008-2012)，国际学术年会SAT2008大会主席；2005年入选教育部“新世纪优秀人才”支持计划，2006年获中山大学文科优秀学者桐山奖；研究方向是数理逻辑及其在计算机科学和人工智能的应用，近年来主要关注逻辑系统的表达能力与计算复杂性研究；曾参与翻译《数学百科全书》，出版著作《选择公理》，主编会议论文集Lecture Notes in Computer Science 第4996卷 (Springer)，The proceedings of the 13th Asian Logic Conference (World Scientific)，主编“社会博弈逻辑”丛书。国家社会科学基金重大项目“社会博弈的逻辑与计算模拟研究”首席专家。
......(更多)
目录
丛书序
前言
第1章 绪论 1
1.1 数理逻辑发展简介 1
1.2 数学定义、证明与定理 5
1.3 证明方法 7
第2章 集合论 10
2.1 集合 10
2.1.1 对象及其名称 10
2.1.2 集合的定义 11
2.1.3 集合的表示 11
2.1.4 罗素悖论 12
2.1.5 公理化方法 13
2.1.6 外延公理和空集公理 13
2.1.7 子集 14
2.1.8 分离公理 14
2.1.9 无序对和单点集 15
2.1.10 交集 16
2.1.11 并集 16
2.1.12 集合的差 18
2.1.13 幂集 19
2.1.14 广义并 20
2.1.15 广义交 20
2.2 关系 21
2.2.1 有序对 21
2.2.2 笛卡儿积 22
2.2.3 二元关系 23
2.2.4 关系的运算 24
2.2.5 像与原像 25
2.2.6 等价关系 26
2.2.7 偏序关系 27
2.2.8 良序关系 29
2.2.9 多元关系 30
2.3 映射 31
2.3.1 映射的定义 31
2.3.2 单射、满射和双射 34
2.3.3 序同态与序同构 36
2.3.4 集族 37
2.3.5 广义笛卡儿积 37
2.3.6 选择公理 38
2.3.7 多元映射 38
2.4 归纳证明与归纳定义 39
2.4.1 自然数的定义 39
2.4.2 数学归纳法 40
2.4.3 归纳定义 43
2.5 有穷集合和无穷集合 47
2.5.1 等势集合 47
2.5.2 康托尔-伯恩斯坦定理 49
2.5.3 有穷集合 51
2.5.4 可数集合 52
2.5.5 无穷集合 53
2.5.6 不可数集合 54
2.6 序数与基数 56
2.6.1 序数 56
2.6.2 超穷归纳法 59
2.6.3 可数序数 61
2.6.4 基数 62
2.6.5 基数算术 64
第3章 命题演算 66
3.1 命题演算的形式语言 66
3.1.1 命题演算的形式符号 66
3.1.2 形成规则 67
3.2 命题演算的语义 68
3.2.1 赋值、真值表、重言式 69
3.2.2 代入 72
3.2.3 语义后承 73
3.2.4 紧致性定理 73
3.2.5 等价与替换 75
3.2.6 联结词的个数 76
3.3 命题演算的公理及推理规则 77
3.4 形式证明及形式定理 78
3.5 形式推演 78
3.6 推演定理 82
3.7 导出规则及辅助推演规则 84
3.8 斜式推演 85
3.9 可靠性定理 90
3.10 范式与完全性定理 91
3.11 联结词完全性 96
第4章 谓词演算 97
4.1 一阶谓词逻辑的形式语言 97
4.1.1 符号系统 97
4.1.2 形成规则 98
4.1.3 自由变元与约束变元 99
4.2 谓词演算的语义 100
4.2.1 一阶语言的结构 100
4.2.2 指派与项的取值 101
4.2.3 满足关系 103
4.2.4 语义后承 107
4.3 谓词演算的公理系统及推理规则 108
4.3.1 谓词演算的形式证明 109
4.3.2 形式推演 109
4.4 谓词演算的可靠性定理 110
4.5 推演定理 112
4.5.1 依赖性与变化性 113
4.5.2 谓词演算的推演定理 115
4.6 谓词演算的推演规则 118
4.7 斜式推演 121
4.8 具有特殊句法结构的公式 123
4.8.1 前束范式 123
4.8.2 公式分层 125
4.8.3 斯科伦范式 126
4.9 完全性定理与紧致性定理 127
第5章 可计算性理论 129
5.1 部分递归 129
5.1.1 原始递归函数 130
5.1.2 部分递归函数 132
5.1.3 递归函数 133
5.1.4 递归关系 135
5.2 图灵可计算函数 137
5.2.1 单带确定图灵机 137
5.2.2 多带图灵机 141
5.3 图灵计算的算术化 145
5.3.1 图灵机的编码 145
5.3.2 计算的算术化 147
5.4 丘奇-图灵论题 150
5.5 通用图灵机 151
5.5.1 通用函数 152
5.5.2 s-m-n定理 153
5.5.3 通用函数的应用 155
5.6 不可判定性 158
5.7 部分可判定性 162
5.7.1 部分可判定谓词 162
5.7.2 递归可枚举集 166
5.7.3 集合间的多一归约 169
5.8 图灵计算的逻辑刻画 172
5.9 递归定理 175
5.10 神谕图灵机 181
5.10.1 神谕图灵机的配置 181
5.10.2 神谕图灵机的编码 183
5.10.3 相对于A的递归集与r.e.集 184
5.10.4 图灵归约与图灵度 185
第6章 哥德尔不完全性定理 188
6.1 皮亚诺算术系统PA 188
6.1.1 皮亚诺算术系统 188
6.1.2 PA的语义 190
6.2 序关系 191
6.3 可表示性 193
6.4 哥德尔编码 196
6.5 元数学的算术化 197
6.6 哥德尔不完全性定理的证明 200
第7章 模型论 207
7.1 结构之间的关系 208
7.1.1 子结构 208
7.1.2 初等子结构 210
7.1.3 同态与同构 210
7.1.4 嵌入与初等嵌入 211
7.1.5 初等等价 212
7.1.6 膨胀与收缩 212
7.1.7 图像与初等图像 213
7.2 完全性定理与紧致性定理的详细证明 213
7.2.1 完全性定理 213
7.2.2 斯科伦化 218
7.2.3 紧致性定理 220
7.2.4 全称型理论的模型论刻画 223
7.3 完全理论与模型完全理论 223
7.4 部分同构 230
7.4.1 部分同构与有穷同构 230
7.4.2 Fra*ssé定理 232
7.5 量词消去 235
7.6 内插定理 238
7.6.1 命题逻辑的内插定理 238
7.6.2 谓词逻辑的内插定理 238
7.6.3 Beth可定义性定理 241
7.7 Ⅱ2-理论的模型论性质 242
7.8 型省略定理 245
7.8.1 相对于结构的型 245
7.8.2 相对于理论的型 248
参考文献 250
索引 251
......(更多)
读书文摘
......(更多)
