离散数学 (2009 年度畅销榜NO.15312 )

本书是作者参照国内外多种同类教材，结合多年的教学实践，在自编讲义的基础上整理而成的。全书覆盖了计算机专业和电子信息专业最需要的基本内容，它包括四大部分共14章。介绍了数理逻辑、集合论、代数系统和图论的基础知识以及这四个部分之间的内在联系，叙述详细、推演严密，注重基础，深入浅出，便于理解。\r\n　　本书可作为高等院校计算机类、电子信息类等相关专业的教材，也可供计算机专业的自考人员、从事计算机研究的工作人员参考。

第一部分　数理逻辑\r\n　第一章　命题逻辑基本概念\r\n　　§1.1　命题及其符号化\r\n　　　§1.1.1　命题\r\n　　　§1.1.2　命题符号化\r\n　　§1.2　合式公式和真值赋值\r\n　　　§1.2.1　合式公式及层次\r\n　　　§1.2.2　真值赋值及公式分类\r\n　　§1.3　真值表和真值函数\r\n　　习题一\r\n　第二章　命题逻辑等值演算\r\n　　§2.1　等值关系\r\n　　§2.2　联结词的全功能集\r\n　　§2.3　范式\r\n　　§2.4　数字逻辑电路初步\r\n　　　§2.4.1　门电路和触发器\r\n　　　§2.4.2　组合逻辑电路的设计\r\n　　　§2.4.3　时序逻辑电路的设计\r\n　　习题二\r\n　第三章　命题逻辑自然推理\r\n　　§3.1　推理的形式结构\r\n　　§3.2　自然推理系统P\r\n　　§3.3　常见的证明方法\r\n　　习题三\r\n　第四章　谓词逻辑的基本概念\r\n　　§4.1　谓词和量词\r\n　　§4.2　一阶语言\r\n　　　§4.2.1　一阶语言\r\n　　　§4.2.2　解释和赋值\r\n　　　§4.2.3　公式的分类\r\n　　§4.3　一阶逻辑等值演算\r\n　　　§4.3.1　等值演算\r\n　　　§4.3.2　前束范式\r\n　　§4.4　一阶逻辑形式推理\r\n　　　§4.4.1　推理定律\r\n　　　§4.4.2　推理规则\r\n　　习题四\r\n第二部分　集合论\r\n　第五章　集合代数\r\n　　§5.1　集合的概念及表示\r\n　　§5.2　集合运算\r\n　　§5.3　集合定律\r\n　　§5.4　有限集的计数问题\r\n　　§5.5　有序对与卡氏积\r\n　　习题五\r\n　第六章　二元关系\r\n　　§6.1　元关系及其表示\r\n　　§6.2　二元关系的性质\r\n　　§6.3　元关系的运算\r\n　　　§6.3.1　关系的限制和像\r\n　　　§6.3.2　关系的逆\r\n　　　§6.3.3　关系的合成\r\n　　　§6.3.4　关系的闭包\r\n　　§6.4　特殊关系及其性质\r\n　　　§6.4.1　等价关系及性质\r\n　　　§6.4.2　相容关系及性质\r\n　　　§6.4.3　序关系及性质\r\n　　习题六\r\n　第七章　函数\r\n　　§7.1　函数基本概念\r\n　　§7.2　函数的合成\r\n　　§7.3　反函数\r\n　　§7.4　特殊函数\r\n　　　§7.4.1　特征函数\r\n　　　§7.4.2　变换函数和置换函数\r\n　　§7.5　集合的基数\r\n　　习题七\r\n第三部分　代数系统\r\n　第八章　代数结构\r\n　第九章　格与布尔代数\r\n第四部分　图论\r\n　第十章　图\r\n　第十一章　通路应用问题\r\n　第十二章　树\r\n　第十三章　平面图\r\n　第十四章　偶图与匹配\r\n附录1　数学工具\r\n附录2　习题答案或提示\r\n参考文献

离散数学是计算机专业的一门核心课程，为计算机科学和技术的发展奠定了重要的数学基础，其基本思想、概念和方法广泛渗透到计算机科学和技术的各个领域，如谓词演算成为程序理论的一种重要研究工具；布尔代数为开关电路的研究提供了重要的的分析工具，并导致数字逻辑理论的建立；代数结构中的群环域理论，为编码理论提供了新的途径；后两者也是电子和信息专业的基础理论，数字逻辑理论是数字电路的基本理论，数字信号作为现代通信最主要的手段，其相应处理必须利用数宇电路，而数字信号的传送过程中，编码是不可缺少的；有限状态札理论不仅贯穿：于时序逻辑设计的分析和设计过程，同时为通信系统的仿真方法提供了有力的工具；图论理论则广泛应用到信号系统的分析、电网络及通信网络之中。 因此完全可以说离散数学的基本理论和研究成果也广泛应用到电子和信息领域，离散数学的这些重要成果和作用，使得它成为一个计算机科学工作者和工程师所必备的基础理论知识，同时也是一个从事电子和信息处理的人员不可或缺的基础知识。 离散数学在纯粹数学和应用数学中都占有重要的地位，它的内容极其丰富，其中许多重要问题源于数学游戏或者一些看似简单的趣味数学问题的解决，从其发展历史来看，尽管300多年前离散数学有关问题就出现了，而且经过这几百年的研究发展，许多问题已成为一个一个的体系，但正是由于电子计算机的问世，计算技术的发展，人们才对这些离散量进行分析，研究其结构、特点及他们之间的联系，从而形成一门较为完整的离散数学理论，反过来，离散数学理论的发展也促进了计算技术的飞跃发展。 本书覆盖了离散数学的基本内容，包括了计算机专业和电子信息专业最需要的部分，共分为四大部分14章，它们是数理逻辑、集合论、代数系统、图论。尽管作为应用数学的离散数学应用非常广泛，但许多读者了解了离散数学的基本概念，却不知怎样应用，为此本书特别阐述了一些电子和信息方面的应用，如数字逻辑电路初步就是怎样运用逻辑等值演算理论设计数字逻辑电路，这些章节均已标出。 一般来说，本书所涉及的四大部分内容都各成一体，但它们有着内在的联系，如利用数理逻辑这种应用形式化语言研究推理的方式，可以充分地描述集合论的各种运算，而有了集合和运算之后，才可以定义代数系统，图论作为关系的形象化表示，却提供特殊的方法分析集合元素之间的关系。考虑到这种内在的逻辑联系，本书编排以数理逻辑作为基础首先介绍，掌握好对后续内容可以起到事半功倍的效果，所以这里着墨较重较细，然后应用数理逻辑充分地介绍另一个基础集合论，这不仅可以加强新知识的理解，还可以巩固数理逻辑的知识。并不是每位读者都了解离散数学所需要的数学基础，本书给出了部分用到的数学工具，这些内容实际上也是离散数学的有机组成部分。 学习离散学习的目的在于培养一个人的抽象思维能力、逻辑思维能力以及综合归纳分析的能力，因此本书力求理论上叙述严谨、推演严密，同时注重基础知识完整，概念与实例密切结合，深入浅出，便于理解。 本书是在编者近年来在北京大学信息科学技术学院讲述离散数学的自编讲义的基础上整理而成的，在编写过程中，参考了国内外多种离散数学文献，并总结了编者的教学经验。它可作为高等理工科院校计算机类、工程类本、专科专业的离散数学的教材，而其中的基础理论部分对计算机专业自考人员理解基本概念很有帮助。 本书经过多届同学们的使用，他们提出了许多宝贵意见，特别是孙琰同学为讲义成书做了许多工作，在此一并感谢。 由于水平有限，加之成书时间仓促，缺点、错误在所难免，敬请读者批评指正。