离散数学

出版时间：2009-11  出版社：电子工业出版社  作者：马叔良 编  页数：194  

前言

　　改革开放三十年来，我国经济高速发展。当今，在激烈的国际竞争环境下，从劳动密集型向技术集约型的经济结构转型成了当务之急。而人才问题是这次转型成败的一个关键因素，教育首当其冲。近年来，创新型的科学技术研究和生产链的两端——合格的从事基础理论研究和高级技术生产的人才奇缺已经成为制约我国生产力发展的一大问题。无论从理论上考虑，还是从一些成功的高级技术人才的经验来看，培养具有必要的理论基础和善于把理论知识应用到生产实践的创新型人才是我们高等教育的培养目标。除却少数培养基础理论研究人才的纯理科专业外，高等教育既不能是理论脱离实际的“纯理论”教育，也不能是为某一生产线所谓“对口岗位”培养高级操作人员的培训班。我们始终认为，掌握必要的理论知识并且善于用理论指导实践的科技人才才是当今我国经济建设所需要的。　　数学作为～切科学的基础是不言而喻的事实，只是不同的学科领域更加密切地依重数学的某一些分支而已。计算机科学和某些工程学科则是以“离散数学”作为其主要的研究工具。一是因为目前使用最广泛的各种架构的机器都是所谓“数字模式”的，即这种机器的内部有且仅有两种不同的信息元，在硬件内用高、低电平或者介质的不同磁化方向或晶相等加以记录，数学上用“离散量”0和1对这两种信息元加以描述（抽象的对应物）。二是因为当今通过计算机运算的绝大多数课题，要么直接就是基于若干离散对象之间的种种联系，要么就是将一个或简单或复杂的连续变量之间的关系，通过所谓的数值分析的方法用相应的离散变量近似地加以描述，并且这种近似的精度是可以以计算量的增大来换取的。譬如，简单到连续函数图形下的曲边梯形面积的求解，复杂至飞行器的空气动力外形的网格设计方法等，都是处理离散变量的过程。三是因为计算机的软、硬件系统本身就是一个有限结构或有限离散结构。　　本书是为计算机科学等专业的学生写的一本离散数学基础教材。理论部分取材于数学的几个与计算机学科联系紧密的理论分支，并且在不致与其他课程内容重复的宗旨下，尽可能地给出了一些运用数学理论解决专业问题的实例。　　我们认为，同一门课程，不论是本科还是专科，在介绍其基本概念、术语和基本理论方面，同样需要做到严缜性和系统性。因为这些概念、术语和基本理论构成离散数学的理论体系，是准确理解和掌握离散数学的基石。本教材正是基于这样的理解来安排教学内容的。虽然教材的各章内容取材于若干数学分支，通过仔细的考虑安排了一个合理的次序，使之前后呼应，并以数理逻辑为论证工具贯穿全书，希望借以培养学生的逻辑思维能力。尽管如此，我们还是不打算使本书包含离散数学的所有内容。本书省略了数值分析、组合学、概率等理论的内容，这主要是考虑到学生在他们不同阶段的学习中会涉猎这些知识。

内容概要

离散数学和微积分不同，离散数学是以离散对象为研究对象的，是计算机专业和其他一些工程专业的数学基础。本书包含了数理逻辑、集合论、数函数和递推关系、图论、代数系统及布尔代数等主要内容。本书注重理论的系统性和准确性，特别重视对理论难点的诠释，叙述通俗易读。　　本书适合作为高等学校计算机专业或其他工程类专业教材使用，也可以供对离散数学有兴趣的读者自学。

书籍目录

第1章 绪论　1.1 离散数学的研究对象　1.2 离散数学的主要内容　1.3 学习离散数学的方法第2章 数理逻辑　2.1 命题　　2.1.1 命题的概念　　2.1.2 命题的表示　2.2 命题联结词　　2.2.1 联结词的定义　　2.2.2 命题逻辑中联结词的最小集　2.3 命题的合式公式　　2.3.1 合式公式　　2.3.2 语句的符号化　2.4 真值表、永真式和永假式　　2.4.1 真值表　　2.4.2 永真式和永假式　2.5 公式的等价和蕴含　　2.5.1 公式的等价　　2.5.2 公式的蕴含　2.6 公式的主范式　　2.6.1 主析取范式　　2.6.2 主合取范式　2.7 命题演算的推理理论　　2.7.1 有效推理的概念　　2.7.2 有效推理的方法　2.8 命题逻辑和二值逻辑器件　2.9 一阶谓词逻辑　2.10 命题函数和个体变量及量词　　2.10.1 命题函数　　2.10.2 量词　2.11 谓词公式　　2.11.1 谓词公式　　2.11.2 变量的约束和替换　　2.11.3 谓词演算中的等价与蕴含　2.12 谓词演算的推理理论　习题第3章 集合和关系　3.1 集合和集合的运算　　3.1.1 集合的基本概念　　3.1.2 集合的运算　　3.1.3 集合运算中的恒等式　　3.1.4 序偶和笛卡儿积　3.2 关系　　3.2.1 关系及其表示法　　3.2.2 几种特殊的关系　　3.2.3 关系的运算　3.3 等价关系和集合的划分　　3.3.1 等价关系　　3.3.2 等价关系与划分　3.4 序关系和哈斯图　　3.4.1 序关系　　3.4.2 偏序关系的哈斯图　　3.4.3 偏序集中的某些特殊元素　3.5 函数及其运算　　3.5.1 函数的概念　　3.5.2 函数的复合　　3.5.3 逆函数　习题第4章 数函数和递推关系　4.1 数函数概念　4.2 数函数的基本运算　4.3 数函数的母函数　4.4 递推关系　　4.4.1 常系数线性递推关系　　4.4.2 用母函数求解数函数的通式　习题第5章 图论　5.1 图的基本概念和术语　5.2 路和回路　5.3 图的矩阵表示　5.4 树和生成树　　5.4.1 无向树的概念　　5.4.2 最小生成树　5.5 有向树及其应用举例　　5.5.1 有向树的概念　　5.5.2 根树的一个应用举例　5.6 欧拉图与哈密顿图　　5.6.1 欧拉图　　5.6.2 欧拉定理的一个应用举例　　5.6.3 哈密顿图　5.7 最短路径与最长路径问题　　5.7.1 最短路径　　5.7.2 最长路径　5.8 平面图　习题第6章 代数系统　……第7章 格与布尔代数参考文献

章节摘录

　　推理是人类特有的思维活动。人们在社会实践中自觉或不自觉地通过感官接受外界的消息形成所谓表象，同类表象的反复出现在人脑中建立起一个概念。概念已不再囿于个别的表象而具有一类表象的本质属性，这就是概念的内涵。反过来说，所有归纳出该概念的具有特定表象的事物（对象）组成了概念的外延。例如，人们在品尝了苹果、梨、香蕉等之后，将具有各种特定香味而富含营养和水分的植物果实概括为“水果”这一概念。客观世界里实际并不存在具体的一个水果，但水果这一概念却包涵了每一个苹果、梨、香蕉等。因此，我们说概念是存在于人脑里的对现实世界对象的一种抽象，它只存在于人的思维中。而水果这一概念的外延却是由客观世界中存在的所有有水果属性的个体组成的。我们可以向别人展示一只梨，并对他说：这是一只梨，它是一种水果（严格地说，他应当说这是水果中的一个）。但任何人都无法展示水果是什么。这就是说，概念存在于思维之中，而概念的外延存在于客观世界。当然，以上的叙述只是为了使大家明白概念是怎样产生而举的一个特殊例子。现实生活中还有很多“抽象的概念”，如时间、空间、数学上的点等。事实上，我们根本不可能找到一个只有位置而无大小的几何点。但是，我们照样可以完美地将所有的实数和几何上的一根有方向的直线，即所谓数轴对应起来。于是我们要对前面提到的“外延存在于客观世界”一语做一些补充说明。通常，在科学技术领域里，人们在研究某些现象时发现，必须对某些客观实体做出更为抽象的概括，摒弃客体的某些属性，张扬它的局部属性，形成一种全新的概念。这样做了，往往可将被研究事物的本质属性突现出来。例如，几何上的点就是从具有一定大小的普通的点，通过忽略其大小而强调其几何位置所得的。这样做了，就使得实数理论建立在一个有形的对应物——数轴上了。不要低估了这样做的影响。从此，几何学与代数学建立起密切的联系，使得解析几何、画法几何、微分几何得以借助分析手段长足地发展起来。所以说，“概念的外延存在于客观世界”一语的正确理解应当是：人们不可能杜撰一个根本不反映任何客观事物本质属性的概念。如果有这样的概念，那只能存在于迷信或神话中。　　概念还不是人类思维的全部，判断是人们更具创造力的思维活动。所谓判断，就是对某些概念之间的必然联系做出的断言。判断的真实性最终只能为客观实践所证实或否定。这就是我们通常说的“实践是检验真理的唯一标准”。数理逻辑主要研究的就是如何从一组已知判断，通过所谓有效推理而最终获得一个全新判断的逻辑学分支。　　说到有效推理，这是一组明确规定的法则，允许从一个或一组已知判断，得到一个新的判断。特别要强调的是：有效推理是经过反复实践认证符合客观规律的一种人类的正确思维法则。但它只保证推理本身是正确的，并不能保证推理的结果——最终得出的判断也正确。因为如果作为推理前提的判断是虚假的或局部是虚假的话，即使推理过程是有效的，我们也不能保证结论一定是正确的。我们唯一可以保证的是在正确的前提下，经过有效推理必定产生正确的结果。