离散数学 Discrete mathematics

Presentation on theme: "离散数学 Discrete mathematics"— Presentation transcript:

1 离散数学 Discrete mathematics
信息学院自动化系

2 课程介绍 现代数学的一个重要分支 是以研究离散量的结构和相互间的关系为主要目标；
其研究对象一般是有限个或可数个元素，充分描述了计算机科学离散性的特点，是信息相关专业的核心课程； 离散数学的应用十分广泛 数字逻辑理论、逻辑电路设计、程序正确性证明、信息编码理论以及大量的图的实际应用模型…

3 课程目标 掌握处理离散结构的描述工具和方法，为后续课程的 学习创造条件； 提高抽象思维和严格的逻辑推理能力，为将来参与创
新性的研究和开发工作打下坚实的基础； 相关领域的应用 希望大家能提供应用实例

4 课程内容 四部分： 集合论 代数结构 集合论、代数结构、图论、数理逻辑
集合基本概念、有限集与无限集、包含排斥原理、映射和函数、单射与满射、二元关系、等价关系、相容关系、偏序关系、集合论的应用； 代数结构 代数运算、代数系统、同态与同构、群、循环群、陪集与商群、环与域、格与布尔代数简介，代数结构的应用；

5 课程内容（续） 图论 图论的基本概念、图的邻接矩阵和关联矩阵、关系图、树、欧拉图、哈密顿图、二分图、平面图，权图中的最短路径，有向图，图论的应用； 数理逻辑 命题与联结词、命题公式、真值表、命题公式的运算、析取范式与合取范式、演绎推理、谓词公式及其运算、谓词推理简介，数理逻辑的应用。

6 教师简介 谭小彬 自动化系副教授 xbtan@ustc.edu.cn 科技实验楼西楼806 研究方向： 未来网络体系架构和网络优化 信息安全
课件地址：

7 参考书目 《离散数学导论（第3版）》 《离散数学简明教程》 徐洁磐 高等教育出版社，2006年； 超星图书馆可以下载电子版 邵学才、张纪勇
科学出版社，1995年。

8 课程安排： 60课时，每周两次课 成绩： 上课要求 ： 作业（30%） 考试（70%） 按时上下课 不影响其他同学
研究方向相关离散数学应用实例（ppt形式） 考试（70%） 开卷 上课要求 ： 按时上下课 不影响其他同学

9 第一部分：集合论 1、集合论介绍： 研究集合的数学理论，包含集合和元素、关系等最基本数学概念。
在大多数现代数学的公式化中，都是在集合论的语言下谈论各种数学对象； 集合论、命题逻辑与谓词逻辑共同构成了数学的公理化基础，以集合论术语来形式化地建构数学对象； 集合论是数学的一个基本分支，在数学中占据着独特的地位，其基本概念已渗透到数学的所有领域； 集合论就成了全部数学的基础，而且有力地促进了各个数学分支的发展。 创始人：康托 Cantor， 德国数学家（ ）

10 第一部分：集合论 1、集合论介绍 集合论体系： 朴素集合论 公理化集合论 模糊集合论

11 悖论（paradox） 在某些公认正确的知识背景下，可以合乎逻辑地建立两个矛盾语句相互推出的矛盾等价式。
K真，当且仅当，K假。 认识论悖论（语义悖论）——“我正在说谎” 狭义逻辑悖论（语形悖论）——→集合论

12 悖论——科学的难题 低估悖论的重要性，把它们当作诡辩或者笑料，从科学进步的角度看来是十分危险的；
我们必须找到它的原因，就是说，必须分析出悖论所依据的前提； 然后，在这个前提中我们必须至少抛弃其中一个，而且还必须研究这将给我们的整个探讨带来什么样的后果。 ——阿尔弗雷德·塔尔斯基 （逻辑学家和数学家）

13 集合论及其发展背景 18世纪，无穷未定义，使微积分理论遇到严重的逻辑困难。
19世纪上半叶，柯西给出了极限概念的精确描述，却没有彻 底完成微积分的严密化，其思想中甚至能产生逻辑矛盾。 19世纪后期，许多数学家又致力于分析的严格化。涉及到对 连续函数的描述。在数与连续性的定义中，再次涉及关于无 限的理论。一切问题指向一个中心——无穷概念、无限集合

14 ∞的悖论——漫长的困扰 两个同心圆点可以一一对应 周长相等吗？ 线段的整体等于部分吗？ N={ 0，1，2，3，...}
A={ 0，1，4，9，...} F(X)=X•X A是N的子集吗？

15 罗素悖论 1902年罗素提出了“罗素悖论” 罗素悖论另一种表示方式：理发师悖论
构造一个所有不属于自身（即不包含自身作为元素）的集合R，R={A｜A∉A}，请问R是否属于R？ 罗素悖论另一种表示方式：理发师悖论 某村庄只有一个人会理发，该村的人都需要理发，理发师规定给且只给村中不自己理发的人理发。 问题：理发师给不给自己理发？

16 罗素悖论的影响 ——第三次数学危机 集合论的悖论，尤其是罗素和策梅罗所发现的一个矛盾，直接在数学界产生灾难性的作用 ——希尔伯特
集合论的悖论，尤其是罗素和策梅罗所发现的一个矛盾，直接在数学界产生灾难性的作用 ——希尔伯特 狄德金放弃了划时代著作《什么是数和数的应用》的出版 弗雷格：我的著作要出版时，发现建筑物的基础塌了 拓扑学权威劳威尔宣布自己过去的工作全在说废话 。。。。。。

17 集合论 产生矛盾（罗素悖论）引发第三次数学危机产生了公理化集合论 说明：19世纪末物理学危机引发相对论、量子力学 公理化集合论
1908年策梅罗提出 后改进为无矛盾的集合论公理，简称ZF公理系统（第一个常用的公理系统） 有些字不认识，最后没打完

18 第一章、集合论初步 集合的基本概念 集合及其元素 这些对象称为集合的元素 一些不同的、确定的对象的全体称为集合 举例：
这些对象可以是具体的，也可以是抽象的，当然也可以是集合； 这些对象称为集合的元素 举例： 全体中国人组成一个集合，每个人 是集合中的元素 所有正整数组成一个集合，每个正整数是集合中的元素

19 集合及其元素 集合中元素的3个特点： ①确定性： ②互异性： ③无序性 任意对象都能确定它是或不是集合的元素
“很大的数”、“个子比较高的人”则不能构成集合（模糊集合论） ②互异性： 集合中的元素均不相同 或者可以说：{a,b,b,c}和{a,b,c}都一样 ③无序性 集合中元素无顺序之分

20 集合的记法 大写字母（带或不带标号）表示集合：A,B,X 小写字母（带或不带标号）表示元素：a,b,x1
若元素a是集合A的元素，记作a∈A，否则a∉A

21 集合的表示方法 列举法/穷举法/枚举法 A={a,b,1,2} 如较多可用省略号 B={1,2,……,100} C={1,2,…………}
按任意顺序逐一列举集合中的元素（元素间用 逗号隔开） 和顺序无关 A={a,b,1,2} 如较多可用省略号 B={1,2,……,100} C={1,2,…………}

22 集合的表示方法 特征法/描述法： 通过特征来描述：即集合就是满足某个特征的元素的全体；
给定一个条件p(x)，当且仅当个体a使p(a)满足时，a∈A ，则表示方法为： A={a|p(a)} 例： A={小于等于2的正整数} B={1,2}， C={x2-3x+2=0的根} D={n|n为自然数，且xn+yn=zn有xyz≠0的整数解} 说明：这4个集合的元素都完全相同，只是表示方法不同，即A=B=C=D，即：集合与其表示方式无关

23 N：正整数 Q：有理数 Z：非负整数 R：实数
常用集合： N：正整数 Q：有理数 Z：非负整数 R：实数 I：整数 P：素数 特殊集合 ①有限集合/无限集合 ②空集：元素个数为0的集合记作Ø ③全集：所有研究对象全体的集合，记作“U”或“E” 说明：全集和研究对象所处的范围密切相关，与研究内容总量限制在某个集合之内时，这个集合就是全集。

24 集合的基数： 有限集合中不同元素的个数，记作|| A={1,2,3} |A|=3 |Ø|=0

25 集合之间的关系 ①集合相等 定义1.1 如果集合A与集合B的元素相同（不考虑顺序），则称这两个集合相等，记作A=B，否则称这两个集合不相等，记作A≠B 两个集合不相等就是有不相同的元素； 后面证明集合相等或不相等，常会用到如下方法： 存在一个元素x，x∈A，且x∉B，或者x∈B，且x ∉A，即A≠B 对任意元素x，x∈A 能推出x ∈B，并且对任意元素x，x∈B能推出x ∈A，即A=B

26 ②包含关系 定义1.2： 说明： 集合A、B，如果元素a∈A，必有a∈B，则称B包含A，或称A是B的子集，记作B⊇A或A⊆B
如果B⊇A，并且存在b使得b∈B但b∉A，则称A是B的真子集，记作B⊃A或A⊂B 即：集合B除过包含A的所有元素外，还有集合A中没有的元素 如果集合A、B之间不满足A⊆B，则称B不包含A，记作 A⊈B 说明： 对于每个非空集合A至少有两个子集A和Ø，根据定义，A和Ø都是A的子集； 称为A的平凡子集，如果A=Ø，则只有一个平凡子集；

27 文氏图 Venn Diagram，John Venn（ ） 平面上的n个圆（或椭圆），使得任何可能的相交部分都是非空的和连通的，则集合之间关系可以用圆之间的关系表示。 说明：主要是为了用来直接说明集合之间的关系 A=B B⊂A

28 E E E E E E E E B B A B A B A A A A C A B A B B A∩B= A∩B=A A-B A∪B
集合间的关系与运算的表示：文氏图(Venn Diagrams) E E E E B B A B A B A A A∩B= A∩B=A A-B A∪B E E E E A A C A B A B B A∩B ~A (A∩B)-C AB

29 相关定理 定理1.1 对任一集合A，必有Ø⊆A 证明：假设Ø⊈A，则至少存在一个x，有x∈Ø而x∉A 定理1.2 对任一集合A，必有A⊆E

30 定理1.4 对于任意两个集合A、B，则A=B的充分必要条件是B ⊆A且A⊆B
充分性： 设B ⊆A且A⊆B ，并且假设A≠B，则一定存在至少一个元素x 使得x ∉ A且x∈B（否则A=B），这与B ⊆A矛盾； 同理，也应至少存在一个元素y，使得 y ∉B且y∈A，这与A⊆B矛盾 综上所述，充分性得证 必要性： 设A=B，且假设B ⊆A且A⊆B中至少有一个不成立； 若A⊆B不成立，则至少存在一个x，x ∈ A但x ∉ B这与A=B矛盾 同理，当B⊆A不成立时也不会推出矛盾，则必要性得证。 综上所述，可证明定理1.4

31 说明 ①空集是唯一的 设 Ø1，Ø2都是空集，由空集的性质可知： Ø1⊆Ø2 且Ø2⊆Ø1 ，由定理1.4可知Ø1=Ø2
②全集E也是唯一的（对于同样的研究背景来讲） ③证明集合相等的方法 ⑴ 恒等式 ⑵设集合A中任意（不能只是某个）元素x∈A，如果能证明x∈B，即A ⊆B，然后再证明B ⊆A （用同样的方法） 则由定理1.4可得A=B

32 1.1.3集合代数（集合运算） 定义1.3 由集合A，B中所有元素合并组成的集合，称为集合A和B的并集，记作A∪B，“∪” 称为并运算。

33 定义1.5 集合A，B若满足A∩B=Ø，则称A与B 是分离的。
A∪B=E，且A∩B=Ø A与B互斥 定义1.6 集合A的补集~A可定义为~A=E-A “~”称为补运算

34 定义1.7 由集合A，B中所有属于集合A而不属于集合B的元素组成的集合，称为集合A对集合B的差集，记作A-B，“-”称为差运算。 A-B= A∩~B
A+B=(A-B)∪(B-A) “+”称为对称差运算，也用“⊕”表示。 说明：A、B所有非公共元素组成的集合

35 集合运算性质 ①交换律 ②结合律 (A∪B)∪C= A∪(B∪C) ③分配率 A∩B=B∩A, A∪B=B∪A
A∩(B∪C)= (A∩B)∪(A∩C) A∪(B∩C)= (A∪B)∩(A∪C)

36 ④同一律 ⑤互补律 ⑥零一律 ⑦吸收律 A∪Ø=A, A∩E=A A∪~A=E, A∩~A=Ø A∪E=E, A∩Ø=Ø
A∪(A∩B)=A, A∩(A∪B)=A

37 集合运算性质 ⑧双补律（双重否定律） ⑨德摩根律 ⑩等幂律（幂等律） ~(~A)=A ~(A∩B)= ~A∪~B
A∪A=A, A∩A=A

38 证明德摩根律： ~(A∪B)= ~A∩~B 思路： 根据互补律A∪~A=E 即如果 A∪B和~A∩~B互补
即 (A∪B) ∪( ~A∩~B) =E 如果能证明上式，则可得出： ~(A∪B)= ~A∩~B

39 证明过程： (A∪B) ∪( ~A∩~B) =((A∪B)∪~A)∩((A∪B)∪~B) 分配律
=((A∪~A)∪B)∩(A∪(B∪~B)) 交换律结合律 =(E∪B)∩(A∪E)) 互补律 =E∩E 零一律 =E 同一律/等幂律

40 1.2幂集，n元有序组及笛卡尔乘积 1.2.1幂集 定义1.9 由集合A的所有子集所组成的集合称为A的幂集，记作2A或者ρ (A) 说明：
例：A={a，b} ρ(A)={Ø，{a}，{b}，{a，b}}

41 定理1.5 若有限集A， |A|=n，则|ρ(A)|=2n
说明： |ρ(A)|=Cn0+Cn1++Cnn= 2n Cni表示从n个元素中取i个组成一个集合，这种集合的数量； Cn0 =Cnn =1说明空集和全集都是唯一的

42 定义1.10 两个按一定次序排列的客体a，b组成一个有序序列，称为有序偶，并记作(a,b)，a，b分别被称为(a,b)的第一客体与第二客体。
n元有序组 定义1.10 两个按一定次序排列的客体a，b组成一个有序序列，称为有序偶，并记作(a,b)，a，b分别被称为(a,b)的第一客体与第二客体。 说明： 有序偶刻画两个客体之间的关系 并不表示由两个元素组成的集合 定义1.11 有序偶(a,b)与(c,d)如果a=c，b=d，则说(a,b)与(c,d)是相等的。 说明：两个客体相等，且顺序相等。

43 定义1.12 n个（n>1）按一定次序排列的客体a1, a2,  an ， 组成一个有序序列，称为n元有序组，记作(a1, a2,  an )， 其中ai为第i客体。
定义1.13 n元有序组(a1, a2,  an )与(b1, b2,  bn ) ，如果ai = bi ，（i=1,2，……，n）则称(a1, a2,  an )与(b1, b2,  bn )是相等的。 说明： 所有对应客体都相等，且顺序相同； 有序偶相等定义的扩展。

44 1.2.3 笛卡尔乘积 定义1.14 集合A,B的笛卡尔乘积可表示为 A×B={(a,b)|a∈A，b∈B} 说明：
①笛卡尔乘积是一个集合； ②集合中的元素是有序偶； ③这些有序偶的第一个客体取自于集合 A，第二个元素取自于集合B； ④这个集合中包括所有的形如③中表示的有序偶。

45 定义1.15 集合 A1, A2,  An 的笛卡尔乘积可表示为 A1×A2××An ={(a1, a2 , an)| ai∈ Ai }
A1×A2××An可表示为An 笛卡尔乘积的基数 当集合A,B均为有限集时，A×B也是有限集 如果|A|=n，|B|=m，则|A×B|=nm，|A×A|=n2

46 与笛卡尔乘积有关的一些恒等式 ①A×（B∪C）=（A×B）∪（A×C） ②（B∪C) ×A=（B×A）∪（C×A） ③ A×（B∩C）=（A×B）∩（A×C） ④ （B∩C) ×A=（B×A) ∩（C×A）

47 1.3包含排斥原理 在有限集合计数时，为了使重叠部分不被重复计数，人们研究出一种排除计数的方法；

48 基本思想： 定理1.6 设A、B为有限集合 ，则有： |A∪B|=|A|+|B|-|A∩B|
先不考虑重叠部分的情况，把包含于某内容中的所有对象的数目先计算出来； 然后再把计数时重复计算的数目排除出去. 定理1.6 设A、B为有限集合 ，则有： |A∪B|=|A|+|B|-|A∩B|

49 =|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
|说明 区域1、2、3都被多加了一次，因此要被减去； 但是减去后，区域4被多减去了一次，因此应该再加上一次；

50 定理1.7设 A1, A2,  An为有限集合，则有 | A1∪A2∪∪An | 例1、分母是1001的最简分数一共有多少？
分析：即找分子中不能整除1001的数 1001可分解为7×11×13 即找不能被7、11、13整除的数

51 例2、在一根长的木棍上有3种刻度线： ①将木棍10等分 ②将木棍12等分 ③将木棍15等分 问题：如果沿每条刻度线将木棍锯断，木棍总共会被锯断多少段？ 分析：有些刻度会重合

52 容斥原理的另一种形式 设Ai是具有性质Pi的元素的子集，具有性质 的元素将记作 ， 用集合术语表示为
的元素将记作 ， 用集合术语表示为 如果不具有n个性质 中的任何一条的元素数量记 并且集合中的元素数量M，则有 由容斥原理：

53 例、x1+ x2+ x3=11，有多少个整数解？ x1 ，x2， x3非负整数，且x1≤3，x2≤4，x3≤6，
解：令P1为x1>3，P2为x2>4，P3为x3>6 则满足不等式x1≤3，x2≤4，x3≤6，的解的个数为 N(P1’P2’P3’) =M- N(P1) - N(P2) - N(P3)+N(P1P2) +N(P1P3) +N(P2P3)-N(P1P2P3) M= N(P1)= … N(P1’P2’P3’)=6

54 错位排列问题 错位排列：使得没有一个物体在它初始位置的排列 例：对于 来说， 是一个错位排列 不是错位排列，因为4在初始位置上 设Dn表示n个物体的错位排列数 例：D3=2，因为对1 2 3 来说，只有2 3 1、3 1 2 是错位排列 利用容斥原理可知

55 容斥原理的使用 在计数前，要先弄清楚计数对象的属性有几种，确定好A1, A2,  An等。一般来讲，只要仔细阅读题目， A1, A2,  An的确定还是不难的。 有了A1, A2,  An等集合以后，要搞清楚它们之间的组合所代表的意义。这步处理不好，计算是无法进行的。 在分析和表示的过程中，要注意分好类，类分不好，表达会乱的，会导致计数出错。一般来讲，分类要注意这么几点： 分类要彻底，既不能重复也不能有遗漏；一个对象只能属于一类，不能有对象不在任何一类中。 一次分类的标准要统一，不能一次分类有多个标准； 分类的方法是不唯一的，要科学的选择分类的方式，以便于表达和计算为选择的依据。

56 容斥原理的使用 在具体的题目中，属性是随问题性质的不同而不同的。
可以是：“得满分”、“及格”、“不及格； 可以是：“身高”、“体重”；可以是：“男生”、“女生”； 可以是：“团员”、“非团员”； 可以是：“直角三角形”、“等腰三角形”、“四边形”、“正方形”、“菱形”、“平行四边形”、“等腰梯形”； 可以是：“红色”、“兰色”、“绿色”等等。 到底被计数的对象具有什么属性，要看问题的具体情况来定。 利用容斥原理来计数只是我们的一种计数选择，不是一定就要用这个原理才能计数，用其它的方法也能计数。只不过是这个原理的计算比较程序化和公式化，比较方便。

57 容斥原理的归属 计数 分类 解读 容斥原理是属于计算数据的，所以从量的角度来看，它属于计数的范畴，是一种计数方法；
从分析和逻辑的角度来看，容斥原理又属于分类的范畴； 分类的一个基本要求就是既不重复也不遗漏，这就和我们计数的要求一致了、合拍了。 解读 “容”就是容纳、涵盖、算在内、无限制条件的。对“容”字的数学解读就是“加上”。 “斥”就是排斥、不要、去掉、剔除、排它的。对“斥”字的数学解读就是“减去”

58 集合论在概率论中的应用 1.4.1 相关概念 概率论中引进集合论，用集合来研究事件，使概率论的研究更加严格化。
样本空间Ω：随机试验所有可能结果组成的集合 基本事件（样本）：样本空间中的元素 随机事件：样本空间的子集 全集Ω：必然事件 空集Ø：不可能事件 事件A,B同时发生：A∩B，事件A,B至少一个发生： A∪B A,B互斥事件： A∩B=Ø A的对立事件~A

59 1.4.2计数问题在古典概率中的应用 在有限集情况下，设样本空间Ω，事件A，A ⊆ Ω | Ω |=n， | A|=m，m≤n
则P（A）=m/n，对于事件A,B P（A∪B）=P(A)+P(B)-P(A∩B) 由容斥原理推出

60 若以连续掷两次骰子分别得到的点数m,n作为点P的坐标，求点P在圆x2+y2=16内的概率。
2017/9/9  若以连续掷两次骰子分别得到的点数m,n作为点P的坐标，求点P在圆x2+y2=16内的概率。

61

62 1.5集合论在计算机科学中的应用 计算机科学的基础； 可应用于计算机科学研究的多个方面； 在新一代智能计算机的发展中具有重要作用
模糊集合论计算机智能模糊推理论。

63 集合的计算机表示 ①数组法 char*set[ ]={“abc”，“123”，“def”} 优点：易于访问
缺点：不便于集合元素中元素的动态增删，移动； 需要连续存在空间 ②链表法 struct setElement { char*element;//集合中元素 char*ncxt }；//当然也可以用双向链表 优点：添加、删除元素方便；不需要连续的空间 缺点：复杂、用较大空间、操作慢

64 ③位串法 数组法和链表法的最大缺点是集合并、交、差运算很耗时 位串法：设全集E={a1, a2,  an }，对于其子集来说，可用一个二进制位串来表示。 如果ai ∈A，则位串的第i位为1，否则为0 优点：很容易通过二进制串的位操作进行集合运算 集合运算 位运算 并 按位或 交 按位与 非~ 按位取反 差 第二操作数按位取反后与第一操作数按位与 （A-B=A∩~B） 对称差 按位异或