离散数学

章节摘录

插图：逻辑学是研究推理的科学，具有十分悠久的历史，在两千多年前的古希腊时代就已很发达。数理逻辑是数学化的逻辑学，是用数学方法研究推理的科学，其历史只有三百多年。德国数学家、哲学家莱布尼茨（Leibniz）于17世纪中叶明确地提出了建立通用的符号语言和通用代数的思想[1]。他指出，如果我们能对人类的全部思想进行综合分析，并把它们化归成最简单的概念，那么，只要再进一步设计出适当的符号来表示这些基本概念及其组合关系，就可以获得一种既简单又严密的符号语言。由于这种语言克服了自然语言的弊病及局限性（如不规则性、歧义性等），因此，它是一种理想的、世界性的公共语言，即所谓的“通用语言”。其次，通用语言的建立不仅有益于思想的交流，而且也有益于思维。由于在通用语言中实现了彻底的符号化，其中的推理过程就表现为符号序列的变形，从而只要对此做出明确的规定，就可以按照这些规定机械地实行推理，正如人们在代数运算中按照明确的法则对代数式进行演算一样。我们最终所获得的就不仅是一种“通用语言”，而且也是一种“通用代数”。在这种符号语言中，思维被“演算化”了。莱布尼茨只是进行了一些初步的尝试，并没有能够实现他的关于通用符号语言和通用代数的设想，但是数理逻辑却是沿着他的设想发展起来的。因此，人们公认莱布尼茨为数理逻辑的创始人。布尔（Boole）构造了一个抽象的代数系统，并且给予它多种解释，如类的演算、命题演算、概率演算。当然，布尔所提出的演算很不成熟，某些演算公式没有逻辑解释。但是，布尔的贡献在于，他在逻辑史上首先提出了一个逻辑演算，实现了莱布尼茨的一部分设想。经过许多数学家的改进，今天的布尔代数已发展成为具有广泛应用的丰富的代数理论。

前言

近年来，计算机科学与信息技术正在以惊人的速度迅猛发展，并且对人类社会的各个领域产生着日益广泛和深远的影响。离散数学，作为计算机科学与技术的重要理论基础之一，也因此更加显示出它的重要性。离散数学在计算机科学与技术中的地位如同微积分在物理学和工程技术中的地位一样，离散数学为计算机科学与技术的发展奠定了重要的数学基础。不仅离散数学的基本思想、概念和方法广泛地渗透到计算机科学与技术的各个领域，而且其基本理论和研究成果更是全面而系统地影响和推动着这些领域的发展。例如，布尔代数为开关电路的研究提供了重要的分析工具，并且导致了数字逻辑理论的建立；自动机理论对形式语言及其编译产生了重大的影响，并形成了完整而严密的理论体系；谓词演算成为程序理论的一种重要研究工具；代数结构为编码理论的研究提供了新的途径；图灵机模型和递归函数理论构成了可计算性理论研究的基础。离散数学的这些重要成果和作用，使得它成为一个计算机科学工作者和工程师所必须具备的基本理论知识。对于计算机专业的学生来说，离散数学不仅是很多后续专业课程所必需的先修课，而且也为高等院校工科本科生提供了必要的抽象思维和严密推理的基本训练。

书籍目录

第一篇 数理逻辑第一章 命题逻辑§1．1 命题和联结词§1．2 公式和真值赋值§1．3 等值演算§1．4 对偶定理§1．5 联结词的完全集§1．6 范式§1．7 逻辑推论习题第二章 谓词逻辑§2．1 谓词和量词§2．2 项和公式§2．3 解释和赋值§2．4 永真式§2．5 等值演算§2．6 逻辑推论习题二第三章 公理系统§3．1 命题逻辑的公理系统§3．2 谓词逻辑的公理系统习题三第四章 归结法原理§4．1 命题逻辑的归结法§4．2 前束范式与斯科伦范式§4．3 谓词逻辑的归结法习题四参考文献第二篇 集合论第五章 集合的基本概念及其运算§5．1 集合与元素§5．2 集合间的相等和包含关系§5．3 幂集§5．4 集合的运算§5．5 有穷集的计数原理§5．6 集合的归纳定义法§5．7 有序偶和笛卡儿乘积习题五第六章 关系§6．1 关系及其性质§6．2 关系的运算§6．3 次序关系  §6．4 等价关系、划分及其他习题六第七章 函数§7．1 基本概念§7．2 函数的复合§7．3 特殊性质的函数§7．4 集合的特征函数习题七第八章 自然数和基数§8．1 自然数及数学归纳法§8．2 基数习题八 参考文献第三篇 图论第九章 基本概念§9．1 有向图及无向图  §9．2 图的基本结构§9．3 子图  §9．4 连通性  §9．5 顶点基和强分图习题九第十章 通路问题§10．1 最短通路§10．2 关键通路习题十第十一章 图的矩阵表示§11．1 邻接矩阵§11．2 有向图的可达性矩阵§11．3 关联矩阵习题十第十二章 树§12．1 树的一般定义§12．2 根树与有序树§12．3 二元树§12．4 生成树§12．5 割集习题十二第十三章 穿程问题§13．1 欧拉图§13．2 哈密顿图习题十三第十四章 二分图的匹配问题§14．1 基本概念§14．2 二分图的最大匹配§14．3 从x到y的匹配习题十四第十五章 平面图及色数§15．1 平面图§15．2 色数习题十五参考文献 第四篇 代数系统第十六章基本概念§16．1 代数系统§16．2 同态和同构§16．3 子代数和商代数习题十六第十七章 半群和群§17．1 半群的概念§17．2 子半群和半群同态§17．3 商半群和半群直积§17．4 群的概念§17．5 子群和群的同态§17．6 变换群、置换群和循环群§17．7 不变子群和商群习题十七第十八章 环和域§18．1 环和域的概念§18．2 子环和环的同态§18．3 理想和商环习题十八第十九章 格和布尔代数§19．1 格的定义与基本性质§19．2 子格和格的同态§19．3 布尔代数§19．4 布尔代数的表示习题十九第二十章 抽象数据类型的代数规范§20．1 标记、项和代数规范§20．2 ∑-代数和范畴§20．3 代数规范的初始语义习题二十参考文献第五篇 有限自动机理论第二十一章 基本概念§21．1 字符表、字符串及其集合的运算§21．2 有限自动机的定义§21．3 有限自动机的等价§21．4 Mealy机与Moore机习题二十第二十二章 有限自动机的简化§22．1 最小有限自动机的定义及性质§22．2 状态集的S划分和格LM§22．3 有限自动机的最小化习题二十二第二十三章 有限自动机和正则表达式§23．1 有限自动机的识别功能§23．2 非确定有限自动机§23．3 正则表达式§23．4 由正则表达式构造FA的算法§23．5 有限自动机和正则表达式的等价性§23．6 正则集合及其性质习题二十三第二十四章 有限自动机的综合与应用§24．1 有限自动机的综合§24．2 FA理论在算法设计中的应用§24．3 FA理论与形式语言理论的关系习题二十四参考文献名词索引

编辑推荐

《离散数学(修订版)》为高等学校教材之一，由高等教育出版社出版。

作者简介

《离散数学(修订版)》由五篇构成。第一篇数理逻辑，内容包括：命题逻辑，谓词逻辑，公理系统，归结法原理。第二篇集合论，内容包括：集合的基本概念及其运算，关系，函数，自然数和基数。第三篇图论，内容包括：基本概念，通路问题，图的矩阵表示，树，穿程问题，二分图的匹配问题，平面图及色数。第四篇代数系统，内容包括：基本概念，半群和群，环和域，格和布尔代数，抽象数据类型的代数规范。第五篇有限自动机理论，内容包括：基本概念，有限自动机的简化，有限自动机和正则表达式，有限自动机的综合与应用。

《离散数学(修订版)》内容系统、全面，概念清晰，叙述严谨精炼，推理详尽严格，语言简明易懂，各部分独立成篇，并有大量例题和习题，便于读者理解和掌握相关知识。《离散数学(修订版)》可作为高等院校本科计算机专业离散数学课程的教材，也可供计算机科学与工程技术人员学习参考。

图书封面

---

 离散数学下载

---