离散数学基础及实用算法

出版时间：2009-6  出版社：清华大学出版社  作者：吴修国 编  页数：266  

前言

　　离散数学形成于20世纪70年代初期，是随着计算机科学的发展和计算机应用的日趋广泛而建立起来的一个数学分支，它为计算机科学技术和工程应用提供了有力的理论工具，其中涉及的概念、原理和方法在计算机及相关学科领域都有着重要应用。离散数学与计算机科学中的数据结构、操作系统、编译原理、算法分析、逻辑设计、系统结构、机器定理证明等课程联系紧密，是培养学生缜密思维，提高学生素质的核心课程之一。因此，离散数学已经显示出强大的生命力和渗透力，发展前景广阔。　　本课程不但要培养学生的抽象思维能力，而且更注重培养学生运用数学方法解决实际问题的能力。然而，从作者多年讲授离散数学的效果来看，有不少学生在学习完抽象的数学理论后，对于其中相关理论和方法的学习目标和作用并不明确，也不知道这些理论的真正作用，尤其是不能将离散数学的学习与其计算机实现相结合。往往是单纯地学习理论知识，缺乏与实际问题的联系，这是离散数学教学时一个亟待改进的问题。　　本书的特色　　本教材在内容取材和写作风格上做了相应的整合与尝试。将抽象的离散数学理论和具体的计算机实现有机地联系起来，提出了离散数学的教学离不开计算机实验的思想，主要表现在：　　（1）将离散数学理论教学与算法实现结合。　　（2）将多种算法和数据结构有机结合。　　（3）将离散数学理论与应用结合。　　（4）通俗易懂、循序渐进地给出算法的实现。　　本书的主要内容　　本教材分为基本理论和算法实现两个部分。基本理论包括数理逻辑、集合与关系、代数系统以及图论四方面内容；算法实现穿插于理论介绍之后，详细地给出了具体的实现算法，其目的都是为读者进一步理解基本理论。本书所提供的源程序可以作为读者自主开发的基础。

内容概要

　　《离散数学基础及实用算法》包括离散数学基础理论和算法实现两部分内容。基础理论部分包括数理逻辑、集合与关系、代数系统以及图论等。算法实现部分以大量的算例系统地给出了离散数学中典型理论成果的计算机实现。《离散数学基础及实用算法》包含丰富的算法、大量的应用实例，在详细解释源代码的同时，为读者进一步自主开发提供了便利。　　《离散数学基础及实用算法》可以作为普通高等学校、计算机、信息科学或其他相关专业本、专科教材，同时，可供科技人员、教学人员以及研究生参考。将离散数学理论教学与算法实现结合。将多种算法和数据结构有机结合。将离散数学理论与应用结合。通俗易懂、循序渐进地给出算法的实现。

书籍目录

第1篇 数理逻辑及实用算法第1章 命题逻辑1.1 命题的基本概念1.2 命题联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其他联结词1.7 对偶与范式1.8 命题演算的推理理论第2章 谓词逻辑2.1 谓词的概念与表示2.2 谓词公式与翻译2.3 变元的约束2.4 谓词公式的等价式与蕴含式2.5 谓词公式的范式2.6 谓词演算的推理理论第3章 数理逻辑中的实用算法3.1 命题公式的真值表算法3.2 命题公式的主析（合）取范式算法山第2篇 集合与关系及实用算法第4章 集合与关系4.1 集合的基本概念4.2 集合的运算4.3 序偶与笛卡尔积4.4 关系及其表示4.5 关系的性质4.6 复合关系和逆关系4.7 关系的闭包运算4.8 集合的划分与覆盖4.9 等价关系与等价类4.1 0相容关系与相容类4.1 1偏序关系与偏序集第5章 函数5.1 函数的概念5.2 逆函数和复合函数5.3 基数的概念5.4 基数的比较第6章 集合与关系中的实用算法6.1 集合的基本运算算法6.2 集合的幂集算法6.3 关系的闭包运算算法6.4 等价关系和等价类算法第3篇 代数系统及实用算法第7章 代数系统7.1 代数系统的引入7.2 运算及其性质7.3 半群7.4 群与子群7.5 阿贝尔群与循环群7.6 陪集与拉格朗日定理7.7 同态与同构7.8 环与域第8章 代数系统中的实用算法8.1 代数系统性质判定算法8.2 群的判定算法第4篇 图论及实用算法第9章 图论9.1 图的基本概念9.2 路与回路9.3 图的矩阵表示9.4 欧拉图和哈密尔顿图9.5 平面图9.6 对偶图与着色9.7 树与生成树9.8 根树及其应用第10章 图论中的实用算法10.1 计算机中图的表示10.2 图的连通性算法10.3 欧拉图的判定算法10.4 哈夫曼树的构造算法10.5 最小生成树算法第11章 程序集成11.1 系统总界面的开发11.2 系统总界面算法参考文献

章节摘录

　　从以上的分析可以看出，表达思想的语句有不同的类别，数理逻辑中研究的是出现较多而又比较规范的语句即可以判断出真或假的陈述句。　　定义1.1.1 命题（proposition）　　凡是能判断是真或是假的陈述句称为命题。　　这里所说的“真”可以理解为正确的、符合事实逻辑的；“假”可以理解为错误的，不符合事实逻辑的。本书中一般用True或者T来表示真，用False或F表示假.　　如前面的（1）－（5）都是命题，（6）－（11）都不是命题。　　在判定一个命题的真假时，从语法上就是看它是否是陈述句。由于在推理过程中，无法从疑问句、祈使句、感叹句中获取有用的信息。因此，一切疑问句、祈使句、感叹句都不能称为命题。但需要注意的是，那些“自指谓”的陈述句，不在其列。如“本页这一行的这句话是假话”这一语句，它的结论是对自身而言的，就是所谓的“自指谓”。这种“自指谓”的语句往往会产生自相矛盾的结论，即所谓的悖论。如上面这句话，如果承认它是真的，由于本页这一行中没有别的话，所以必须承认它是假的；另一方面，如果承认它是假的，这刚好就是这句话所说的，所以又必须承认它是真的。因此，这句话本身包含了悖论，故我们在判断一个语句是否是命题时把这种语句排除在命题之外。　　上述语句（11）也是这种情况。　　例1.1.1 中国在第30届奥运会上取得金牌数和奖牌数第一。　　解：这句话，虽然不能马上分辨真假，但是只要在伦敦奥运会结束时就可以验证，还是可以知道的，因此是命题。　　例1.1.2 “一个偶数可表示成两个素数之和”（哥德巴赫猜想）。　　解：这句话是命题，或为真或为假，只不过当今尚不知其是真命题还是假命题。　　例1.1.3 雪是黑的。　　解：这是一个陈述句，可确定真值。显然其真值为假，或说为F。所以，是一个命题.　　定义命题的目的是希望我们在推理时能从命题中获取有用信息。由于本章主要介绍的是有关命题推理的理论方法，因此，尽量不要去纠缠各种具体命题的真假问题，而是将命题当作是一个抽象的数据概念来处理，把命题定义成非真必假的陈述句。此时，所关心的并不仅仅是这些陈述句究竟是真还是假，更关心的是它可以被赋予真或假的可能性，以便考查被赋予真值后它与其他命题的联系。　　在数理逻辑中，使用大写字母A，B，…，P，Q，…，或者用带有下标的大写字母，如A1，B5，Pi等表示命题。例如，　　P：今天下雨。　　P可表示“今天下雨”这个命题的名。　　也可以用加方括号的数字表示命题，例如，[12]：今天下雨。　　表示命题的符号称为命题表示符，P或[12]称为标识符。

编辑推荐

　　《离散数学基础及实用算法》可以作为普通高等学校、计算机、信息科学或其他相关专业本、专科教材，同时，可供科技人员、教学人员以及研究生参考。将离散数学理论教学与算法实现结合。将多种算法和数据结构有机结合。将离散数学理论与应用结合。通俗易懂、循序渐进地给出算法的实现。