工科离散数学.pdf

21 世纪高等学校计算机规划教材 工科离散数学 牛连强 陈 欣 张胜男 编著 内 容 简 介 离散数学是研究离散结构及其相互关系的数学学科，是计算机科学与技术及其相关专业的理论基础。本书以数理逻辑为基础，介绍命题逻辑、一阶谓词逻辑、集合论、关系、函数、代数结构和图论。不同于一般的离散数学书籍，本书内容主要以满足一般工科院校计算机科学与技术、软件工程、信息与计算科学以及其他信息领域相关专业的离散数学课程教学要求为主，不求大求全，尤其是根据工程教育的要求，注重介绍有应用价值的理论，避免理论上的缠绕，内容简介务求通俗明了。同时，还增加了相当数量的工程应用方面的简介以及相关参考文献，使学习者能够快速了解这些理论的实际工程用途。本书的配套网络课程、电子教案和习题辅导用书将陆续推出，以满足现在立体化教学的要求。本书不仅能很好地满足一般工科院校的离散数学课程教学需要，也特别适合自学。未经许可，不得以任何方式复制或抄袭本书之部分或全部内容。版权所有，侵权必究。图书在版编目(CIP)数据 工科离散数学/牛连强，陈欣，张胜男编著.北京：电子工业出版社，2017.2 ISBN 978-7-121-30641-9 I工 II牛 陈 张 III离散数学高等学校教材 IVO158 中国版本图书馆 CIP 数据核字(2016)第 305974 号 策划编辑：王羽佳 责任编辑：郝黎明 印 刷：三河市鑫金马印装有限公司 装 订：三河市鑫金马印装有限公司 出版发行：电子工业出版社 北京市海淀区万寿路 173 信箱 邮编：100036 开 本：787980 1/16 印张：12.75 字数：367.2 千字 版 次：2017 年 2 月第 1 版 印 次：2017 年 2 月第 1 次印刷 定 价：35.00 元 凡所购买电子工业出版社图书有缺损问题，请向购买书店调换。若书店售缺，请与本社发行部联系，联系及邮购电话：(010)88254888，88258888。质量投诉请发邮件至 ，盗版侵权举报请发邮件至 。本书咨询联系方式：(010)88254535，。前 言 离散数学是研究离散量的结构及其相互关系的一门学科，是由逻辑学、集合论、关系理论、图论、抽象代数、布尔代数甚至算法设计、组合分析、离散概率和计算模型等汇集起来的一门综合学科。由于数字电子计算机是一个离散结构，只能处理离散的或离散化了的数量关系和数学模型，这正是离散数学的主要内容，因此，离散数学构成了计算机相关学科的基础学科。为此，中国计算机科学与技术学科教程 2002将其界定为计算机科学与技术专业的核心基础课程，美国IEEE&ACM 也确定其为计算机专业的核心课程。应该说，计算机及其相关专业的绝大部分课程，都是直接以离散数学作为理论基础的，也可以说是离散数学的直接运用，或者说需要依靠离散数学课程中建立的观点、方法和逻辑思维能力去解决具体问题。因此，离散数学课程的教学目的就是要建立逻辑（数学）推理能力、了解重要的离散对象与结构、构建和应用解决离散问题的模型及具备算法思维等。现在有一些相当成功的离散数学教材，如 Kenneth H.Rosen 的Discrete mathematics and its applications、左孝凌的离散数学和屈婉玲、耿素云的离散数学等。在近 30 年的教学实践中，我们采用这些教材取得过一定的成功，但也存在着诸多问题。概括地说，这些教材大而全，更关注理论与系统的完整性，这与教材的定位甚至国家对精品教材、规划教材、优秀教材等的要求和评价标准不无关联，缺乏对学习对象本身的情况和层次、学时的减少以及工程教学目的的变化等实实在在因素的关注。这些问题在湖南大学的张洪圣等老师编写的同名教材中已经部分提及，我们深有同感。举例说，普通工科高校在我国高校中占大多数，但她们的学生与 985、211 高校存在着很大的差异，以学术研究为目标的教材和教学内容上的趋同不仅达不到“拔高”的目标，反而使学生过早丧失了学习兴趣，形成一系列不良的连锁反应。又如，在仅有 4864 学时的教学时间里，我们不能期望把类似数论、离散概率、组合设计、形式语言、自动机等内容都灌输给普通院校的学生。本书的写作目的是为一般的而非拔尖的普通工科高校的计算机、软件工程及其相关专业提供一本通俗、易于理解、易于自学、有一定工程应用背景和实际问题引导的教材。因此，本书不追求体系的完整、内容的全面和对理论的深入探讨，也不关注竞赛、考研等问题。为了达到目标，体现自身的特点，我们注重如下问题并采取了我们认为适当的做法：内容按教学实际取舍。舍弃中学学过的简单组合计数、前文提到的离散概率、数论、组合设计、形式语言等内容，以及数据结构等课程中涵盖的算法，不使内容过于膨胀，并尽量避免与后续课程重复。次序编排突出逻辑思维。以逻辑学而不是集合论为出发点，用命题逻辑和谓词逻辑主导解决后续所有问题的思维，以便强化分析、解决问题的逻辑性和能力。对问题平实、透彻讲解。离散数学也是数学，内容抽象。通过信息相关领域实例、问题引 IV导、分析、评价、辨析等步骤，将问题讲解透彻，避免读者需要花过长的时间思考或借助参考书才能读懂，甚至利用“理解”标签予以提示并展示应理解的程度。特别地，对大量值得注意或认真分析的关键问题，都通过“辨析”标签给出讨论和警示。概括、突出问题核心。对解决一类问题的核心内容给予总结、概括和突出，说明此类问题的实质和解决方法的关键，而不是给出一个具体题目的解法。适当引入工程问题。选取相关领域中有代表性的工程应用实践问题作为示例或习题，消除学生总认为学理论与实际脱节的误解，激发其学习课程和解决实际问题的兴趣。对思考和应用进行引导。作为教材，对于新的成果、大量的相关问题及其解决方案不可能全部囊括，仅是一斑。对于很多问题，通过“延伸”标签指出其发展方向、实际应用案例、存在的解决方法等，并列出可供参考的论文等素材，以引导学生自己探索。当然，这些内容作为课堂的延伸，以辅助学习和思考为主，研究为辅。因此，列出的论文都不是专门研究理论而是程度较浅的应用型文章、教学论文乃至书籍。洗练定理与习题。过多罗列已有的结果令人眼花缭乱，还会误导学生机械记忆而不是由基本概念出发进行主动思考、探究和发现结果。同时，尽管多做习题有助于问题的理解，但需要大量的时间和精力，过多习题也容易使人恐惧并产生排斥心理。为此，尽量精简了定理与习题。考虑到本课程中概念（定义）对内容理解和题目求解的极端重要性，故将重要概念纳入习题，直接提醒学生弄懂并记住这些定义。使本书体现上述特点源自于学生的实际情况、教学上的要求以及人才培养工程化的形势变化等因素。我们认为，在把更多的时间、思考、总结、发现任务交给学生时，教师要能使学生学会学习，教材要有助于学生自主学习。教材既不能包罗万象，求深求全，也不能只是“干巴巴”的纲，更不应连一节中有几个重要概念、主要方法之类的总结都由教材代替。考虑到目前离散数学课程多在一年级中开设，我们没有对算法的描述以及程序实现提出过多要求，以免徒增额外负担且冲淡主题。此外，还对重要名词配以英文对照，以期可以辅助对专业外文词汇的掌握。全书分为 8 章，分别是“命题逻辑”“谓词逻辑”“集合论基础”“关系”“函数”“运算与代数系统”“环、域、格和布尔代数”“图”。这种安排次序的目的是期望以严密的逻辑思维贯穿各部分内容，以使思考和推理更富有理论依据。全书的内容可在 70 个学时内讲完。本书的几位作者都具有 20 多年的课程教学经验，且未间断地从事本科离散数学课程的教学工作，无论是对课程内容、体系、教学方法和安排，还是工程教育的发展方向与工科学生的实际情况均有着深刻的理解，这使得本书的写作更有针对性。我们期望通过本书使离散数学的内容更容易理解、学习和掌握，促进课程教学质量的提高，但囿于个人见解，仍会存在诸多缺憾，欢迎读者指出其不足，也期待能与读者做更多的交流（）。此外，本书的出版得到了沈阳工业大学和学校诸多老师的支持和帮助，作者深表感谢！作 者 目 录 第 1 章 命题逻辑 1 1.1 命题 1 1.2 逻辑联结词 3 1.2.1 基本联结词 3 1.2.2 其他联结词 6 1.3 命题公式与真值表 7 1.3.1 命题公式 7 1.3.2 真值表 8 1.4 命题翻译 9 1.4.1 合取命题 9 1.4.2 可兼与不可兼析取命题 10 1.4.3 条件命题 10 1.4.4 多联结词命题 11 1.5 命题公式的值与等价 14 1.5.1 命题公式的分类 14 1.5.2 命题公式的等价 14 1.5.3 联结词的功能完备集 17 1.5.4 由德摩根律到对偶原理 17 1.6 范式 19 1.6.1 简单的范式 19 1.6.2 小项与大项 20 1.6.3 主析取范式与主合取范式 21 1.7 推理理论 24 1.7.1 蕴含与论证 24 1.7.2 自然推理系统 26 第 2 章 谓词逻辑 34 2.1 谓词、个体词与量词 34 2.1.1 个体词与谓词 34 2.1.2 量词与量化 36 2.2 谓词逻辑中的命题翻译 38 2.2.1 特殊化个体词的命题 38 2.2.2 量词量化的命题 38 2.3 量词约束与谓词公式的解释 42 2.3.1 量词对个体词变元的作用 42 2.3.2 谓词公式的解释与求值 43 2.3.3 量词与联结词的搭配 44 2.4 谓词逻辑中的基本等价和蕴含 关系 45 2.4.1 基本等价与蕴含关系 46 2.4.2 利用等价关系计算前束范式 49 2.5 谓词演算的推理理论 50 第 3 章 集合论基础 57 3.1 集合的概念与表示方法 57 3.1.1 集合描述 57 3.1.2 集合的包含与相等 58 3.1.3 空集与全集 59 3.1.4 集合的幂集 61 3.2 集合运算 63 3.2.1 基本运算 63 3.2.2 多集合的交与并 65 3.3 集合运算的性质与证明方法 68 3.3.1 集合运算的性质与演算证明 68 3.3.2 基于定义的集合运算证明 方法 69 3.4 序偶与笛卡儿积 72 3.4.1 序偶与元组 73 3.4.2 笛卡儿积 73 第 4 章 关系 77 4.1 二元关系的含义与表示 77 4.1.1 二元关系 77 VI4.1.2 关系的矩阵和图表示法 79 4.2 关系运算 80 4.2.1 关系求逆与复合 81 4.2.2 关系运算的性质 82 4.2.3 利用关系图与关系矩阵实现 关系运算 84 4.2.4 多关系的复合 86 4.3 关系的性质 88 4.3.1 自反与反自反关系 88 4.3.2 对称与反对称关系 89 4.3.3 传递关系 91 4.3.4 特殊关系的判定 91 4.4 关系的闭包 94 4.4.1 闭包的概念 94 4.4.2 闭包计算 95 4.5 相容关系与等价关系 99 4.5.1 集合的覆盖与划分 99 4.5.2 相容与等价 100 4.5.3 相容关系产生的完全覆盖 101 4.5.4 等价关系产生的划分 102 4.5.5 由覆盖、划分生成相容关系 和等价关系 103 4.6 序关系 106 4.6.1 体现部分次序的偏序关系 106 4.6.2 哈斯图 106 4.6.3 链与全序关系 108 4.6.4 偏序集的特殊元素 109 第 5 章 函数 112 5.1 从关系到函数 112 5.1.1 函数的概念 112 5.1.2 函数集 113 5.1.3 特殊函数 114 5.2 函数的逆与复合 117 5.2.1 双射的反函数 117 5.2.2 函数的复合 117 5.2.3 函数运算的性质 119 5.3 集合的基数 120 5.3.1 集合等势 121 5.3.2 有限集与无限集 122 5.3.3 可数集与不可数集 122 5.3.4 基数比较 124 第 6 章 运算与代数系统 126 6.1 运算及其性质 126 6.1.1 n 元运算 126 6.1.2 二元运算的主要性质 127 6.2 二元运算中的特殊元素 129 6.2.1