离散数学-集合.ppt

《离散数学-集合.ppt》由会员分享，可在线阅读，更多相关《离散数学-集合.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第4章 关系n4.0 集合及相关概念集合及相关概念n4.1 关系的定义及其表示关系的定义及其表示n4.2 关系运算关系运算n4.3 关系的性质关系的性质n4.4 等价关系与偏序关系等价关系与偏序关系14.0 集合及其运算n集合及其表示法集合及其表示法n包含包含(子集子集)与相等与相等n空集与全集空集与全集n集合运算集合运算(,-,)n基本集合恒等式基本集合恒等式n包含与相等的证明方法包含与相等的证明方法2集合的概念集合集合是数学中最基本的概念是数学中最基本的概念,没有严格的定义没有严格的定义 理解成某些个体组成的整体理解成某些个体组成的整体,常用大写字母常用大写字母A,B,C等表示等表示元素元

2、素:集合中的个体，通常用小写字母集合中的个体，通常用小写字母a,b,c等表示等表示又又例例如如 所有的正整数组成一个集合，每一个正整数均是这个集 合的元素。例如例如 全体中国人可组成一个集合，每一个中国人均是这个集合的 元素3集合的概念（续）x A(x属于属于A):x是是A的元素的元素 x A(x不不属于属于A):x不不是是A的元素的元素无无穷穷集集:元素个数无限的集合元素个数无限的集合有有穷穷集集(有限集有限集):元素个数有限的集合元素个数有限的集合.|A|:A中元素个数中元素个数k元集元集:k个元素的集合个元素的集合,k 04集合的表示法列举法列举法:列出集合中的全体元素，元素之间用逗号分

3、开，然后列出集合中的全体元素，元素之间用逗号分开，然后用花括号括起来。用花括号括起来。如如 A=a,b,c,d,N=0,1,2,描述法：描述法：用用谓词谓词P(x)表示表示x具有性具有性质质P，用，用 x|P(x)表示具有性表示具有性质质P的所有元素的所有元素组组成的集合。成的集合。如如N=x|x是自然数是自然数 说说明明:(1)集合中的元素各不相同集合中的元素各不相同.如如,1,2,3=1,1,2,3(2)集合中的元素没有次序集合中的元素没有次序.如如,1,2,3=3,1,2=1,3,1,2,2(3)有有时时两种方法都适用两种方法都适用,可根据需要可根据需要选选用用.5常用集合nN：自然数集

4、：自然数集nZ：整数集整数集nZ+：正整数集：正整数集nQ：有理数集有理数集nP：素数集素数集nQ*：非零有理数集：非零有理数集nR：实实数集数集nR*：非零：非零实实数集数集nC：复数集复数集 于是于是2N2N，2.5 N2.5 N，-3 N-3 N，但，但2.5Q2.5Q，-3R-3R。6例例1 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,192x|xNN且且x100 x1

5、00-3,-1,1,3 2n|nZ+且且n10n10 7包含与相等包含包含(子集子集)A B x(x A x B)不包含不包含 A B x(x A x B)相等相等 A=B A B B A不相等不相等 A B A B B A真包含真包含(真子集真子集)A B A B A B 集合的包含和相等是集合间的两个基本关系。集合的包含和相等是集合间的两个基本关系。8包含与相等(续)例如：例如：A=1,2,3,B=x|x R|x|1,C=x|x R x2=1,D=-1,1,有：有：C B,C B,C A,A B,B A,C=D9集合的包含关系具有如下几条性质：（1）对对任意集合任意集合A，A A；（2）对

6、任意集合）对任意集合A、B、C，若，若A B,B C，则，则 A C；。包含与相等(续)10空集与全集空集空集:不含任何元素的集合不含任何元素的集合例如例如,x|x20 x R=定理定理1.1 空集是任何集合的子集空集是任何集合的子集证证 用归谬法用归谬法.假设不然假设不然,则存在集合则存在集合A,使得使得 A,即存在即存在x,x 且且x A,矛盾矛盾.推论推论 空集是惟一的空集是惟一的.证证 假设存在假设存在1和和2，则，则12 且且21，因此，因此1=2全集全集E:限定所讨论的集合都是限定所讨论的集合都是E的子集的子集.相对性相对性 11幂集幂集幂集幂集P(A):A的所有子集组成的集合的所

7、有子集组成的集合,即即 P(A)=x|x A 例例2 2 设设A=aA=a 则则0 0个元素的子集：个元素的子集：1个元素的子集：个元素的子集：a因此 设设B=B=a,ba,b 则则0 0个元素的子集个元素的子集：1个元素的子集：个元素的子集：a,b 2个元素的子集个元素的子集：a,b 因此 定理定理1.2 如果如果|A|=n，则则|P(A)|=2n 证证12例例3 3 设设 ,求求P(A)P(A)和和P(B)解解 对于集合对于集合A，它只有一个子集，它只有一个子集 ，即 对于集合对于集合B，有，有 1个元素的子集：个元素的子集：，a，a 2个元素的子集：个元素的子集：,3个元素的子集：个元素

8、的子集：0个元素的子集：个元素的子集：因此因此 13答案：答案：ABD2.2.设设 ,试判断下列各式是否正试判断下列各式是否正确，并将正确的题号填入括号内。确，并将正确的题号填入括号内。A.B.C.D.答案：答案：A BCA.B.C.D.练习练习1.试判断下列各式是否正确，并将正确的题试判断下列各式是否正确，并将正确的题号填入括号内。号填入括号内。143.设设 ,，判，判断下列论断是否正确，并将断下列论断是否正确，并将“Y”或或“N”填入相应论断后面的括号中。填入相应论断后面的括号中。(1)(2)(3)(4)()()()()()()()()YYYYYYNN令令则则15集合运算并并 A B=x|

9、x A x B 交交 A B=x|x A x B 相对补相对补 A B=x|x A x B 对称差对称差 A B=(A B)(B A)=(A B)(A B)绝对补绝对补 A=E A=x|x A 例如例如 设设E=0,1,9,A=0,1,2,3,B=1,3,5,7,9,则则 A B=0,1,2,3,5,7,9,A B=1,3,A B=0,2,A B=0,2,5,7,9,A=4,5,6,7,8,9,B=0,2,4,6,8说明说明:1.只使用圆括号只使用圆括号2.运算顺序运算顺序:优先级别为优先级别为(1)括号括号,(2)和幂集和幂集,(3)其他其他.同级别的按从左到右运算同级别的按从左到右运算16

10、实例例例4 设设E=x|x是北京某大学学生是北京某大学学生,A,B,C,D是是E的子集的子集,A=x|x是北京人是北京人,B=x|x是走读生是走读生,C=x|x是数学系学生是数学系学生,D=x|x是喜欢听音乐的学生是喜欢听音乐的学生.试描述下列各集合中学生的特征试描述下列各集合中学生的特征:(A D)C=A B=(A-B)D=D B=x|x是北京人或喜欢听音乐是北京人或喜欢听音乐,但不是数学系学生但不是数学系学生 x|x是外地走读生是外地走读生 x|x是北京住校生是北京住校生,并且喜欢听音乐并且喜欢听音乐 x|x是不喜欢听音乐的住校生是不喜欢听音乐的住校生17文氏图表示18基本集合恒等式1.幂

11、幂等等律律A A=A,A A=A2.交交换换律律A B=B A,A B=B A3.结结合合律律(A B)C=A(B C)(A B)C=A(B C)4.分配分配律律A(B C)=(A B)(A C)A(B C)=(A B)(A C)5.德摩根律德摩根律 绝对形式绝对形式(B C)=BC,(B C)=BC 相对形式相对形式 A(B C)=(A B)(A C)A(B C)=(A B)(A C)19基本集合恒等式(续)6.吸收吸收律律 A(A B)=A,A(A B)=A7.零律零律 A E=E,A=8.同一律同一律 A=A,A E=A9.排中排中律律 AA=E10.矛盾律矛盾律 AA=11.余补律余补

12、律 =E,E=12.双重否定双重否定律律 A=A13.补交转换律补交转换律 A-B=AB20基本集合恒等式(续)14.关于对称差的恒等式关于对称差的恒等式 (1)交换律交换律 A B=B A (2)结合律结合律 (A B)C=A(B C)(3)对对 的分配律的分配律 A(B C)=(A B)(A C)(4)A=A,A E=A (5)A A=,A A=E注意注意:对对 没有分配律没有分配律,反例如下反例如下 A=a,b,c,B=b,c,d,C=c,d,e A(B C)=a,b,c b,e=a,b,c,e (A B)(A C)=a,b,c,d a,b,c,d,e=e,两者不等两者不等21证明集合包

13、含或相等方法一方法一.根据定义根据定义,通过逻辑等值演算证明通过逻辑等值演算证明方法二方法二.利用已知集合等式或包含式利用已知集合等式或包含式,通过集合演算证明通过集合演算证明例例5 证明证明:(1)A B=B A(交换交换律律)证证 x x A B x A x B (并的定义并的定义)x B x A (逻辑演算的交换律逻辑演算的交换律)x B A (并的定义并的定义)22例5(续)(2)A(B C)=(A B)(A C)(分配分配律律)证证 x x A(B C)x A(x B x C)(并并,交的定义交的定义)(x A x B)(x A x C)(逻辑演算的分配律逻辑演算的分配律)x(A B

14、)(A C)(并并,交的定义交的定义)(3)A E=E(零律零律)证证 x x A E x A x E (并的定义并的定义)x A 1 (全集全集E的定义的定义)1 (逻辑演算的零律逻辑演算的零律)x E (全集全集E的定义的定义)23例5(续)(4)A E=A(同一同一律律)证证 x x A E x A x E (交的定义交的定义)x A 1 (全集全集E的定义的定义)x A (逻辑演算的同一律逻辑演算的同一律)24实例例例6 证明证明 A(A B)=A（吸收律）吸收律）证证 利用例利用例5证明的证明的4条等式证明条等式证明 A(A B)=(A E)(A B)(同一律同一律)=A(E B)(

15、分配律分配律)=A(B E)(交换律交换律)=A E (零律零律)=A (同一律同一律)对其余的基本集合恒等式不再一一证明对其余的基本集合恒等式不再一一证明(请自行证明请自行证明),今后把它们作为已知的集合等式使用今后把它们作为已知的集合等式使用.25实例例例7 证明证明(A-B)-C=(A-C)-(B-C)证证 (A-C)-(B-C)=(A C)(B C)(补交转换律补交转换律)=(A C)(B C)(德德摩根律摩根律)=(A C)(B C)(双重否定律双重否定律)=(A C B)(A C C)(分配律分配律)=(A C B)(A )(矛盾律矛盾律)=A C B (零律零律,同一律同一律)=

16、(A B)C (交换律交换律,结合律结合律)=(A B)C (补交转换律补交转换律)26实例例例8 证明证明(A B)(A C)=(B C)-A证证 (A B)(A C)=(A B)-(A C)(A C)-(A B)=(A B)A C)(A C)A B)=(B A C)(C A B)=(B C)(C B)A =(B-C)(C-B)A =(B C)-A27实例例例9 设设A,B为任意集合为任意集合,证明证明:(1)A A B证证 x x A x A x B (附加律附加律)x A B(2)A B A证证 x x A B x A x B x A (化简律化简律)28实例(续)(3)A-B A证证

17、x x A-B x A x B x A (化简律化简律)(4)若若A B,则则P(A)P(B)证证 x x P(A)x A x B (已知已知A B)x P(B)29实例例例10 证明证明 A B=A B-A B.证证 A B=(A B)(A B)=(A A)(A B)(B A)(B B)=(A B)(B A)=(A B)(A B)=A B-A B 30D 若若 ，则，则 A=B 练习练习 1 设设A、B、C是任意集合，判断下述论断是否是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。正确，并将正确的题号填入括号内。A 若若 ，则，则 B=CB 若若 ，则，则 B=C C 若若A-B

18、=A-C，则，则 B=C()D 反例反例 设设A=a,b,c,B=b,d,C=c,d 则则 但但31(2)2 设设U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，确定下列集合，确定下列集合的元素，将其填入相应的花括号内。的元素，将其填入相应的花括号内。(1)(3)(4)(521,42,3,4,54323 设设U表表示示刘刘平平拥拥有有的的所所有有书书的的集集合合，其其中中A是是离离散散数数学学参参考考书书的的集集合合，B是是操操作作系系统统参参考考书书的的集集合合，C是是今今年年出出版版的的新新书书的的集集合合，D是是从从图图书书馆馆借借来来的的书书的的集集合合。现现知知道

19、道如如下下情形：情形：（1）所有离散数学参考书都是今年出版的新书。（）所有离散数学参考书都是今年出版的新书。（）（2）所有操作系统参考书都是从图书馆借来的。（）所有操作系统参考书都是从图书馆借来的。（）（3）今年出版的新书不是从图书馆借来的。（）今年出版的新书不是从图书馆借来的。（）（4）没有一本操作系统的参考书是今年出版的。（）没有一本操作系统的参考书是今年出版的。（）3157试试用用集集合合的的方方法法分分别别表表示示上上述述四四种种情情形形，可可供供选选择择的的答答案案如如下下，请请从从下下述述答答案案中中挑挑选选出出相相应应表表达达式式的的编编号号填填入入每每一一种情形后面的括号中。种

20、情形后面的括号中。1.2.3.4.5.6.7.334 判判断断下下列列论论断断是是否否正正确确，对对正正确确的的论论断断在在相相应应题题后后的的括括号号中中标标入入“Y”，对对错错误误的的论论断断在在相相应应题题后后的的括括号号中中标标入入“N”。1）若若 ，则，则 （）2）若若 ，则，则 （）3）若若 ，则，则 （）4）若若 ，则，则 （）5）若若 ，则，则 ()6）若若 ，则，则 ()7）若若 ，则，则 ()8）若若 ，则，则 ()YYYYNNNN345 设设某某校校有有运运动动员员总总数数为为70人人，其其中中足足球球队队员员38人人，篮篮球球队队员员35人人，排排球球队队员员32人人，其其中中有有8人人同同时时参参加加三三个个队队，试试求求仅仅同同时时参参加加两两个个队队的的队队员员人人数是几人？数是几人？ACBXYZ8 则则#又又 在文氏图中用在文氏图中用A、B、C分别分别表示足球队员、篮球队员和表示足球队员、篮球队员和排球队员的集合排球队员的集合 解解答案：答案：仅同时参加两个队的队员人数是仅同时参加两个队的队员人数是19人人 35作业nP30n1.4，1.5，1.12(2)、(4)n1.13，1.14，1.15，1.16，1.2036