离散数学全册配套最完整精品课件1.ppt

1、1 离散数学 主讲：韩兰胜 博士 副教授 H 88学时 2 课课 程程 说说 明明 一、离散数学课程的地位和作用 离散数学是计算机专业的一门核心基础课程。离散数学是计算机专业的一门核心基础课程。 1 离散数学为计算机专业的后继课程如数据结构、操作系统、数离散数学为计算机专业的后继课程如数据结构、操作系统、数 据库、编译原理、网络和算法设计等课程提供必要的数学基础。据库、编译原理、网络和算法设计等课程提供必要的数学基础。 2 2 为学生今后从事计算机科学和技术各方面的工作提供有力的为学生今后从事计算机科学和技术各方面的工作提供有力的 工具。工具。 3 3 离散数学是现代数学的一个重要分支，通过该

2、课程的学习可离散数学是现代数学的一个重要分支，通过该课程的学习可 以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养以提高学生的抽象思维、严格推理以及综合归纳分析能力，培养 出高素质的人才。出高素质的人才。 3 二、离散数学课程的特点二、离散数学课程的特点 离散数学课程是应计算机科学和技术发展的离散数学课程是应计算机科学和技术发展的 需要，综合了高等数学的多个分支而形成的。其需要，综合了高等数学的多个分支而形成的。其 特点是以离散量为研究对象，内容丰富，涉及面特点是以离散量为研究对象，内容丰富，涉及面 较宽。因此概念多、定理多、推理多并且内容较较宽。因此概念多、定理多、推理多并且内容较

3、为抽象。但由于它是为学生后继专业知识的学习为抽象。但由于它是为学生后继专业知识的学习 做必要的数学准备，因此它研究的内容均比较基做必要的数学准备，因此它研究的内容均比较基 础，难度不大。础，难度不大。 4 三、如何学好离散数学三、如何学好离散数学 要学好这门课程，首先必须充分认识到这门课程的上述特要学好这门课程，首先必须充分认识到这门课程的上述特 点，需要做到以下几点：点，需要做到以下几点： 1 熟读教材。熟读教材。准确理解各个概念和定理的含义（结合多个例子准确理解各个概念和定理的含义（结合多个例子 来理解），必要的推理过程要看懂、理解（它可以帮助你熟悉来理解），必要的推理过程要看懂、理解（它

4、可以帮助你熟悉 和深刻理解定理的含义）。和深刻理解定理的含义）。 2 独立思考，大量练习。独立思考，大量练习。仅靠熟读教材并不能将书本上的知识仅靠熟读教材并不能将书本上的知识 变成你自己的知识，在熟读教材的基础上，必须通过大量练变成你自己的知识，在熟读教材的基础上，必须通过大量练 习，独立思考来真正获取知识。习，独立思考来真正获取知识。 3 注重抽象思维能力的培养。注重抽象思维能力的培养。数学与其他学科相比较具有数学与其他学科相比较具有 较高的抽象性，而离散数学的抽象性特点更为显著，它有着大较高的抽象性，而离散数学的抽象性特点更为显著，它有着大 量抽象的概念和抽象的推理，要学好这门课程必须具有

5、较好的量抽象的概念和抽象的推理，要学好这门课程必须具有较好的 抽象思维能力，才能深入地掌握课程内容。抽象思维能力，才能深入地掌握课程内容。 5 第四部分第四部分 数理逻辑。数理逻辑。包括命题逻辑和谓词逻辑。（教材的包括命题逻辑和谓词逻辑。（教材的 第九、十章第九、十章 四、四、 离散数学课程的主要内容离散数学课程的主要内容 离散数学课程的主要内容可以分为四个部分：离散数学课程的主要内容可以分为四个部分： 第一部分第一部分 集合论。集合论。包括集合、关系和函数。（教材的第一、包括集合、关系和函数。（教材的第一、 二、三章）二、三章） 第二部分第二部分 代数系统。代数系统。包括代数系统的一般概念，

6、几类典型包括代数系统的一般概念，几类典型 的代数系统。（教材的第四、五、六、七章）的代数系统。（教材的第四、五、六、七章） 第三部分第三部分 图论。图论。包括图的基本概念，几种特殊的图。（教包括图的基本概念，几种特殊的图。（教 材的第八章）材的第八章） 6 五、五、 教材及参考书教材及参考书 2 参考书：参考书：离散数学习题题解离散数学习题题解 洪帆、付小青编，华中洪帆、付小青编，华中 理工大学出版社。理工大学出版社。 1、教材：教材：离散数学基础离散数学基础 第二版，洪帆主编，华中理第二版，洪帆主编，华中理 工大学出版社工大学出版社。 7 第一章第一章 集集 合合 本章采用朴素集合论的方法，

7、介绍有关集合的一些基本本章采用朴素集合论的方法，介绍有关集合的一些基本 知识，内容显得较为直观，学起来易于接受。但集合及其相知识，内容显得较为直观，学起来易于接受。但集合及其相 关的概念是本门课程后面各章内容的基础，读者务必熟练的关的概念是本门课程后面各章内容的基础，读者务必熟练的 掌握。掌握。 主要内容如下：主要内容如下： 1.1 1.1 集合及其表示方法集合及其表示方法 1.2 1.2 集合间的关系集合间的关系 1.3 1.3 集合的运算和运算定律集合的运算和运算定律 1.4 1.4 集合成员表集合成员表 1.5 1.5 集合的分划与覆盖集合的分划与覆盖 8 又例如又例如 所有的正整数组成

8、一个集合，每一个正整数均是这个集 合的元素。 例如例如 全体中国人可组成一个集合，每一个中国人均是这个集合的 元素 第一章第一章 集集 合合 1.11.1集合及其表示方法集合及其表示方法 一、集合和元素一、集合和元素 v 把一些确定的、彼此不同的事物作为一个整体来 看待时，这个整体便称为是一个集合集合。 v 组成集合的那些个体称为集合的元素元素。 通常用大写英文字母来标记集合，用小写英文字母标 记组成集合的个体 若个体a是集合A的元素，则记作“aA” 若a不是集合A的元素，则记作“a A” 9 几个常见的集合的表示符号： N：所有正整数的集合。：所有正整数的集合。 Q Q：所有有理数的集合。：

9、所有有理数的集合。 Z Z：所有非负整数的集合。：所有非负整数的集合。 R R：所有实数的集合。：所有实数的集合。 I I：所有整数的集合。：所有整数的集合。 N Nm m：从：从1 1到到m m，这，这m m个正整数的集合。个正整数的集合。 P P：所有素数的集合。：所有素数的集合。 Z Zm m：从：从0 0到到m-1m-1，这，这m m个非负整数的集合。个非负整数的集合。 于是于是2N2N，2.5 N2.5 N，-3 N-3 N，但，但2.5Q2.5Q，-3I-3I。 10 二、集合的表示方法二、集合的表示方法 (1)(1)列举法列举法：按任意顺序逐一列举集合中的元素于花括号：按任意顺序

10、逐一列举集合中的元素于花括号 内，元素之间用逗号隔开。内，元素之间用逗号隔开。 例如：例如：A=2,a,b,9,B=4,5,6,7,8A=2,a,b,9,B=4,5,6,7,8 (2)(2)描述法描述法：给定一个条件：给定一个条件P(x)P(x)，当且仅当个体，当且仅当个体a a使使 P(a)P(a)成立时，成立时，aAaA。其一般形式为。其一般形式为A=aP(a)A=aP(a) 例如例如 上述集合上述集合B=aaNB=aaN且且4a84a8 又如又如 C=2C=2i iiZ,iZ,即即C=2C=20 0,2,21 1,2,22 2,2,23 3, , D=2xxZ D=2xxZ且且x50,x

11、50,即即D=0,2,4,6,D=0,2,4,6,98,100,98,100 11 三、集合的基数三、集合的基数 集合集合A A中不同元素的个数称为集合中不同元素的个数称为集合A A的的基数基数，记作，记作#A#A。 例如例如 上页中的集合，上页中的集合，#A=4#A=4，#B=5#B=5，#D=51#D=51，集合，集合C C 有无穷多个元素，因此有无穷多个元素，因此C C的基数是无穷大。的基数是无穷大。 若若#A#A是有限数，则称是有限数，则称A A为有限集，否则称为有限集，否则称A A为无限集。为无限集。 例如例如 N , Z , I , R 等均为无限集等均为无限集。 四、空集四、空集

12、 定义定义1-11-1 不含有任何元素的集合，称为空集空集，记作。 例如例如 A=x | xR 且 x2+8=0 = 12 练习练习1-11-1 1. 用列举法表示下列集合用列举法表示下列集合 （1）A=a|aPP且且a20a20 （2）B=a|a|4且且a为奇数为奇数 2. 用描述法表示下列集合用描述法表示下列集合 (1) A=0,2,4,200 (2) B=2,4,8,1024 2,3,5,7,11,13,17,19 - -3,- -1,1,3 2x|xZZ且且x100 x100 2n|nNN且且n10n10 13 1.2 1.2集合间的关系集合间的关系 集合的包含和相等是集合间的两个基本

13、关系。集合的包含和相等是集合间的两个基本关系。 例如例如 设设 A=a, b, c, d, B=a, e, x, y, z, C=a, x B A，A B。则 ，C A， BC 一、集合的包含一、集合的包含 定义定义1-21-2 设有集合设有集合A A、B B，如果，如果A A的每一个元素都是的每一个元素都是B B 的元素，则称的元素，则称A A是是B B的子集或的子集或B B是是A A的包含集，记的包含集，记 。 如果如果A A不是不是B B的子集，则记作的子集，则记作A BA B。 BA 14 集合的包含关系具有如下几条性质： 证明性质（1） （反证法）（反证法）假设 ， （1）对任意集合

14、）对任意集合A， ； A （2）对任意集合）对任意集合A， ；AA （3）对任意集合）对任意集合A、B、C，若，若 ， ，则，则 。 BACB CA 则至少有一个元素 但 ，这与空集的定义相矛盾，因此成立。Ax Ax 15 二、集合的相等二、集合的相等 例如例如 设设A=x | xN 且且 x能整除能整除24， B=1, 2, 3, 4, 6, 8, 12, 24 则则 A=B = 又例如又例如 （1）a, b, c b, c, a （2）a, b, c, c a, b, c （3）a, b, c a, b, c （4） = 定义定义1-31-3 设有集合设有集合A、B，若，若 且且 ，则称，

15、则称 集合集合A与与B相等，记作相等，记作A=B。 BA AB 16 例如例如 设设A=0A=0，11，B=0B=0，1 1，22，C=0C=0 则但 四、空集的唯一性四、空集的唯一性 定理定理1-11-1 空集是唯一的空集是唯一的 因为空集被包含于每一个集合中因为空集被包含于每一个集合中， 三、集合的真包含三、集合的真包含 定义定义1-41-4 设有集合设有集合A、B，若，若 , 且且ABB，则称，则称A A是是B B的真的真 子集，记作子集，记作 ，若，若A A不是不是B B的真子集，则记作的真子集，则记作 。 BA BA BA BA BC BBB 证明证明 假设有两个空集假设有两个空集

16、和和 ， 1 2 所以有所以有 ， ， 21 12 由定义由定义1-31-3， , , 故空集是唯一的。故空集是唯一的。 21 17 五、幂集五、幂集 定义定义1-51-5 设有集合设有集合A A，由，由A A的所有子集组成的集合，的所有子集组成的集合， 称为集合称为集合A A的幂集，记作的幂集，记作2 2A A 即 ASS A |2 例例1 1 设设A=aA=a 则则0 0个元素的子集：个元素的子集： 1个元素的子集：个元素的子集：a 因此 a A ,2 设设B=a,bB=a,b 则则0 0个元素的子集个元素的子集： 1个元素的子集：个元素的子集：a,b 2个元素的子集个元素的子集：a,b

17、因此 baba B ,2 设设C=a,b,cC=a,b,c 则则0 0个元素的子集：个元素的子集： ； 1个元素的子集：个元素的子集：a,b,c 2个元素的子集：个元素的子集：a,b,a,c,b,c 3个元素的子集：个元素的子集：a,b,c 因此 cbacbcabacba C ,2 18 定理定理1-21-2 设设A A是有限集，则是有限集，则#(2#(2A A)= 2)= 2#A #A n n n nnnn A CCCCC 1210 )2(# 在二项式定理在二项式定理 nn n nn n n n n n n yCxyCyxCxCyx 11110 )( 中，令中，令 x=y=1, 便有便有 n

18、 n n nnnn n CCCCC 1210 2 因此因此 #(2 2A A)= 2 2n n 即 即 #(2 2A A) = 2 2#A #A : 0 n C 1 n C :a1,:a2 ,an 2 n C :a1,a2,a1,a3 n n C :a1,a2 , , an 证明证明 设设A= A= a1,a2 , , an, ,从从n n个元素中选取个元素中选取m m个元素的方个元素的方 法有法有 种，所以种，所以A A的子集个数为的子集个数为 m n C 19 例例2 2 设设 , 求求2A和和2B A aaB, 解解 对于集合对于集合A，它只有一个子集，它只有一个子集 ， 即 A 2 对

19、于集合对于集合B，有，有 1个元素的子集：个元素的子集： ，a，a 2个元素的子集：个元素的子集： , , a, a, aa, 3个元素的子集：个元素的子集： aa, 0个元素的子集：个元素的子集： 因此因此 ,2 B aaaa , ,aaaa 20 答案：答案： ABD 2 2 设设 , 试判断下列各式是否正试判断下列各式是否正 确，并将正确的题号填入括号内。确，并将正确的题号填入括号内。 A. B. C. D. S SS S , 4, 3,aS 答案：答案：A BC A. B. C. D. aa 练习练习1-21-2 1 试判断下列各式是否正确，并将正确的题试判断下列各式是否正确，并将正确

20、的题 号填入括号内。号填入括号内。 aaa, aa aaa, 21 3 设设 , , ，判断下列论断，判断下列论断 是否正确，并将是否正确，并将“Y”或或“N”填入相应论断填入相应论断 后面的括号中。后面的括号中。 A )2( 2 A B (1) (2) (3) (4) B B B B B B B, B, ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Y Y Y Y Y Y N N 2 A C ,2 C B 令令 则则 22 1.3 1.3集合的运算和运算定律集合的运算和运算定律 二、文氏图二、文氏图 定义定义1-61-6 如果在某个问题中，所讨论的一切集 合均是某个集合的子

21、集，则称这个集合是该问题 的全集合。记作U（或E）。 一、全集合一、全集合 例如例如 UA BA A B 23 三、集合的运算三、集合的运算 定义定义1-71-7 设有集合设有集合A、B，属于，属于A或属于或属于B的所有元的所有元 素组成的集合称为素组成的集合称为A与与B的并集，记作的并集，记作 。即。即 BuAuuBA或| BA 例如例如 设设A=a,b,c, B=c,d,f, C=b,e 则 fdcbaBA, ecbaCA, fedcbCB, 由定义由定义1-7知知， BABBAA, BA A B 24 定义定义1-81-8 设有集合设有集合A、B，属于，属于A同时又属于同时又属于B 的所

22、有元素组成的集合称为的所有元素组成的集合称为A与与B的交集，记的交集，记 作作 。即。即 BA BuAuuBA且| 例如例如 设设A=a,b,c,d, B=d,f,a, C=e,f,g 则 adBA, 由定义由定义1-8可知可知， ABABBA CA fCB BA AB 25 定义定义1-91-9 设有集合设有集合A、B，所有属于，所有属于B而不属于而不属于A 的元素组成的集合，称为的元素组成的集合，称为A相对于相对于B的补集，记作的补集，记作 B-A。即。即 AuBuuAB但| 例如例如 设设A=a,b,c,d, B=d,f,a, C=e,f,g 则则B-A= f , C-A= e ,f ,

23、 g =C AB B A 32页页 26 定义定义1-101-10 集合集合A相对于全集合相对于全集合U的补集称为的补集称为A的的 绝对补集，简称为绝对补集，简称为A的补集，记作的补集，记作 。即。即 A AuuAuUuuAUA|但 例如例如 设设U=1，2，3，4，10，A=2，4，6，8，10 则 9 , 7 , 5 , 3 , 1AUA 又例如又例如 设设U=I（I是整数集），是整数集）， 0,|iIiiA且 则0|iIiiAUA且 27 四、集合运算的定律四、集合运算的定律 对于全集合对于全集合U的任意子集的任意子集A、B、C，有：，有： 交换律交换律 ABBAABBA 结合律结合律

24、CBACBA)()( CBACBA)()( 分配律分配律)()()(CABACBA )()()(CABACBA 同一律同一律AAAUA 28 互补律互补律UAA AA 对合律对合律 AA ) ( 等幂律等幂律AAAAAA 零一律零一律 UUAA 吸收律吸收律ABAA)(ABAA)( 德德摩根律摩根律 BABA)(BABA)( 29 （1）根据定义进行证明）根据定义进行证明 若要证明集合若要证明集合S=H，根据集合相等关系的定义，根据集合相等关系的定义， 我们需证明我们需证明 且且HS SH 例例 1 1 证明证明 BABA)( 证明证明 若若 , 则则 ，)(BAuBAu 因此因此 或者或者

25、AuBu 于是于是 或者或者AuBu 从而从而 ，则，则BAuBABA)( 反之反之 若若 ， 故故 或者或者 。BAuAuBu 因此，因此， 或者或者 ,AuBu于是于是 ， BAu 从而从而 ，故有，故有 。)(BAu)(BABA 由上证得，由上证得， 。 BABA)( 30 例例 2 2 证明证明BABA 证明证明 若若 则则 且且 ，BAuAuBu 即即 且且 ，AuBu 因因 此此 ， BAu 故故 。 BABA 反之反之 若若 ，BAu 则则 且且 ，AuBu即即 且且 ，AuBu 因此因此 。BAu 故故 。BABA 由上证得，由上证得， BABA 31 （2）利用已有的集合恒等

26、式证明新的恒等式）利用已有的集合恒等式证明新的恒等式 例如例如 假设交换律、分配律、同一律和零一律都成立，假设交换律、分配律、同一律和零一律都成立， 则可以证明吸收律则可以证明吸收律 也成立。也成立。 ABAA)( 证明证明 )(BAA )()(BAA （由同一律）（由同一律） )(BA（由分配律）由分配律） )(BA （由交换律）（由交换律） A （由零一律）（由零一律） A （由同一律）（由同一律） 又例如又例如 证明等幂律证明等幂律 AAA 证明证明 = =AAA)(AAAA (3)(3)利用下一节介绍的集合成员表证明集合恒等式利用下一节介绍的集合成员表证明集合恒等式 32 D 若若 ，

27、则，则 A=B 练习练习1-31-3 1 设设A、B、C是任意集合，判断下述论断是否是任意集合，判断下述论断是否 正确，并将正确的题号填入括号内。正确，并将正确的题号填入括号内。 A 若若 ，则，则 B=CCABA B 若若 ，则，则 B=CCABA C 若若A-B=A-C，则，则 B=C BA ( ) D 反例反例 设设A= a , b , c , B= b , d , C= c , d 则则 但但 ,dcbaCABA CB 23页页 33 CBA)( 2 设设U=1，2，3，4，5，A=2，4， B=4，3，5，C=2，5，3，确定下列，确定下列 集合的元素，将其填入相应的花括号内。集合的

28、元素，将其填入相应的花括号内。 (1) (2) (3) (4) (5 BA )(CBA CA BCA)( 2 1, 4 2, 3, 4, 5 4 34 3 设设U表示刘平拥有的所有书的集合，其中表示刘平拥有的所有书的集合，其中A是离散数学是离散数学 参考书的集合，参考书的集合，B是操作系统参考书的集合，是操作系统参考书的集合，C是今年出版是今年出版 的新书的集合，的新书的集合，D是从图书馆借来的书的集合。现知道如下是从图书馆借来的书的集合。现知道如下 情形：情形： （1）所有离散数学参考书都是今年出版的新书。（）所有离散数学参考书都是今年出版的新书。（ ） （2）所有操作系统参考书都是从图书馆

29、借来的。（）所有操作系统参考书都是从图书馆借来的。（ ） （3）今年出版的新书不是从图书馆借来的。（）今年出版的新书不是从图书馆借来的。（ ） （4）没有一本操作系统的参考书是今年出版的。（）没有一本操作系统的参考书是今年出版的。（ ） 3 1 5 7 试用集合的方法分别表示上述四种情形，可供选择的答案试用集合的方法分别表示上述四种情形，可供选择的答案 如下，请从下述答案中挑选出相应表达式的编号填入每一如下，请从下述答案中挑选出相应表达式的编号填入每一 种情形后面的括号中。种情形后面的括号中。 1. 2. 3. 4. 5. 6. 7. DB BC CA DA DC CB CB 35 4 判断下

30、列论断是否正确，对正确的论断在相应题后的括判断下列论断是否正确，对正确的论断在相应题后的括 号中标入号中标入“Y”，对错误的论断在相应题后的括号中标入，对错误的论断在相应题后的括号中标入 “N”。 1） 若若 ，则，则 （ ） 2） 若若 ，则，则 （ ） 3） 若若 ，则，则 （ ） 4） 若若 ，则，则 （ ） 5） 若若 ，则，则 ( ) 6） 若若 ，则，则 ( ) 7） 若若 ，则，则 ( ) 8） 若若 ，则，则 ( ) AaBAa AaBAa BAaBa BAaBa BA BBA BA ABA AaBAa AaBAa Y Y Y Y N N N N 36 1.4 1.4集合成员表

31、集合成员表 一、并、交和补集的成员表一、并、交和补集的成员表 根据集合的并和交运算的定义，全集合根据集合的并和交运算的定义，全集合U中的元素中的元素u可分为可分为 如下四种情形：如下四种情形： （ 1） ， （ 2） ， （ 3） ， （ 4） ， AuBuBAuBAu Au Bu BAuBAu AuBuBAuBAu AuBuBAuBAu A B 0 0 0 1 1 0 1 1 BABA 0 0 1 0 1 0 1 1 37 设设A是全集合是全集合U的子集，根据补集的定义，全集合的子集，根据补集的定义，全集合 U中的元素可分为两种情形，中的元素可分为两种情形， （1）若）若 ，则，则 （2）若

32、）若 ，则，则 Au Au Au Au 的成员表的成员表 A A 0 1 A 1 0 38 二、由集合二、由集合A A1 1、A A2 2、A Ar r所产生的集合所产生的集合 的成员表。的成员表。 设设A1、A2、Ar是全集合是全集合U的子集，对这些集合以及的子集，对这些集合以及 和和U有限次地施加补、并、交运算，可以产生出一些有限次地施加补、并、交运算，可以产生出一些 新的集合，这样产生的集合称为是由新的集合，这样产生的集合称为是由A1、A2、Ar所所 产生的集合。产生的集合。 例例 如如 S)()(CBCBA BBAT)( 39 例例 1 构造构造 T= 的成员表的成员表 BBA)( A

33、 B 0 0 0 1 1 0 1 1 BA B BBA)( 0 1 1 1 1 0 1 0 0 0 1 0 40 例例 2 构造构造 S 的成员表的成员表 )()(CBCBA A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 B CB C CB)()(CBCB S 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 0 41 三、利用集合成员表证明集合恒等式三、利用集合成员表证明集合恒等式 例例 设设A

34、、B、C是任意集合，试问等式是任意集合，试问等式 S=TS=T是否成立？是否成立？ 解解 令令S= T= )()(CABA )()(BACA 分别构造分别构造S和和T的成员表如下：的成员表如下： A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A BACA S BA CA T 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 42 1.5 1.5 集合的分划与覆盖

35、集合的分划与覆盖 一、集合的分划一、集合的分划 定义定义1-111-11 设有非空集合设有非空集合A，H=A1、A2、Am， 其中其中 ，且，且 （i=1，2，m），若），若 AAi i A （1） ，当，当ij时时 ( 2 ) ji AA AAi m i 1 例例 1 1 设设A=1，2，3，4 则则 H1=1，2，3，4 H2=2，3，1，4 H3=1，2，3，4 。 都是都是A的分划的分划 则称则称H是集合是集合A的一个分划，每一个的一个分划，每一个 称为这个分划的一个分块。称为这个分划的一个分块。 i A 43 例例 2 2 设设A=2A=2，3 3，4 4，8 8，9 9，1010，

36、15 15 定义定义A A的如下子集：的如下子集： 整除能被且2| 2 xAxxA 整除能被且3| 3 xAxxA 整除能被且5| 5 xAxxA 试问试问 是否是否A的一个分划。的一个分划。 , 532 AAA 解解根据题意根据题意 2，4，8，10 2 A 3，9，15 3 A 10，15 5 A 不是不是A的分划，的分划，, 532 AAA , 32 AA 可成为可成为A的一个分划。的一个分划。 44 二、集合的覆盖二、集合的覆盖 定义定义1-12 设有非空集合设有非空集合A， ,其中其中 且且 （i=1，2，m），若），若 ， 则称则称S是集合是集合A的一个覆盖。的一个覆盖。 m AA

37、AS, 21 AAi i AAAi m i 1 例如例如 例例2中中 是是A的分划，也是的分划，也是A的覆盖。的覆盖。 是是A的覆盖，但不是的覆盖，但不是A的分划。的分划。 , 32 AA , 532 AAA 45 练习练习1-51-5 1 设设A=a，b，c，d，e，f，指出下列哪些是，指出下列哪些是A的的 分划（在相应括号内填入分划（在相应括号内填入“1”），哪些是），哪些是A的覆盖的覆盖 （在相应括号内填入（在相应括号内填入“2”），哪些既不是分划，也），哪些既不是分划，也 不是覆盖（在相应括号内填入不是覆盖（在相应括号内填入“0”） H1= a，b ，c，d ，a，e，f （ ） H2

38、= c，e ，c，d，f ，b （ ） H3= a，b，c，d ，e，f （ ） H4= a，c，e ， b，c （ ） 2 0 1,2 0 46 例题一例题一 1 给定正整数集给定正整数集N的下列子集的下列子集 求集合求集合 8 , 7 , 2 , 1A 50| 2 iiB 303|iiiC整除，可被 60 ,2|kZkiiD k DBA)( 解解 B = 1 , 2 , 3 , 4 , 5 , 6 , 7 DBA)(= 1 , 2 , 3 , 4 , 5 , 6 , 8 , 16 , 32 , 64 C = 3 , 6 , 9 , 12 , 15 , 18 , 21 , 24 , 27 ,

39、 30 D = 1 , 2 , 4 , 8 , 16 , 32 , 64 47 2 设设A、B、C和和D是集合，下述论断哪是集合，下述论断哪 些正确？哪些错误？对正确的论断给出些正确？哪些错误？对正确的论断给出 证明，对错误的论断举出反例。证明，对错误的论断举出反例。 （1）若 ， ，则 DC BA )()(DBCA 解解 （1） 正确。 证明如下： 设设 CuAuCAu或则, DuBu或 BA DC 因为因为 所以所以 DBu因此因此 48 （2）若）若 ， ，则，则BA DC )()(DBCA 设设 ， 则则CAu CuAu且 正确。证明如下：正确。证明如下：解解 BA DC 因为因为 D

40、uBu且所以所以 DBu DBCA 因此因此 49 （3）若）若 ， ，则，则BA DC )()(DBCA 解解 错误错误 DBCA DBCA 但但 BA DC 则则 例如，设例如，设A=1，2， C=3，4， B=D=1，2，3，4 50 （4）若）若 ， ，则，则 BA DC )()(DBCA 解解 错误错误 例如，设例如，设A=2，3， B=1，2，3， C=2，3，D=2，3，4 则则 BA DC 但但 DBCADBCA 51 3 n个元素的集合个元素的集合A，有多少种不同的方法，有多少种不同的方法 分划成为两块？分划成为两块？ 解解 A有有 个不同的子集，且这个不同的子集，且这 个不

41、同个不同 的子集中，两两互补，除的子集中，两两互补，除 和和U互补，但互补，但 不能构成不能构成A的分划外，其余的每对集合均的分划外，其余的每对集合均 构成将构成将A分成两块的一个分划，因此分成两块的一个分划，因此A 有有 种方法分成两块。种方法分成两块。 )22( 2 1 n n 2 n 2 52 4 设某校有运动员总数为设某校有运动员总数为70人，其中足球队员人，其中足球队员38 人，篮球队员人，篮球队员35人，排球队员人，排球队员32人，其中有人，其中有8人同人同 时参加三个队，试求仅同时参加两个队的队员人时参加三个队，试求仅同时参加两个队的队员人 数是几人？数是几人？ A C B X

42、Y Z 8 则则 # 70)(CBA 又又 82)(#)(#zyxCBACBA 在文氏图中用在文氏图中用A、B、C分别分别 表示足球队员、篮球队员和表示足球队员、篮球队员和 排球队员的集合排球队员的集合 解解 答案：答案：仅同时参加两个队的队员人数是仅同时参加两个队的队员人数是19人人 53 第二章 关 系 本章讨论的关系（主要是二元关系），它仍然是一种 集合，但它是比第一章更为复杂的集合。它的元素是有序 二元组的形式，这些有序二元组中的两个元素来自于两个 不同或者相同的集合。因此，关系是建立在其它集合基础 之上的集合。关系中的有序二元组反映了不同集合中元素 与元素之间的关系，或者同一集合中元

43、素之间的关系。本 章讨论这些关系的表示方法、关系的运算以及关系的性质， 最后讨论集合A上几类特殊的关系。 主要内容如下： 2.1 笛卡尔积与关系 2.5 等价关系 2.2 关系的表示 2.6 相容关系 2.3 关系的复合运算 2.7 偏序关系 2.4 关系的性质与闭包 54 有序n元组与n个元素的集合，是不相同的。 例如 但 ,cdbacdabdcba ),(),(),(cdbacdabdcba 2.1 笛卡尔积与关系 一、有序n元组与笛卡尔积 1. 有序n元组 定义2-1 由n个具有给定次序的个体 组成的 序列称为有序n元组，记作（ ）。 n aaa, 21 n aaa, 21 55 例如

44、4,4,3,2=4,3,2 但 (4,4,3,2)(4,3,2) 定义2-2 设 和 是两 个有序n元组，若 ,则称这两 个有序n元组相等，并记作 ),( 21n aaa),( 21n bbb nn bababa, 2211 ),(),( 2121nn bbbaaa 当n=2时，有序二元组(a,b)又称为序偶。 56 2. 笛卡尔积 (1)笛卡尔积的定义 定义2-3 设A,B为任意集合， A 和 B 的笛卡尔积用 表示， 定义为 BA ,| ),(BbAabaBA 例1 设 则 但 ,1 , 0cbaBA ), 1 (), 1 (), 1 (), 0(), 0(), 0(cbacbaBA )1

45、 ,(),1 ,(),1 ,(),0 ,(),0 ,(),0 ,(cbacbaAB 当 或者 时， ，即 。 AB BAAB ABBA 笛卡尔积 我们常记作 AA 2 A ,| ),(AaAaaaA jiji 2 例2 设 则 1 ,0A ),(),(),(),(11011000 2 AAA 57 （2）笛卡尔积的基数 当 A 和 B 均 是 有 限 集 时 ， 必 为 有 限 集 ， 而 且 当其中有一个是无限集时，必为无限集。 （3）与笛卡尔积有关的一些恒等式 设A、B、C是任意的集合，则有 1） 2） 3） 4） )()()(CABACBA )()()(ACABACB )()()(CAB

46、ACBA )()()(ACABACB BA BABA#)(# 58 以第一个等式 为例，给出其证明。 )()()(CABACBA 证明 设 ， )(),(CBAyx 则 ，且 , Ax CBy 因此 或 。 ),(ByAx),(CyAx 于是 或 ， BAyx),(CAyx),( 即 ， )()(),(CABAyx 故 。 )()()(CABACBA 即 ，且（ 或 )，AxCy By 59 反之，设 ， ) ()(),(CABAyx 则 或 ， BAyx),(CAyx),( 于是( 且 ）或( 且 ）， AxByAxCy 即 且（ 或 ）, Ax ByCy 即 且 ，因此 , AxCBy)(

47、),(CBAyx 故 。 ) ()()(CBACABA 由上证得 )()()(CABACBA 60 BA BA 二、关系 1. 关系的定义 定义2-4 笛卡尔积 的任意一个子集 称为 是由A到B的一个二元关系，当 时，称 是A上的二元关系。 61 例3 设A=a,b，B=2,5,8 则 )8 ,(),5 ,(),2 ,(),8 ,(),5 ,(),2 ,(bbbaaaBA 令 )2 ,(),8 ,(),2 ,( 1 baa )5 ,(),2 ,(),5 ,( 2 bba )2 ,( 3 a 因为 ， ， 。BA 1 BA 2 BA 3 所以， , 和 均是由A到B的关系。 1 2 3 又 ),

48、 8(), 5(), 2(), 8(), 5(), 2(bbbaaaAB 令 ), 2(), 2( 4 ba ), 8(), 8(), 5( 5 baa 因为 , 。AB 4 AB 5 所以 和 均是由 B 到 A 的关系。 4 5 62 对于 , )8 , 8 (),5 , 8 (),2 , 8 (),8 , 5 (),5 , 5 (),2 , 5 (),8 , 2 (),5 , 2 (),2 , 2(BB ,852B 令 ),(),(),(282522 6 )5 , 2(),8 , 2(),2 , 5(),5 , 8( 7 因为 ， . BB 6 BB 7 5 1 a 所以 和 均是集合B

49、上的关系。 若 ，则称a与b有关系 ，又记作 。 若 ，则称a与b没有关系 ，又记作 。 例如 在例3中 ， ，但 6 7 ),(baba ),(ba ba 8 1 a2 1 a 63 全域关系（或普遍关系） 因为 , 。 所以 是一个由 到 的关系。 是 上的一个关系。 常将 记作 BABAAAAA AA ,| ),(AaaaaU jijiA AAA BAAB 2. 几种特殊的关系 空关系 对任意集合 . 所以 是由 到 的关系， 也是 上的关系，称为空关系。 AABABA, ABA 64 恒等关系 定义集合 上的恒等关系 | ),(AaaaI A A 例4 设 ,cbaA 则下面集合 AA

50、U A ),(),(),(cabaaa),(),(),(cbbbab 是 上的恒等关系。 ),(),(),(ccbbaaI A A ),(),(),(ccbcac 是 上的普遍关系。 A 65 3. 关系的定义域和值域 定义2-5 设 是由 到 的一个关系， 的定义域记 作 ， 的值域记作 ，分别定义为： AB R D ,|baBbAaaD 使得且存在 ,|baAaBbbR 使得且存在 显然有 BRAD , 例5 设 。 9 , 8 , 7 , 6 , 2,5 , 3 , 2BA 由 到 的关系 定义为：当且仅当a整除b时， 有 。 AB ba 于是 )9 , 3(),6 , 3(),8 ,