离散数学_邓毅雄主编.pdf

书书书离 散 数 学主编邓毅雄副主编廖辉传许景飞参编者刘立月胡林峰江西高校出版社书书书图书在版编目(C I P)数据离散数学/邓毅雄主编 南昌:江西高校出版社，2011 1ISBN 978 7 5493 0172 0.离 .邓 .离散数学.0158中国版本图书馆 CIP 数据核字(2011)第 012552 号出 版 发 行社址邮 政 编 码总编室电话销 售 电 话网址印刷照排经销开本印张字数版次印数书号定价江西高校出版社江西省南昌市洪都北大道 96 号330046(0791)8504319(0791)8513417www juacp com南昌市光华印刷有限责任公司江西太元科技有限公司照排部各地新华书店787mm 960mm1/1616 5283 千字2011 年 1 月第 1 版第 1 次印刷1 2000 册ISBN 978 7 5493 0172 026 80 元赣版权登字 07 2011 12版权所有侵权必究前言人类已经进入信息化社会，信息技术的核心是计算机科学，以计算机、微电子和通信技术为主的信息技术革命是社会信息化的动力源泉计算机的出现是人类文明史上最重要的事件之一，而随着计算机科学的发展，作为研究有限与离散系统的离散数学已成为一门越来越重要的学科离散数学（）是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支，是计算机科学与技术、软件工程等计算机类专业的重要专业基础课由于离散数学可以充分描述计算机学科离散性的特点，它在计算机科学中具有重要的作用，它是其他计算机、软件类课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理、数据库和算法等课程的先修基础课程通过离散数学课程的学习，学生不仅能获得进一步学习和研究计算机、软件相关专业课程所需要的数学基础知识，而且可以提高学生的抽象能力、逻辑思维能力等，有助于培养学生严谨、规范的科学态度本着适用、够用的原则，本书全面介绍离散数学的主要内容全书共分四部分 章，第一部分为数理逻辑，包括命题逻辑与谓词逻辑；第二部分为集合论，包括集合、二元关系与函数；第三部分为代数结构，主要介绍代数系统的基本概念与性质，群、环、域和格；第四部分为图论，包括图的基本概念、一些特殊图及图的应用全书体系严谨、叙述深入浅出，注重理论与应用相结合，每章配有大量的例题和习题全书由邓毅雄、廖辉传、许景飞、刘立月、胡林峰等编写，其中第章由胡林峰编写，第、章由刘立月编写，第、章由廖辉传编写，第、章由邓毅雄编写，第 章由许景飞编写邓毅雄完成了全书的审阅与统稿工作在编写过程中参考了大量的离散数学书籍和资料，在此一并向有关作者表示感谢由于编者水平所限，我们期待广大读者提出宝贵的意见和建议编者 年 月目录第一篇数理逻辑第章命题逻辑 命题及其表示 命题符号化及联结词 命题公式及真值表 等值演算 其他联结词 对偶与范式 命题的推理理论 命题逻辑的应用举例 小结 习题一 第章谓词逻辑 谓词逻辑的基本概念 谓词公式与解释 谓词逻辑等值式与前束范式 谓词逻辑推理理论 小结 习题二 第二篇集合论与二元关系第章集合论 集合的概念与表示方法 集合的基本运算 集合中元素的计数 小结!习题三 第章二元关系 笛卡儿积的概念 二元关系及其表示方法 关系的运算 关系的性质 关系的闭包运算 等价关系 偏序关系 元关系在计算机科学中的应用 小结 习题四 第章函数 函数的基本概念与性质 函数的逆与复合函数 小结 习题五 第三篇代数系统第章代数系统 代数系统的基本概念 代数系统的运算性质及特殊元素 同态与同构 小结 习题六 第章群与环 半群与独异点 群与子群 特殊的群 环与域 群在计算机科学中的应用 离散数学小结 !习题七 第章格与布尔代数 格及其性质 子格与格同态 特殊格 布尔代数及其应用 小结 习题八 第四篇图论第章图论基础知识 图的基本概念 通路、回路及图的连通性 图的矩阵表示 小结 习题九 第 章一些特殊的图 欧拉通路与欧拉图 哈密顿图 二部图 平面图 树与生成树 小结 习题十 第 章图论的若干应用 树的若干应用 最短路问题与关键路径问题 图的着色 小结 习题十一 主要参考文献 目录书书书第一篇数理逻辑研究思维(或推理)的形式结构和规律的学科可分为辩证逻辑与形式逻辑两种 辩证逻辑是以辩证法、认识论的世界观为基础的逻辑学，形式逻辑主要是对思维的形式结构和规律进行研究的一门工具性学科逻辑是探索、阐述和确立有效推理原则的学科，最早是由古希腊学者亚里士多德(Aristotle)创建的 思维的形式结构包括了概念、判断和推理之间的结构和联系;由一个或几个判断推出另一判断的思维形式，就是推理 研究推理的方法很多，用数学方法来研究推理的形式结构和推理规律的数学学科称为数理逻辑 数理逻辑属于形式逻辑的一种，是用数学的方法来研究逻辑问题这里所指的数学方法就是引进一套符号体系的方法 所以，数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的 数理逻辑已在逻辑电路、自动控制、程序设计、人工智能及计算机科学的其他领域有着广泛的应用数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其他分支，如集合论、数论代数、拓扑学等的发展有重大的影响，特别是对新近形成的计算机科学的发展起了推动作用，如它与人工智能、语言学、逻辑学等学科均有密切的联系 反过来，其他学科的发展也推动了数理逻辑的发展数理逻辑内容相当丰富，大体可分为五部分，即证明论、模型论、递归函数论、公理集合论、逻辑演算 本书介绍的是数理逻辑最基本的内容，也是与计算机科学关系最为密切的:命题逻辑和谓词逻辑(一阶逻辑)第 1 章命题逻辑命题逻辑是研究命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法 命题是指具有具体意义且又能判断它是真还是假的句子我们也注意到，命题逻辑是谓词逻辑的基础，只有掌握好了命题逻辑才能学好谓词逻辑1 1命题及其表示在数理逻辑中，为了表达概念、陈述理论和规则，常常需要对应用语言进行描述，但是日常使用的自然语言，往往叙述时不够准确，也容易产生二义性，因此，需要引入一种目标语言，这种目标语言和一些公式符号，就形成了数理逻辑的形式符号体系 目标语言就是表达判断的一些语言的汇集，而判断就是对事物肯定或否定的一种思维形式数理逻辑研究的中心问题是推理，而推理的前提和结论都是表达判断的陈述句，因此这种能表达判断的陈述句就是推理的基本单位，称为命题 陈述句是陈述一个事实或者表达一个人的看法的语句，一个陈述句的判断只有两种可能，一种是正确的判断，一种是错误的判断 因此，一个命题，总是具有一个“值”，称为真值 真值只有“真”和“假”两种，分别用符号 T(或 1)和 F(或0)表示 判断为正确的命题的真值为真，即 1;判断为错误的命题的真值为假，即 0 因而命题又可以表示为具有确定真值的陈述句 一切不能判断真值的句子，如感叹句、疑问句、祈使句等，都不是命题命题可分为两种，一种是不能分解为更简单的陈述句的命题，称作原子命题或简单命题;一种是由联结词和简单命题复合构成的命题，称作复合命题例题 1 1判断下列句子中哪些是命题?(1)中华民族是勤劳勇敢的(2)雪是黑色的(3)2+3=5(4)地球外的星球上也有生物2离散数学(5)5x+1 11(6)请不要迟到!(7)天气多好呀!(8)明天下午开会吗?(9)我正在说谎(10)小王正在学英语和日语在上面这些例子中，(1)、(2)、(3)、(4)、(10)是陈述句，并且有确定的真值，因此都是命题，其中(10)是复合命题 尽管目前无法确定命题(4)的真值，但是从事物的本质而论，它的真值是确定的(5)是陈述句，但它没有确定的真值 当 x=1 时，5+1 11 的真值为假;而当 x=3 时，15+1 11 的真值为真 因此(5)不是命题(6)、(7)、(8)不是陈述句，因此都不是命题(9)是逻辑学中的悖论，真值不确定，因此不是命题从以上的分析可以看出，判断一个句子是否是命题，首先看它是否是陈述句，其次看它的真值是否是确定的1 2命题符号化及联结词在数理逻辑中，用英文字母或带下标的英文字母表示简单命题，本书用小写的英文字母，如 p，q，r，pi，qi，ri表示简单命题用符号来表示命题，称为命题的符号化 例如，p:雪是黑色的q:你是优秀大学生表示命题的符号成为命题标识符，p 和 q 就是标识符 一个命题标识符如果表示确定真值的命题，就称为命题常项或命题常元，如上面的 p、q命题标识符也可用来表示不是命题的特殊的陈述句 如例 1 1 中，(5)不是命题，但是当 x 的值确定后，(5)的真值也确定了 这种陈述句称为命题变项或命题变元 因为命题变项的真值不确定，故命题变项不是命题以上讨论的是简单命题 简单命题可以直接用英文字母来表示在自然语言中，常常使用“不是”“和”“或”“如果，那么”“当且仅当”等一些联结词 在数理逻辑中，主要是研究由原子命题与逻辑联结词组合而成的复合命题，即命题逻辑所讨论的正是多个命题联结而成的复合命题的规律性 联结词是复合命题中的重要组成部分，为了便于书写和进行推理演算，必3第一篇数理逻辑须对联结词作出明确规定并符号化 下面介绍各个联结词1 否定联结词定义1 1设 p 为一命题，则 p 的否定为一新的命题，称为 p 的否定式，即为p，读作“非 p”为否定联结词 若 p 为真，则p为假;若 p 为假，则p为真，即p 为真当且仅当 p 为假 命题 p 及其否定p的关系如表 1 1 所示表 1 1pp0110例题 1 2(1)设 p:雪是黑色的，则p:雪不是黑色的 显然，p 的真值为0，p的真值为 1(2)设 q:2+3=5，则q:2+35 显然，q 的真值为 1，q的真值为 02 合取联结词定义 1 2设 p、q 为两个命题，则复合命题“p 并且 q”称作 p 与 q 的合取式，记为 pq，读作“p 合取 q”“”为合取联结词 pq 为真当且仅当 p、q 皆为真 联结词“”的定义如表 1 2 所示表 1 2pqpq000010100111例题 1 3设 p:今天下雨;q:明天下雨 则 p、q 的合取为:pq:今天下雨并且明天也下雨显然，只有当 p、q 都为真时，pq 才为真合取的概念与自然语言中的“与”“且”“和”意义相似，但并不完全相同例如，命题“李明与王华是同学”是简单命题，可符号化为 p 设 p:李明与王华是同学设 p:我们去看电影，q:2 是偶数，则命题“我们去看电影与2 是偶数”可符号化为 pq在自然语言当中，上述命题是没有意义的，因为命题 p、q 没有内在联系，但在数理逻辑中，p、q 的合取式 pq 仍然是一个新的命题，当 p、q 的真值确定4离散数学后，pq 的真值也可确定 复合命题的真值，不能根据参与复合的命题之间是否存在联系来判断除了“与”外，自然语言中的“既又”“不但而且”“不仅而且”“虽然但是”等，都可以符号化为合取联结词“”例题 1 4将下列命题符号化(1)天气不但炎热而且湿度高(2)天气不仅炎热而且湿度高(3)天气既炎热，湿度又高(4)天气虽然炎热，但是湿度高解设 p:天气炎热，q:天气湿度高 则上述 4 个例子都可以符号化为 pq3 析取联结词定义1 3设 p、q 为两个命题，则复合命题“p 或 q”称作 p 与 q 的析取式，记为 pq，读作“p 析取 q”“”为析取联结词 pq 为假当且仅当 p、q 皆为假 联结词“”的定义如表 1 3 所示表 1 3pqpq000011101111由析取的定义可以看出，析取联结词“”与自然语言中的“或”的意义不完全相同 自然语言中的“或”有两种含义，有时为“排斥或”，有时为“相容或”析取式 pq 表示的是“相容或”例题 1 5将下列命题符号化(1)博尔特是 100 米冠军或 200 米冠军(2)小王现在在宿舍或在图书馆(3)选张三或李四中的一人当副班长解(1)设 p:博尔特是 100 米冠军，q:博尔特是 200 米冠军 这里的“或”是“相容或”，因此命题可直接符号化为 pq(2)设 p:小王在宿舍，q:小王在图书馆 这里的“或”是“排斥或”，但是因为 p、q