泸西县图书馆“U书快借”平台

编辑推荐

本书主要读者对象是省重点和一般院校计算机类、电子工程类、信息管理和信息工程类、数学类等理工科学生。也可作为重点大学非研究类型的理工科学生的教材或参考书。

展开

精彩书摘

第1章绪论 　　1.1 离散量与离散数学 　　离散数学是包含数理逻辑、数论、代数、图论等多个数学分支内容的一门学科，它的研究对象是离散量的结构以及离散量之间的相互关系。离散量用于描述量之间相互关联的紧密程度。有些量之间的关联是松散的，其分布是稀疏的，这些量称为离散量。例如，整数全体、有限个实数、有限集合等所代表的量都是离散量。而有些量之间的关联是紧致的，它们的分布是稠密的、连续的，这些量称为连续量。例如，实数全体所代表的量是一个连续量。离散量是相对于连续量而言的，目前还没有关于离散量的严格定义。为了更好地把握离散数学的研究对象，下面给出离散量的一个较为严格的定义。 　　【基本量】定义1.1 一个独立的不再细分的对象称为一个基本量。 　　例如，每一个自然数n都可以作为一个基本量；三个实数2、3、6.5可分别定义为三个基本量；集合A={a1，a2，，ak}中的每一个元素都可以定义为一个基本量。 　　注：基本量是在讨论具体问题时作为一个基准的量来定义的，当一个对象被定义为基本量以后，就不再进行进一步的分解。 　　例如，在购买飞机的交易中，其价格以元为基本量，那么无论飞机价格如何浮动，都要以元为*小的价格单位，不能有更小的零头。又如，设集合A={[0，1]，[2，3]}，把A中的元素定义为基本量，则A有两个基本量[0，1]和[2，3]。作为基本量，[0，1]不能再进一步分解，只能作为一个整体对待。 　　【可数无穷集】定义1.2 设A是一个集合，如果存在集合A与自然数集之间的双射，则称A为可数无穷集。 　　【离散型集合】定义1.3 设A是一个集合，若A是有限集或可数无穷集，则称A是离散型集合。 　　【连续统】定义1.4 全体实数所构成的集合称为连续统(continuum)。 　　【连续型集合】定义1.5 设A是一个集合，如果存在集合A与连续统之间的双射，则称A为连续型集合。 　　【一个集合所代表的量】定义1.6 设A是一个集合，把A中的每一个元素都定义为一个基本量，则A中的基本量全体称为A所代表的量。 　　集合A所代表的量是由A中所有成员构成的。“集合A”与“集合A所代表的量”这两个概念具有不同的含义：对于集合A来说，A中的成员是A的元素，仅仅表示一个对象，没有量的含义；而对于集合A所代表的量来说，A中的每一个成员是一个基本量，可以作为量来运算和操作。例如，设A={1，2，5，10，20，50，100}，作为集合，A由7个元素组成，每个元素都是数，不代表任何的量。若把A中的每一个元素都定义为一个基本量，则A代表了7个量。例如，可以用A所代表的量来表示人民币的面值。 　　【离散量】定义1.7 设A是一个离散型集合，把A中的每一个元素都定义为一个基本量，则A所代表的量称为离散量。 　　换言之，设x是一个变量，若x的所有取值构成的集合是一个离散型集合，则称x是一个离散量。 　　例如，令x表示“一个姓张的中国人”，则x的所有取值构成的集合为M={a|a是中国人且姓张}，M是一个有限集，M是离散型集合，因此，x是一个离散量。 　　【连续量】定义1.8 设A是一个连续型集合，把A中的每一个元素都定义为一个基本量，则A所代表的量称为连续量。 　　换言之，设x是一个变量，若x的所有取值构成的集合是一个连续型集合，则称x是一个连续量。 　　例如，令x表示“一个负数”，则x的所有取值构成的集合为H={b|b是实数且b＜0}，H是一个连续型集合，因此，x是一个连续量。 　　例1.1 全体整数所代表的量是离散量；全体有理数所代表的量也是离散量。 　　解：因为整数集Z是可数无穷集，有理数集Q也是可数无穷集，所以，按定义1.7，Z所代表的量是离散量，Q所代表的量也是离散量。 　　例1.2 开区间(0，1)上的全体实数所代表的量不是离散量。 　　解：因为区间(0，1)上的全体实数组成的集合不是可数无穷集，所以，该集合所代表的量不是离散量。 　　【离散数学与计算机数学】离散数学是在计算机科学与技术的发展过程中派生出来的一门学科，而不是在数学的研究过程中从某个数学领域(或数学专题)分离出来的一个数学分支。离散数学的诞生是计算机科学和技术发展的需要。早期，“离散数学”是作为大学计算机专业一门课程的名称出现的。美国于20世纪70年代开始开设“离散数学”课程。随着计算机硬件和软件的迅速发展，计算机的应用领域不断扩大，许多问题都借助于计算机来解决。但是，计算机不能完美地解决所有实际问题，这是由计算机的系统结构决定的。人们现在用的计算机的系统结构本质上仍属于冯诺依曼结构。这种系统结构的特征是，在计算机运行一个程序的过程中先将组成程序的指令和相关数据一同存放在计算机的存储器中，然后在执行程序时计算机按照程序指定的逻辑顺序把指令从存储器中读出来逐条执行。由于计算机以字节为单位存储数据，且任何一台计算机只能存储有限字节，因而，一台计算机只能存储有限个数据和指令。所以，计算机只能处理离散型数据。另外，计算机在不同领域中的应用需要不同的数学工具和数学方法；在解决不同的实际问题时需要建立不同的数学模型和不同的算法。而这些数学工具和方法分布在多个数学分支中。于是，人们就把这些在计算机应用中常用到的数学知识和方法归集到一起构成一门课程，给计算机专业的学生讲授。由于这门课程的内容所涉及的量都是离散量，所以把这门课程称为离散数学。 　　离散数学所涉及的数学分支主要包括：集合论、逻辑演算、递归论、数论、线性代数、抽象代数、布尔代数、组合论、图论、概率论、近似计算、离散化方法等。到目前为止，从理论上讲，离散数学还没有自己独*的理论体系，离散数学所讨论的内容都是其他数学分支中已有的内容。离散数学只关注能在计算机上应用的数学方法。对于一些不能直接在计算机上应用的方法，如连续函数、积分等，离散数学关注的是如何将它们离散化，然后再用计算机来处理。 　　可以用一句话来概括离散数学：离散数学就是应用于计算机上的数学内容和数学方法。所以，也有人把离散数学称为计算机数学。 　　1.2 离散数学的地位和作用 　　数学方法是计算机理论和技术的基础，是计算机在实现方面*有力的工具之一，许多计算机课程都包含大量的数学内容。举例说明如下。 　　(1) 在“C程序设计”中用到数理逻辑的知识。C语言是一种形式语言，C语言中的语句都可看做一个逻辑公式。IF语句就是一个典型的“蕴含式”逻辑公式。C语言中的关系运算、关系表达式和逻辑运算、逻辑表达式等都用到了逻辑演算的知识，它们的运算法则都遵循逻辑演算的规则。另外，C语言中表示n维数组的方法，就是集合论中表示n元关系的方法。 　　(2) 在“数据结构”中用到集合论、图论、递归论方法等知识。 　　(3) 在“数据库系统”中用到集合论和谓词逻辑等知识。关系数据模型中的操作用到集合论中的关系运算。基于逻辑的数据模型以一阶谓词逻辑作为数据模型，其操作都是以逻辑演算方法为基础的。 　　(4) 在“编译原理”中用到形式语言、逻辑演算、图论、布尔代数等知识。 　　(5) 在“数字电路与逻辑设计”中用到逻辑演算、布尔代数(也称逻辑代数)等知识。 　　(6) 在“编码理论”中用到抽象代数、线性代数、数论、布尔代数等知识。编码理论是计算机加密技术的理论基础。 　　(7) “操作系统”“算法设计与分析”“人工智能”“计算机网络”等许多计算机专业课程都用到离散数学知识。 　　在“离散数学”课程出现之前，各门计算机课程所需要的数学知识都是在讲授该课程时进行补充讲授。由于没有单独开设数学课，学生在各门计算机课程中学到的数学知识是零碎的、不完整的，因此不能系统地掌握相关的数学知识。然而，数学知识的缺乏直接影响到计算机专业课程的预期目标。另外，许多计算机专业课程包含相同的数学内容，在多门计算机专业课程中分别重复讲授相同的数学内容，造成了时间上的浪费。于是，美国的大学就把计算机专业课程中常用的数学知识汇编在一起作为单独的一门课程来讲授。这样的课程是专为计算机专业提供数学基础的，所以早期也把这样的课程称为“计算机数学基础”。随着计算机科学与技术的不断发展及计算机在多个领域的广泛应用，计算机对数学工具的要求越来越多。因而，离散数学所涉及的内容也越来越广泛、越来越深入，现已发展成为一门独立的数学学科。 　　由于许多学科的研究和应用都把计算机作为主要工具，许多信息和数据都需要用计算机表示(或显示)。因此，离散数学也成为电子工程、信息技术等学科的数学基础。 　　离散数学不但作为理论基础在计算机科学中有着重要的地位和作用，而且作为应用技术在计算机求解问题中也起着极大的作用。 　　用计算机求解实际问题的过程可分为四大步骤。 　　(1) 用数学语言描述问题，或称为建立实际问题的数学模型。 　　(2) 给出解决问题的步骤，或称为设计解决问题的算法。 　　(3) 写出实现算法的程序。 　　(4) 在计算机上运行程序并验证程序的正确性。 　　在这四个步骤当中，每一个步骤的完成都需要数学工具。 　　在第一步中，需要用抽象的数学概念、数学符号和数学结构来表示实际问题。例如，开发一个城市道路交通管理系统，借助于计算机来管理城市交通。首先就要用图论中的图表示城市的交通网络。实际生活中的交通网络图是地图的样式，两地间道路的长短呈一定的比例，有些弯曲的道路在地图上画出来也是弯曲的。但是，用数学方法表示网络图中两点间的连线时不用真正的线条，而是用顶点集中的一个序对来表示。例如，用(u，v)表示连接顶点u与顶点v的一条边，用一个二元组G=？V，E？表示一个图，其中，V是图的顶点集，E是图的边集。也可以用一个矩阵来表示一个图。总之，只有用数学模型把实际问题表示出来，才能用计算机解决问题。 　　在第二步中，要给出解决问题的算法。例如，要确定某两个地点之间是否有通路，有多少条通路？在实际生活的交通图中，可以按某种经验确定两地间是否有通路。但在计算机求解问题过程中，必须先把实际问题转化为数学问题，然后写出求解数学问题的步骤。这种解决问题的步骤就是算法。这样把实际问题(找两地间的通路)转化为数学问题(找图中两点间的通路)，解决这类问题的数学算法有图的搜索算法或矩阵运算的算法等。 　　第三步是写出实现算法的程序，也就是通常所说的编程。计算机不能直接运行用数学语言描述的算法，只能执行程序设计语言的指令，必须用程序设计语言的指令描述这些算法，才能在计算机上运行。算法中所描述的数据都是用数学结构表示的，所以在程序中描述数据也必须用数学方法来解决。 　　在第四步中，把程序放到计算机上运行并验证程序的正确性。在程序验证过程中*重要的是验证算法的正确性。一个算法的正确性是指对于待求解的这类问题的任何输入实例，按照算法的操作都可得出正确的输出结果。有些算法对某一组数据的输入可得到正确的输出结果，对另一组数据的输入却得到错误的输出结果，这种算法就不是正确的算法。算法的正确性必须用数学方法(如数学归纳法等)或逻辑推理的方法来证明，不能用若干组数据来验证。因为算法中有些变量可以取无穷多个值，此时，有限个值的验证不能说明算法的正确性。 　　由以上分析可知，在计算机求解问题过程中，每一个步骤的实现都以数学知识和数学方法为基础，没有数学工具计算机就解决不了问题。至此，我们已经看到离散数学在计算机科学与技术中的地位和作用，同时也回答了为什么要学离散数学这个问题。 　　1.3 计算机为什么要依赖数学 　　为什么计算机一定要依赖数学？在用计算机解决实际问题的过程中能否绕过数学或用别的办法来替代数学的作用呢？例如，在处理文字、网页、艺术、音乐、自然语言翻译等与数学无关的问题时，能否避开数学工具和数学方法呢？我们的回答是：使用计算机的人在处理这些问题时可以不涉及数学，但开发这些应用软件

展开

目录 前言 第1章绪论 1 1.1 离散量与离散数学 1 1.2 离散数学的地位和作用 3 1.3 计算机为什么要依赖数学 5 1.4 如何学好离散数学 5 第2章命题逻辑 8 2.1 命题逻辑概述 8 2.2 命题及命题联结词 9 习题2.2 13 2.3 命题公式及其赋值 14 习题2.3 24 2.4 用命题公式描述实际问题 25 习题2.4 31 2.5 命题公式的等值演算 32 习题2.5 41 2.6 命题公式的范式 41 习题2.6 55 2.7 命题逻辑的推理理论 57 习题2.7 64 2.8 命题逻辑的归结演绎推理 66 习题2.8 71 第3章谓词逻辑 72 3.1 谓词逻辑概述 72 习题3.1 75 3.2 谓词公式 76 习题3.2 79 3.3 用谓词公式描述实际问题 80 习题3.3 90 3.4 谓词公式的解释 91 习题3.4 96 3.5 谓词公式的等值演算 97 习题3.5 104 3.6 谓词逻辑的自然演绎推理 105 习题3.6 109 第4章集合论 112 4.1 集合的基本概念 112 习题4.1 115 4.2 集合运算 116 习题4.2 121 4.3 集合的包含关系与恒等关系 121 习题4.3 125 4.4 有穷集合的计数 126 习题4.4 131 4.5 二元关系 131 习题4.5 160 4.6 函数与映射 163 习题4.6 167 第5章代数系统 169 5.1 代数运算 169 习题5.1 173 5.2 代数系统 174 习题5.2 183 5.3 群 185 习题5.3 191 5.4 环与域 192 习题5.4 194 5.5 格 194 习题5.5 197 5.6 布尔代数 198 习题5.6 200 第6章图论 201 6.1 图的基本概念 201 习题6.1 204 6.2 图的连通性 205 习题6.2 208 6.3 图的矩阵表示 210 习题6.3 212 6.4 有向图 213 习题6.4 217 6.5 欧拉图与哈密顿图 218 习题6.5 224 6.6 带权图 225 习题6.6 229 6.7 树 230 习题6.7 236 习题答案及提示 239 参考文献 274

展开