《离散数学集合与关系集合精选文档.ppt》由会员分享，可在线阅读，更多相关《离散数学集合与关系集合精选文档.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学集合与关系集合本讲稿第一页，共四十八页第三章第三章 集合与关系集合与关系集合集合 这里采用朴素集合论的方法，介绍有关集合的一些基本知识，这里采用朴素集合论的方法，介绍有关集合的一些基本知识，内容显得较为直观，学起来易于接受。但集合及其相关的概念是本内容显得较为直观，学起来易于接受。但集合及其相关的概念是本门课程后面各章内容的基础，读者务必熟练的掌握。门课程后面各章内容的基础，读者务必熟练的掌握。主要内容如下：主要内容如下：集合及其表示方法集合及其表示方法 集合间的关系集合间的关系 集合的运算和运算定律集合的运算和运算定律集合成员表集合成员表 集合的分划与覆盖集合的分划与覆盖本讲稿第二页
2、，共四十八页又又例例如如 所有的正整数组成一个集合，每一个正整数均是这个集 合的元素。例如例如 全体中国人可组成一个集合，每一个中国人均是这个集合的 元素第三章第三章 集合与关系集合与关系 集合及其表示方法集合及其表示方法一、集合和元素一、集合和元素v 把一些确定的、彼此不同的事物作为一个整体来 看待时，这个整体便称为是一个集合集合。v 组成集合的那些个体称为集合的元素元素。通常用大写英文字母来标记集合，用小写英文字母标记组成集合的个体若个体a是集合A的元素，则记作“aA”若a不是集合A的元素，则记作“a A”本讲稿第三页，共四十八页几个常见的集合的表示符号：N：所有正整数的集合。：所有正整数
3、的集合。Q Q：所有有理数的集合。：所有有理数的集合。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。本讲稿第四页，共四十八页二、集合的表示方法二、集合的表示方法(1)(1)列列举举法法：按按任任意意顺
4、顺序序逐逐一一列列举举集集合合中中的的元元素素于于花花括括号号内内，元素之间用逗号隔开。元素之间用逗号隔开。例如：例如：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=2 C=2i iiZ,iZ,即即C=2C=20 0,2,21 1,2,22 2,2,23 3,D=2xxZ D=2xxZ
5、且且x50,x50,即即D=0,2,4,6,D=0,2,4,6,98,100,98,100本讲稿第五页，共四十八页三、集合的基数三、集合的基数集合集合A A中不同元素的个数称为集合中不同元素的个数称为集合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 等均为无限集等均为无
6、限集。四、空集四、空集定义定义3-13-1 不含有任何元素的集合，称为空集空集，记作。例如例如 A=x|xR且x2+8=0=本讲稿第六页，共四十八页练习练习3-13-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 x1002n|nNN且且n10n10 本讲稿第七页，共四十八页集合间的关系集合间的关系集合的包含和相等是集合间的两个基
7、本关系。集合的包含和相等是集合间的两个基本关系。例如例如 设设 A=a,b,c,d,B=a,e,x,y,z,C=a,x BA，AB。则，CA，一、集合的包含一、集合的包含定义定义3-23-2 设有集合设有集合A A、B B，如果，如果A A的每一个元素都是的每一个元素都是B B的元素，的元素，则称则称A A是是B B的子集或的子集或B B是是A A的包含集，记的包含集，记 。如果。如果A A不是不是B B的的子集，则记作子集，则记作A BA B。本讲稿第八页，共四十八页集合的包含关系具有如下几条性质：证明性质（1）（反证法）（反证法）假设 A，（1）对任意集合）对任意集合A，；（2）对任意集合
8、）对任意集合A，；（3）对任意集合）对任意集合A、B、C，若，若 ，则，则 。则至少有一个元素 ，但 ，这与空集的定义相矛盾，因此成立。本讲稿第九页，共四十八页二、集合的相等二、集合的相等例如例如 设设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）=定义定义3-33-3设有集合设有集合A、B，若，若 且且 ，则称集合则称集合A与与B相等，记作相等，记作A=B。本讲稿第十页，共四十八页例如例如 设设A=0A=0，11，B=0B=0，1 1，22
9、，C=0C=0则但四、空集的唯一性四、空集的唯一性定理定理3-13-1 空集是唯一的空集是唯一的 因为空集被包含于每一个集合中因为空集被包含于每一个集合中，三、集合的真包含三、集合的真包含定义定义3-43-4 设有集合设有集合A、B，若，若 ,且且ABB，则称，则称A A是是B B的真的真子集，记作子集，记作 ，若，若A A不是不是B B的真子集，则记作的真子集，则记作 。证明证明 假设有两个空集假设有两个空集 和和 ，所以有所以有 ，由定义由定义3-33-3，,故空集是唯一的。故空集是唯一的。本讲稿第十一页，共四十八页五、幂集五、幂集定定义义3-53-5 设设有有集集合合A A，由由A A的
10、的所所有有子子集集组组成成的的集集合合，称为集合称为集合A A的幂集，记作的幂集，记作2 2A A 即 例例1 1 设设A=aA=a 则则0 0个元素的子集：个元素的子集：1个元素的子集：个元素的子集：a因此设设B=a,bB=a,b 则则0 0个元素的子集个元素的子集：1个元素的子集：个元素的子集：a,b 2个元素的子集个元素的子集：a,b因此设设C=a,b,cC=a,b,c 则则0 0个元素的子集：个元素的子集：；1个元素的子集：个元素的子集：a,b,c2个元素的子集：个元素的子集：a,b,a,c,b,c3个元素的子集：个元素的子集：a,b,c 因此本讲稿第十二页，共四十八页定理定理3-23
11、-2 设设A A是有限集，则是有限集，则#(2#(2A A)=2)=2#A#A 在二项式定理在二项式定理 中，令中，令 x=y=1,便有便有 因此因此#(2 2A A)=2 2n n 即即#(2 2A A)=2 2#A#A:a1,:a2,an:a1,a2,a1,a3:a1,a2,an证证明明 设设A=A=a1,a2,an,从从n n个个元元素素中中选选取取m m个个元元素素的的方法有方法有 种，所以种，所以A A的子集个数为的子集个数为本讲稿第十三页，共四十八页例例2 2 设设 ,求求2A和和2B 解解对于集合对于集合A，它只有一个子集，它只有一个子集 ，即对于集合对于集合B，有，有 1个元素
12、的子集：个元素的子集：，a，a2个元素的子集：个元素的子集：,3个元素的子集：个元素的子集：0个元素的子集：个元素的子集：因此因此 本讲稿第十四页，共四十八页答案：答案：ABD答案：答案：ABC练习练习3-23-2 A.B.C.D.1 试判断下列各式是否正确，并将正确的题试判断下列各式是否正确，并将正确的题号填入括号内。号填入括号内。2 2 设设 ,试判断下列各式是否正试判断下列各式是否正确，并将正确的题号填入括号内。确，并将正确的题号填入括号内。A.B.C.D.本讲稿第十五页，共四十八页3 设设 ,，判，判断下列论断是否正确，并将断下列论断是否正确，并将“Y”或或“N”填入相应论断后面的括号
13、中。填入相应论断后面的括号中。(1)(2)(3)(4)()()()()()()()()YYYYYYNN令令则则本讲稿第十六页，共四十八页 集合的运算和运算定律集合的运算和运算定律二、文氏图二、文氏图定义定义3-63-6如果在某个问题中，所讨论的一切集合均是某个集合的子集，则称这个集合是该问题的全集合。记作U（或E）。一、全集合一、全集合例如例如 UAAB本讲稿第十七页，共四十八页三、集合的运算三、集合的运算1.并运算并运算 定定义义3-73-7设设有有集集合合A、B，属属于于A或或属属于于B的的所所有有元元素素组组成的集合称为成的集合称为A与与B的并集，记作的并集，记作 。即。即例如例如 设设
14、A=a,b,c,B=c,d,f,C=b,e则由定义由定义1-7知知，AB本讲稿第十八页，共四十八页2.交运算交运算 定定义义3-83-8 设设有有集集合合A、B，属属于于A同同时时又又属属于于B的的所所有有元素组成的集合称为元素组成的集合称为A与与B的交集，记作的交集，记作 。即。即例如例如 设设A=a,b,c,d,B=d,f,a,C=e,f,g则由定义由定义1-8可知可知，AB本讲稿第十九页，共四十八页3.相对补运算相对补运算 定定义义3-93-9设设有有集集合合A、B，所所有有属属于于B而而不不属属于于A的的元元素素组组成成的的集集合合，称称为为A相相对对于于B的的补补集集，记记作作B-A
15、。即即例如例如 设设A=a,b,c,d,B=d,f,a,C=e,f,g 则则B-A=f,C-A=e,f,g=C BA32页页本讲稿第二十页，共四十八页2.绝对补运算绝对补运算 定义定义3-103-10 集合集合A相对于全集合相对于全集合U的补集称为的补集称为A的绝对补的绝对补集，简称为集，简称为A的补集，记作的补集，记作 。即。即A AAA本讲稿第二十一页，共四十八页例如例如 设设U=1，2，3，4，10，A=2，4，6，8，10 则则又例如又例如设设U=I（I是整数集），是整数集），则则本讲稿第二十二页，共四十八页四、集合运算的定律四、集合运算的定律1.集合运算的十条定律集合运算的十条定律
16、对于全集合对于全集合U的任意子集的任意子集A、B、C，有：，有：交换律交换律结合律结合律分配律分配律同一律同一律本讲稿第二十三页，共四十八页互补律互补律对合律对合律等幂律等幂律零一律零一律吸收律吸收律德德摩根律摩根律本讲稿第二十四页，共四十八页1.集合恒等式的几种证明方法集合恒等式的几种证明方法（1）根据定义进行证明）根据定义进行证明若要证明集合若要证明集合S=H，根据集合相等关系的定义，我，根据集合相等关系的定义，我们需证明们需证明 且且例例 1 1 证明证明证明证明 若若 ,则则 ，因此因此 或者或者于是于是 或者或者从而从而 ，则，则反之反之 若若 ，故故 或者或者 。因此，因此，或者或
17、者 ,于是于是 ，从而从而 ，故有，故有 。由上证得，由上证得，。本讲稿第二十五页，共四十八页例例 2 2 证明证明证明证明 若若 则则 且且 ，即即 且且 ，因此因此 ，故故 。反之反之 若若 ，则则 且且 ，即即 且且 ，因此因此 。故故 。由上证得，由上证得，本讲稿第二十六页，共四十八页（2）利用已有的集合恒等式证明新的恒等式）利用已有的集合恒等式证明新的恒等式例如例如 假设交换律、分配律、同一律和零一律都成立，假设交换律、分配律、同一律和零一律都成立，则可以证明吸收律则可以证明吸收律 也成立。也成立。证明证明（由同一律）（由同一律）（由分配律）由分配律）（由交换律）（由交换律）（由零一
18、律）（由零一律）（由同一律）（由同一律）又例如又例如 证明等幂律证明等幂律 证明证明 =A(3)(3)利用下一节介绍的集合成员表证明集合恒等式利用下一节介绍的集合成员表证明集合恒等式本讲稿第二十七页，共四十八页D 若若 ，则，则 A=B 练习练习3-33-3 1 设设A、B、C是任意集合，判断下述论断是否正确，是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。并将正确的题号填入括号内。A 若若 ，则，则 B=CB 若若 ，则，则 B=C C 若若A-B=A-C，则，则 B=C()D 反例反例 设设A=a,b,c,B=b,d,C=c,d 则则 但但23页页本讲稿第二十八页，共四十八页2
19、 设设U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，确定下列集合的元，确定下列集合的元素，将其填入相应的花括号内。素，将其填入相应的花括号内。(1)(2)(3)(4)(521,42,3,4,54本讲稿第二十九页，共四十八页3 设设U表表示示刘刘平平拥拥有有的的所所有有书书的的集集合合，其其中中A是是离离散散数数学学参参考考书书的的集集合合，B是是操操作作系系统统参参考考书书的的集集合合，C是是今今年年出出版版的的新新书书的的集集合合，D是从图书馆借来的书的集合。现知道如下情形：是从图书馆借来的书的集合。现知道如下情形：（1）所有离散数学参考书都是今年出版的新书。（）所有离
20、散数学参考书都是今年出版的新书。（）（2）所有操作系统参考书都是从图书馆借来的。（）所有操作系统参考书都是从图书馆借来的。（）（3）今年出版的新书不是从图书馆借来的。（）今年出版的新书不是从图书馆借来的。（）（4）没有一本操作系统的参考书是今年出版的。（）没有一本操作系统的参考书是今年出版的。（）3157试试用用集集合合的的方方法法分分别别表表示示上上述述四四种种情情形形，可可供供选选择择的的答答案案如如下下，请请从从下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。1.2.3.4.5.6.7.本讲稿第三十页，共四十八页4
21、判判断断下下列列论论断断是是否否正正确确，对对正正确确的的论论断断在在相相应应题题后后的的括括号号中中标入标入“Y”，对错误的论断在相应题后的括号中标入，对错误的论断在相应题后的括号中标入“N”。1）若若 ，则，则 （）2）若若 ，则，则 （）3）若若 ，则，则 （）4）若若 ，则，则 （）5）若若 ，则，则 ()6）若若 ，则，则 ()7）若若 ，则，则 ()8）若若 ，则，则 ()YYYYNNNN本讲稿第三十一页，共四十八页集合成员表集合成员表一、并、交和补集的成员表一、并、交和补集的成员表根根据据集集合合的的并并和和交交运运算算的的定定义义，全全集集合合U中中的的元元素素u可可分分为为如
22、如下下四种情形：四种情形：（1），（2），（3），（4），A B 0 00 11 01 1 0 0 1 0 1 0 1 1本讲稿第三十二页，共四十八页设设A是是全全集集合合U的的子子集集，根根据据补补集集的的定定义义，全全集集合合U中中的的元元素可分为两种情形，素可分为两种情形，（1）若）若 ，则，则（2）若）若 ，则，则的成员表的成员表 A0110本讲稿第三十三页，共四十八页二、由集合二、由集合A A1 1、A A2 2、A Ar r所产生的集合所产生的集合的成员表。的成员表。设设A1、A2、Ar是是全全集集合合U的的子子集集，对对这这些些集集合合以以及及和和U有有限限次次地地施施加加补补、
23、并并、交交运运算算，可可以以产产生生出出一一些些新新的的集集合合，这这样样产产生生的的集集合合称称为为是是由由A1、A2、Ar所所产产生的集合。生的集合。例例 如如 S本讲稿第三十四页，共四十八页例例 1 构造构造 T=的成员表的成员表 A B0 00 11 01 1011110100010本讲稿第三十五页，共四十八页例例 2 构造构造 S 的成员表的成员表 A B C0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1S110011000100010010101010001000100110011000000110本讲稿第三十六页，共四十八页三、利用集合成员表证明
24、集合恒等式三、利用集合成员表证明集合恒等式例例 设设A、B、C是任意集合，试问等式是任意集合，试问等式 S=T S=T是否成立？是否成立？A B C 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1ST11110000001111111111010100110101001100000000010100110101 其中其中 S=,T=分别构造分别构造S和和T的成员表如下：的成员表如下：解解本讲稿第三十七页，共四十八页集合的分划与覆盖集合的分划与覆盖一、集合的分划一、集合的分划定义定义3-113-11 设有非空集合设有非空集合A，H=A1、A2、Am，其中其中 ，
25、且，且 （i=1，2，m），若），若（1），当，当ij时时 (2)例例 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的一个分划，每一个的一个分划，每一个 称为这个分划的一个分块。称为这个分划的一个分块。本讲稿第三十八页，共四十八页例例 2 2 设设A=2A=2，3 3，4 4，8 8，9 9，1010，15 15 定义定义A A的如下子集：的如下子集：试问试问 是否是否A的一个分划。的一个分划。解解根据题意根据题意 2，4，8，10 3，9，1510，15 不是不是A的分划，的分划，可成为
26、可成为A的一个分划。的一个分划。本讲稿第三十九页，共四十八页二、集合的覆盖二、集合的覆盖定义定义3-12 设有非空集合设有非空集合A，,其中其中 且且 （i=1，2，m），若），若 ，则称则称S是集合是集合A的一个覆盖。的一个覆盖。例如例如 例例2中中 是是A的分划，也是的分划，也是A的覆盖。的覆盖。是是A的覆盖，但不是的覆盖，但不是A的分划。的分划。本讲稿第四十页，共四十八页练习练习3-53-5 1 设设A=a，b，c，d，e，f，指指出出下下列列哪哪些些是是A的的分分划划（在在相相应应括括号号内内填填入入“1”），哪哪些些是是A的的覆覆盖盖（在在相相应应括括号号内内填填入入“2”），哪哪些
27、些既既不不是是分分划划，也也不不是是覆覆盖盖（在在相应括号内填入相应括号内填入“0”）H1=a，b ，c，d ，a，e，f （）H2=c，e ，c，d，f ，b （）H3=a，b，c，d ，e，f （）H4=a，c，e ，b，c （）201,20本讲稿第四十一页，共四十八页例例 题题 1 给定正整数集给定正整数集N的下列子集的下列子集求集合求集合 解解 B=1,2,3,4,5,6,7=1,2,3,4,5,6,8,16,32,64 C=3,6,9,12,15,18,21,24,27,30 D=1,2,4,8,16,32,64 本讲稿第四十二页，共四十八页2 设设A、B、C和和D是是集集合合，下下
28、述述论论断断哪哪些些正正确确？哪哪些些错错误误？对对正正确确的的论论断断给给出出证明，对错误的论断举出反例。证明，对错误的论断举出反例。（1）若，则 解解 （1）正确。证明如下：设设因为因为所以所以因此因此本讲稿第四十三页，共四十八页（2）若）若 ，则，则设设 ，则则正确。证明如下：正确。证明如下：解解因为因为所以所以因此因此本讲稿第四十四页，共四十八页（3）若）若 ，则，则解解 错误错误但但则则例例如如，设设A=1，2，C=3，4，B=D=1，2，3，4 本讲稿第四十五页，共四十八页（4）若）若 ，则，则 解解 错误错误 例如，设例如，设A=2，3，B=1，2，3，C=2，3，D=2，3，4
29、则则但但本讲稿第四十六页，共四十八页3 n个元素的集合个元素的集合A，有多少种不同的方法分划，有多少种不同的方法分划成为两块？成为两块？解解 A有有 个不同的子集，且这个不同的子集，且这 个不同个不同的子集中，两两互补，除的子集中，两两互补，除 和和U互补，但互补，但不能构成不能构成A的分划外，其余的每对集合均的分划外，其余的每对集合均构成将构成将A分成两块的一个分划，因此分成两块的一个分划，因此A有有 种方法分成两块。种方法分成两块。本讲稿第四十七页，共四十八页4 设设某某校校有有运运动动员员总总数数为为70人人，其其中中足足球球队队员员38人人，篮篮球球队队员员35人人，排排球球队队员员32人人，其其中中有有8人人同同时时参参加加三个队，试求仅同时参加两个队的队员人数是几人？三个队，试求仅同时参加两个队的队员人数是几人？ACBXYZ8 则则#又又 在文氏图中用在文氏图中用A、B、C分别分别表示足球队员、篮球队员和表示足球队员、篮球队员和排球队员的集合排球队员的集合 解解答案：答案：仅同时参加两个队的队员人数是仅同时参加两个队的队员人数是19人人 本讲稿第四十八页，共四十八页