扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
全国计算机等级考试最新真考题库模拟考场及详解·二级MSOffice高级应用
-
>
决战行测5000题(言语理解与表达)
-
>
软件性能测试.分析与调优实践之路
-
>
第一行代码Android
-
>
C Primer Plus 第6版 中文版
-
>
深度学习
-
>
MATLAB计算机视觉与深度学习实战-赠在线交流卡和本书源码
数理逻辑引论——计算机科学与系统的天然基础 版权信息
- ISBN：9787030732385
- 条形码：9787030732385 ; 978-7-03-073238-5
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>
数理逻辑引论——计算机科学与系统的天然基础 本书特色
本书需要读者具备一定的高等数学和程序设计的基础知识，适合作为大学与计算机专业相关的本科生和研究生的参考书，也可供相关专业科研技术人员阅读参考。
数理逻辑引论——计算机科学与系统的天然基础 内容简介
本书的内容包括8章，讨论了命题演算和一阶谓词演算的希尔伯特公理系统，包括命题演算和谓词演算系统中逻辑语言的语法定义，形式推演证明系统的建立，逻辑语言的语义定义，以及两个形式系统的元理论，主要是有效性和接近性的定义和证明。以此揭示任何形式系统的组成部分、构建方法、需要研究处理的主要问题、方法和技术。还介绍了如何基于形式逻辑建立各种形式化数学系统，帮助读者理解数理逻辑和数学系统的关系。*后介绍了图灵机的定义，并且讨论了如何图灵机的状态转移函数和符号化逻辑推理（转换）规则之间的联系。进一步展示了如何将形式逻辑中形式语言的定义和研究方法自然迁移到程序语言的定义，如何采用定义和研究一阶逻辑语言语义的方法与技术研究程序语言的形式语义，包括操作语义、指称语义、公理语义和代数语义（规约）。
数理逻辑引论——计算机科学与系统的天然基础 目录
目录
前言
第1章导论1
1.1逻辑的基本概念和术语1
1.2逻辑学3
1.2.1概念与命题3
1.2.2推理论证5
1.2.3自然语言的歧义性与悖论7
1.3从亚里士多德经典逻辑到现代数理逻辑的演化8
1.3.1形式逻辑—推理形式与内容的分离9
1.3.2数理逻辑14
1.4计算机科学中的逻辑19
1.4.1逻辑是计算理论的天然基础19
1.4.2计算机科学技术领域的形式语言20
1.4.3形式证明与验证26
第2章离散数学基础29
2.1集合与集合代数30
2.1.1集合：概念、表示法和意义30
2.1.2子集34
2.1.3集合代数37
2.2关系和关系代数49
2.2.1笛卡儿积49
2.2.2关系52
2.2.3等价关系和划分55
2.2.4关系代数58
2.2.5关系的图示61
2.3函数64
2.4集合、关系、函数和谓词的联系与统一66
2.4.1关系和函数的统一67
2.4.2集合、关系、函数、谓词和布尔代数的统一67
2.5数学归纳法68
2.6集合上的序关系69
2.6.1偏序集70
2.6.2从已知的偏序集构造偏序集72
2.6.3偏序集间的函数74
2.7格、完全格和完全偏序集75
2.7.1偏序集的特殊子集和元素75
2.7.2格和完全格77
2.7.3保持上下确界的函数81
2.7.4塔斯基不动点理论82
2.7.5完全偏序集及不动点理论83
2.8集合的基数87
第3章朴素命题逻辑91
3.1引言91
3.2断言和连接词92
3.3连接词的真值函数和真值表95
3.4断言形式97
3.4.1断言形式的真值函数和真值表98
3.4.2断言形式的语法树101
3.5重言式和矛盾式102
3.6逻辑等价和逻辑蕴涵104
3.6.1逻辑等价104
3.6.2等价替换106
3.6.3逻辑蕴涵的性质111
3.7对偶式和断言范式114
3.7.1对偶式114
3.7.2断言形式的范式116
3.7.3充分连接词集合118
3.7.4子句形式119
3.8推理及推理的有效性120
第4章形式化命题逻辑122
4.1形式逻辑系统123
4.2形式命题逻辑系统L125
4.3L中的演绎推理130
4.3.1演绎定理131
4.3.2关于否定命题的证明与推演134
4.4形式系统L的有效性137
4.5相容性和L的充分性定理138
第5章朴素谓词逻辑147
5.1谓词和量词148
5.1.1谓词149
5.1.2变量、量词和函数149
5.2一阶形式语言154
5.2.1字母表155
5.2.2一阶语言的实例156
5.2.3合式公式157
5.2.4形式语言的语法层次结构158
5.2.5变元的自由与约束出现159
5.2.6换名和代换161
5.3解释165
5.3.1概念166
5.3.2赋值167
5.3.3合式公式可满足性168
5.3.4真值和模型171
5.4重言式和逻辑等价175
5.4.1重言式175
5.4.2逻辑有效的公式177
5.4.3逻辑蕴涵和逻辑等价178
5.5斯科伦定理181
第6章形式化谓词逻辑184
6.1形式系统KL184
6.1.1KL的有效性186
6.1.2KL的演绎定理188
6.2可证明等价和代换192
6.3KL的充分性定理199
6.3.1KL的扩展199
6.3.2充分性定理的证明201
6.4模型206
6.5范式209
6.5.1量词辖域的变换209
6.5.2前束范式211
6.5.3子句形式213
第7章数学系统215
7.1带等词的一阶系统216
7.2公理化群论221
7.2.1群的非形式定义221
7.2.2形式化群论222
7.3公理化布尔代数225
7.4形式化算术226
7.4.1算术的形式化226
7.4.2与皮亚诺算术的关系228
7.4.3形式化算术的模型及完备性问题229
7.5公理集合论230
7.5.1ZF公理系统230
7.5.2ZF公理系统的模型232
7.6相容性和模型之间的关系234
第8章程序设计理论导引236
8.1计算、计算机和计算机程序236
8.1.1可计算性和计算机236
8.1.2程序语法的非形式定义240
8.1.3程序的非形式语义242
8.2程序语言的形式语法244
8.3程序语言的操作语义246
8.3.1栈-状态-控制抽象机解释语义247
8.3.2基于操作语义的程序分析和验证249
8.3.3结构化操作语义251
8.3.4完整的结构化操作语义255
8.4程序语言的指称语义258
8.4.1基本思想和技术258
8.4.2核心问题260
8.4.3Mini的指称语义定义261
8.5指称语义和操作语义的一致性265
8.6程序语言的公理语义268
8.6.1非形式霍尔逻辑269
8.6.2霍尔逻辑271
8.6.3霍尔逻辑可靠性和完全性276
8.7抽象数据类型281
参考文献284
索引285
前言
第1章导论1
1.1逻辑的基本概念和术语1
1.2逻辑学3
1.2.1概念与命题3
1.2.2推理论证5
1.2.3自然语言的歧义性与悖论7
1.3从亚里士多德经典逻辑到现代数理逻辑的演化8
1.3.1形式逻辑—推理形式与内容的分离9
1.3.2数理逻辑14
1.4计算机科学中的逻辑19
1.4.1逻辑是计算理论的天然基础19
1.4.2计算机科学技术领域的形式语言20
1.4.3形式证明与验证26
第2章离散数学基础29
2.1集合与集合代数30
2.1.1集合：概念、表示法和意义30
2.1.2子集34
2.1.3集合代数37
2.2关系和关系代数49
2.2.1笛卡儿积49
2.2.2关系52
2.2.3等价关系和划分55
2.2.4关系代数58
2.2.5关系的图示61
2.3函数64
2.4集合、关系、函数和谓词的联系与统一66
2.4.1关系和函数的统一67
2.4.2集合、关系、函数、谓词和布尔代数的统一67
2.5数学归纳法68
2.6集合上的序关系69
2.6.1偏序集70
2.6.2从已知的偏序集构造偏序集72
2.6.3偏序集间的函数74
2.7格、完全格和完全偏序集75
2.7.1偏序集的特殊子集和元素75
2.7.2格和完全格77
2.7.3保持上下确界的函数81
2.7.4塔斯基不动点理论82
2.7.5完全偏序集及不动点理论83
2.8集合的基数87
第3章朴素命题逻辑91
3.1引言91
3.2断言和连接词92
3.3连接词的真值函数和真值表95
3.4断言形式97
3.4.1断言形式的真值函数和真值表98
3.4.2断言形式的语法树101
3.5重言式和矛盾式102
3.6逻辑等价和逻辑蕴涵104
3.6.1逻辑等价104
3.6.2等价替换106
3.6.3逻辑蕴涵的性质111
3.7对偶式和断言范式114
3.7.1对偶式114
3.7.2断言形式的范式116
3.7.3充分连接词集合118
3.7.4子句形式119
3.8推理及推理的有效性120
第4章形式化命题逻辑122
4.1形式逻辑系统123
4.2形式命题逻辑系统L125
4.3L中的演绎推理130
4.3.1演绎定理131
4.3.2关于否定命题的证明与推演134
4.4形式系统L的有效性137
4.5相容性和L的充分性定理138
第5章朴素谓词逻辑147
5.1谓词和量词148
5.1.1谓词149
5.1.2变量、量词和函数149
5.2一阶形式语言154
5.2.1字母表155
5.2.2一阶语言的实例156
5.2.3合式公式157
5.2.4形式语言的语法层次结构158
5.2.5变元的自由与约束出现159
5.2.6换名和代换161
5.3解释165
5.3.1概念166
5.3.2赋值167
5.3.3合式公式可满足性168
5.3.4真值和模型171
5.4重言式和逻辑等价175
5.4.1重言式175
5.4.2逻辑有效的公式177
5.4.3逻辑蕴涵和逻辑等价178
5.5斯科伦定理181
第6章形式化谓词逻辑184
6.1形式系统KL184
6.1.1KL的有效性186
6.1.2KL的演绎定理188
6.2可证明等价和代换192
6.3KL的充分性定理199
6.3.1KL的扩展199
6.3.2充分性定理的证明201
6.4模型206
6.5范式209
6.5.1量词辖域的变换209
6.5.2前束范式211
6.5.3子句形式213
第7章数学系统215
7.1带等词的一阶系统216
7.2公理化群论221
7.2.1群的非形式定义221
7.2.2形式化群论222
7.3公理化布尔代数225
7.4形式化算术226
7.4.1算术的形式化226
7.4.2与皮亚诺算术的关系228
7.4.3形式化算术的模型及完备性问题229
7.5公理集合论230
7.5.1ZF公理系统230
7.5.2ZF公理系统的模型232
7.6相容性和模型之间的关系234
第8章程序设计理论导引236
8.1计算、计算机和计算机程序236
8.1.1可计算性和计算机236
8.1.2程序语法的非形式定义240
8.1.3程序的非形式语义242
8.2程序语言的形式语法244
8.3程序语言的操作语义246
8.3.1栈-状态-控制抽象机解释语义247
8.3.2基于操作语义的程序分析和验证249
8.3.3结构化操作语义251
8.3.4完整的结构化操作语义255
8.4程序语言的指称语义258
8.4.1基本思想和技术258
8.4.2核心问题260
8.4.3Mini的指称语义定义261
8.5指称语义和操作语义的一致性265
8.6程序语言的公理语义268
8.6.1非形式霍尔逻辑269
8.6.2霍尔逻辑271
8.6.3霍尔逻辑可靠性和完全性276
8.7抽象数据类型281
参考文献284
索引285
展开全部
数理逻辑引论——计算机科学与系统的天然基础 节选
第1章导论 学习一门学问，研究一个领域或一个方向，首先应该溯其本源，明确其基本概念，了解其研究和解决的基本问题，并追踪其发展历程。这有助于学习者明确相关研修的目标，建立研修兴趣，为进一步的深入研究奠定坚实基础。鉴此，本章将介绍逻辑(logic)的基本概念，讨论其研究和解决的基本问题，并简述数理逻辑的发展史。我们也会论及数理逻辑研究中对人类思维及推理规律的思考及其所产生的指导作用，尤其要特别讨论数理逻辑与数学的关系，以及数理逻辑在各个科学与工程领域中所扮演的重要的基础性角色。*后，我们将基于计算理论及计算机科学与技术的视角，阐述数理逻辑在这一特定领域的地位与作用。 本章第1.1节和第1.2节首先介绍数理逻辑的起源、研究的基本问题，相关概念和术语等；第1.3节介绍从亚里士多德逻辑到近代数理逻辑的发展和演化，以及逻辑与数学的关系。*后，第1.4节讨论数理逻辑在计算机科学中的核心基础性地位，以及它对计算科学，尤其是程序语言设计和程序分析验证等领域发展的影响，并展望其对未来一些方向发展的重要性。对这一章的学习可以根据自己的背景选择性地进行：第1.1节和第1.2节对专业知识的假设很少，更适合一般性的读者；第1.3.2节需要一些数学常识，可以结合本书的第2章和第7章学习；第1.4节需要一些计算机科学的概念和知识，该节后面部分关于程序语言语义和程序的形式化验证的讨论需要一些形式化方法的基础知识，计算机专业的读者可以结合自己专业进行研读。本书第8章有对程序语言的语法和语义的介绍，读者可以在研读第8章后再回来读第1.4节。总之，这一章的内容可以在学习本书的过程中反复研读和思考。 1.1逻辑的基本概念和术语 我们在日常生活的言谈中经常用到“逻辑”一词，譬如说“你这是什么逻辑？”，“这不合乎逻辑”，“某某的逻辑性很强”等。但是，如果讲授逻辑课的教授在**节开始时想了解一下学生对逻辑的认识，并请学生们谈谈他们对“什么是逻辑”“逻辑的用途和意义”“逻辑研究什么”等问题的看法。一般情况下，学生们需要经过一定的努力和引导方能归结并提及如下的某些关键术语：断言(assertion)、命题(proposition)、真(true)、假(false)、推理(reasoning)和论证(argument)、证明(proof)、定理(theorem)、矛盾(contradiction)、悖论(paradox)、一致性(consistency)等。再多进行一些尝试和努力，可能会进而提到可靠性(soundness)、合理性(validity)、完备性(completeness)和严密、验证等更高深些的术语。这一情况说明，一般人都有一些与逻辑相关的基本常识。但也非常遗憾，多数计算机专业本科毕业生缺乏对逻辑的系统认知，不清楚上述术语的确切含义及相互间的关系。阅读完这本书以后要达到的一个基本的目标是能够清晰和系统地理解这些术语的定义、内涵和外延，及这些概念之间的相互关系。 为了系统地认识逻辑及其相关问题，我们先考虑一类*简单的逻辑，称为二值逻辑(two-valued logic)。在二值逻辑中，一个命题就是一个或者为真或者为假的陈述句。也就是说，一个命题只有两种可能的“值”，如果它“事实上”成立则其值为真（或简单说它为真），不成立则它为假。下面我们通过一些例句来帮助读者理解命题的二值特征。 例1.1我们不难判断下面几个例句的真假： [例句1]所有人都喜欢吃巧克力。 [例句2]有些人不喜欢吃巧克力。 [例句3]这块黑板是黑色的。 例1.2但我们无法判断如下陈述句是真或假： [例句4]刘备跑得快。 [例句5]这句话是谎言。 例1.2中例句5就是著名的“说谎者的悖论(The Liar’s Paradox)”：如果这句话（“这句话是谎言”）为真，则“这句话”就为假；而如果“这句话”为真，则“这句话是谎言”就应该为假。研究如何避免悖论正是逻辑学兴起的一个重要原因。 逻辑一词本身也是一个多义词，它有时指一个具体的逻辑系统，即由一套逻辑语言、公理和推理规则构成的具体的逻辑。有时却指一种逻辑类别，如：根据不同的推理方式，逻辑可以分为演绎逻辑(deductive logic)和归纳逻辑(inductive logic)；按照不同的哲学理念，又可以分为经典逻辑(classical logic)和直觉主义逻辑(intuitionistic logic)；从表达静态与动态关系的方面考虑，静态的命题逻辑(propositional logic)和谓词逻辑(predicate logic)又可以扩展到相应的模态逻辑(modal logic)；另外还有一阶逻辑(first-order logic)和高阶逻辑(higher-order logic)之分。看到这么多分门别类的逻辑和术语，可能使人对研修数理逻辑有些望而生畏。本章和本书后面的章节将梳理和讨论各种不同逻辑的共同的和基础的性质。 每个具体逻辑系统(logic system)都有一个表达断言或命题的逻辑语言(logic language)，通过一组严格的语法规则(syntactic rule)定义，还有一套规定如何做推理及判断命题真假的公理(axiom)和推理规则(inference rule)。在这样的逻辑（系统）里可以： (1)严格地表述断言或者命题； (2)判断并确定命题的真值(truth value)，或说其为真还是为假； (3)进行推理论证，以确定断言的真假和推理本身的合理性； (4)从一组断言演绎出（或说推导出）另一些断言，或者确定一些断言是否为以另一些断言为假设的正确结论，或者确定推演过程的正确性。 在一个逻辑系统中，上述(1)(4)都必须能按严格的规则，通过一些机械步骤完成，而不能是通过试错或依靠直觉来完成。这种过程必须是可重复的，其正确性可以根据规则机械地检验。本节**段中提到的术语，基本都是与所有逻辑系统相关的基本概念。在理想情况下，一个逻辑系统应该具有如下的基本性质： (L1)有严格的语法，保证断言满足语法正确性，能严格、机械地检查； (L2)有严格的公理、推理规则及推理过程的定义，保证推理过程的构造的正确性，能严格、机械地检查； (L3)公理和推理规则都是有效的，也称可靠性(sound)，是指由公理和推理规则证明的定理都是真的，在正确的前提下，推理的结果也是正确的。 (L4)推理系统是一致的，是指使用推理系统的公理和推理规则不会推导出相互矛盾的结论。一致性也称为协调性和相容性。注意，有效性保证一致性，但反之不成立。 (L5)公理、推理规则的推理能力足够强大，也称推理系统有充分的推理能力，能推导出所有为真的命题。这一保证称为该逻辑系统的充分性/完全性(adequacy)。 这里“机械”的意思可以理解为存在自动完成该项工作的计算机算法或程序。 本书将讨论一些常见的、有广泛应用的逻辑系统的构建，帮助读者学习并练习在这些逻辑中进行推理和论证，掌握主要的逻辑论证方法，学习如何定义和证明一个逻辑的可靠性和完备性，从中理解逻辑论证、逻辑系统的可靠性、充分性和相容性的重要意义。 1.2逻辑学 根据牛津字典的解释，逻辑(logic)一词源于希腊语 logikē，意指推理的艺术(art of reasoning)。作为一门学问，逻辑学*初属于哲学的范畴，数学也如此。即便今天，数学学士和硕士在牛津大学、剑桥大学等一些西方大学仍属于人文学科（Arts）的学位。逻辑学的内涵是研究思维的规律。人们认为，思维的三种基本形式是：概念、命题和推理。命题也称为断言，推理也称为论证或证明。 1.2.1概念与命题 概念是对一个事物、现象或想法的抽象表述和定义。一个概念具有两个基本特征，即概念的内涵(intention)和外延(extension)。内涵是对概念所指称的对象（类别）的意义、目的和本质的抽象描述；外延则指满足概念定义的所有对象或实例。概念具有结构性和层次性，一个概念可以由其他概念定义，或由其他概念的外延中的对象定义，一个概念也可能是另一个概念外延中的个体对象。逻辑中的命题就是刻画分析概念之间这种结构性和层次性关系，逻辑中的推理证明就是分析和判断这些命题的真或假的过程。 定义1.1(命题)一个简单命题是对某概念的某种属性或几个概念的相互关系的一个陈述，或是描述概念外延中的对象性质或几个概念的外延中对象之间关系的一个语句，表述对象是否具有某种性质。根据概念的定义和对象的属性可以判定一个命题的真值，即该命题的成立与否。命题是一个有主语和谓语的句子，主语亦称为主项(subject term)，谓语也称为谓项(predicate term)。 例1.3例如，如果“大学生”这个概念的内涵是指在大学中为获取学位而学习的人，且学生的属性包括“性别”“年龄”“所修课程”等，则如下的各个陈述都是命题： [例句6]张三是大学生。 [例句7]李四不是大学生。 [例句8]所有大学生都修了 Java 程序课。 [例句9]所有大学生都没有修逻辑课。 [例句10]有些大学生是18岁以上。 [例句11]有些大学生不是18岁以上。 上面例子显示了一个命题可涉及多个概念，而且一个概念也可由其他概念所定义。命题可以是特称命题(particular proposition)，如上面的例句6和7；也可以是全称命题，如上面的例句8和9。上面的例句10和11也称为存在命题。存在命题也属于特称命题，因为它们陈述的事实是针对某个（某些）未予明示的特定对象，而不是全部对象。根据命题中谓词的情况又可以将其分类为肯定命题和否定命题，这样就可以分出四种简单命题：全称肯定命题、全称否定命题、特称肯定命题和特称否定命题。除了简单命题，我们还可以表达更复杂的命题，称为复合命题(composite proposition)。 例1.4下面是几个复合命题： [例句12]张三是大学生，而且张三 Java 程序课的成绩是95分。 [例句13]李四是大学生，而且李四 Java 程序课的成绩不到85分。 复合命题是由简单命题通过连接词(connective)组合而成。进一步说，上面的“大学生”概念可以通过（已知的）概念“人”来定义的，即“大学生”是“人”的一个子概念。概念 A 的一个子概念 B 定义了一个对象集合，其中的对象也是其（超）概念 A 的实例。故如下命题是真。 [例句14]如果张三是大学生，则张三是人。 这个命题是用连接词“如果则 ”将简单命题“张三是学生”与“张三是人”连接而构成的复合命题。在面向对象的软件技术中，概念用类(class)表示。这样，子概念就是子类(subclass)，超概念就是超类(superclass)。一个类定义一个对象集合，一个子类的任何对象也是其超类的对象。 本章接下来的部分不再进一步讨论连接词和复合命题。 1.2.2推理论证 推理是论述一个命题的“合理性”或说“正确性”的过程，通常表示为一个有穷的命题序列。序列的*后一个命题称为该推理的结论(conclusion)，其余命题为其前提(premise)。我们希望推理中出现的每个命题都有清晰的证据说明其“言之有理”，如果确实如此，就说这一推理是有效的。 例1.5下面是一些表示推理的命题序列，其中前提之间用逗号分隔，分号之后是结论： [推理1]张三是大学生；所以，张三是人。 [推理2]所有的人都会死，苏格拉底是人；所以，苏格拉底会死。 [推理3]所有大学生都是人，张三是大学生；所以，张三是人。 [推理4]有
书友推荐
- >
经典常谈
经典常谈
¥22.7¥39.8 - >
我从未如此眷恋人间
我从未如此眷恋人间
¥16.4¥49.8 - >
朝闻道
朝闻道
¥10.2¥23.8 - >
名家带你读鲁迅:故事新编
名家带你读鲁迅:故事新编
¥13.0¥26.0 - >
月亮与六便士
月亮与六便士
¥13.4¥42.0 - >
二体千字文
二体千字文
¥16.0¥40.0 - >
企鹅口袋书系列·伟大的思想20:论自然选择(英汉双语)
企鹅口袋书系列·伟大的思想20:论自然选择(英汉双语)
¥6.9¥14.0 - >
诗经-先民的歌唱
诗经-先民的歌唱
¥15.1¥39.8
本类畅销
-
数学之美
¥48.3¥69 -
浪潮之巅-下册-第二版
¥22.1¥45 -
挑战程序设计竞赛(第2版)
¥55.3¥79 -
算法竞赛入门经典-(第2版)
¥34.9¥49.8 -
2022图书×抽奖盲袋
¥9.9¥25 -
2023读书月阅读盲盒——天黑，闭眼，刀谁？
¥42.3¥158
