(1.5.1)--ch3—第一讲离散数学离散数学.pdf

《(1.5.1)--ch3—第一讲离散数学离散数学.pdf》由会员分享，可在线阅读，更多相关《(1.5.1)--ch3—第一讲离散数学离散数学.pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学 Discrete Mathematics 3-1 集合及其运算集合及其运算 定义定义3.1.1 具有某种共同性质的事物的全体具有某种共同性质的事物的全体,称为称为集合集合.3.1.1 集合和元素集合和元素(Sets&Elements)1.集合和元素集合和元素 组成集合的那些个体称为集合的组成集合的那些个体称为集合的元素元素.常用大写字母常用大写字母 A，B，C，D，表示集合表示集合.用小写字母用小写字母 a，b，c，d，表示元素表示元素.若元素若元素a属于集合属于集合A 记作记作:a A.若元素若元素a不属于集合不属于集合A 记作记作:a A.元素和集合之间是从属关系元素和集

2、合之间是从属关系.2.集合的表示方法集合的表示方法(1)列举法列举法:列出集合的所有元素列出集合的所有元素,元素间用逗号隔开元素间用逗号隔开,并把它并把它 用花括号用花括号 括起来括起来.(2)叙述法叙述法:通过刻画集合中元素所具备的某种特性来表示集通过刻画集合中元素所具备的某种特性来表示集合的方法合的方法.若用若用P(x)表示任何谓词表示任何谓词,则下式表示一集合则下式表示一集合 A=xP(x)例如例如 A=x|x21=0;B=a|a 是自然数是自然数 3.集合的基数集合的基数 集合集合A中不同元素的个数称为集合中不同元素的个数称为集合A的的基数基数,记作记作|A|.若若|A|是有限数是有限

3、数,则称集合则称集合A为为有限集有限集;否则称否则称 A为为无限集无限集.例如例如:A=2,a,b,9,B=4,5,6,7,8|A|=4,|B|=5 N,Z ,C ,R 等均为无限集等均为无限集 3.1.2 集合间的关系集合间的关系(Relations between sets)1.集合的相等集合的相等 外延性原理外延性原理:两个集合是相等的两个集合是相等的,当且仅当他们有相同的成员当且仅当他们有相同的成员.集合集合A与与B 相等相等,记作记作A=B;例如例如(1)a,b,c=b,c,a (2)a,b,c a,b,c 不相等不相等,记作记作AB.2.集合的包含集合的包含 定义定义3.1.2 设

4、设A和和B是集合是集合,如果如果A的每一元素是的每一元素是B的成员的成员 则称则称A是是B的的子集子集,或或A包含在包含在B内内,或或B包含包含A.记作记作A B,即有：即有：A B(x)(x Ax B)定理定理3.1.1 集合集合A与与B 相等的充要条件是相等的充要条件是 A B且且B A 定义定义3.1.3 若集合若集合A的每一个元素都属于的每一个元素都属于B,但集合但集合B中至少有中至少有一个元素不属于一个元素不属于A,则称则称 A是是B的的真子集真子集,记作记作A B.A B A BAB(x)(x Ax B)(x)(x Bx A)即有即有:性质性质:自反性自反性:传递性传递性:()()

5、()ABBCACA A 注意：注意：从属关系与包含关系的区别从属关系与包含关系的区别:从属关系从属关系a A,是指集合是指集合A中的元素中的元素a与集合与集合A的关系的关系.包含关系包含关系A B是指集合是指集合A与集合与集合B之间的关系之间的关系.例例 试判断下列各式是否正确试判断下列各式是否正确 A.aa.B.aa.C.a a.D.a a,a.1.空集空集 定义定义3.1.4 不含有任何元素的集合不含有任何元素的集合,称为称为空集空集,记作记作.=x|P(x)P(x),P(x)是任意谓词是任意谓词.例如例如 A=x|xR 且且 x2+8=0=注意注意:,.定理定理3.1.2 对任意集合对任

6、意集合A有有 A.3.1.3 几个重要的集合几个重要的集合 对于每一个非空的子集对于每一个非空的子集A,至少有两个不同的子集至少有两个不同的子集,A,称为称为平凡子集平凡子集.例例.设设S=a,3,4,试判断下列各式是否正确试判断下列各式是否正确 A.S B.S C.S.D.S 2.全集全集 定义定义3.1.5 在一定范围内在一定范围内,如果所有集合均为某一集合的子集如果所有集合均为某一集合的子集,则称该集合为则称该集合为全集全集.记作记作E.即有即有:E=x|P(x)P(x)全集是一个相对概念全集是一个相对概念.由于研究的问题不同由于研究的问题不同,所取的所取的 全集也不同全集也不同,而且并

7、非是唯一的而且并非是唯一的.注意注意:如如,在整数范围内研究问题时在整数范围内研究问题时,既可以取既可以取整数集整数集Z作为全集作为全集E 也可以取有理数集也可以取有理数集Q或实数集或实数集R作为全集作为全集.3.幂集幂集 定义定义3.1.6 给定集合给定集合A,由由A的所有子集为元素组合成的集合的所有子集为元素组合成的集合 称为集合称为集合A的的幂集幂集,记作记作P(A)或或2A.幂幂集的符号化表示为集的符号化表示为:P(A)=x|x A 定理定理3.1.3 若有限集合若有限集合A有有n个个元素元素,则其幂集则其幂集P(A)的元素为的元素为2n 例例 设设 A a，b，c,求求P(A).P(

8、A)=,a,b,c,a,b,a,c,b,c,a,b,c A的子集为的子集为 解解:a,b,c a,b,a,c,b,c,a,b,c,例例1 设设 A=,B=,a,a,求求 P(A),P(B).解解 对于集合对于集合A,它只有一个子集它只有一个子集.即即 P(A)=.对于集合对于集合B,有有 1个元素的子集：个元素的子集：2个元素的子集个元素的子集:3个元素的子集：个元素的子集：0个元素的子集：个元素的子集：因此因此 ，a，a,a,a,a,a ,a,a P(B)=,，a，a,a,a,a,a,a,a 例例2.设设 A=,B=P(P(A),判断下列论断是否正确判断下列论断是否正确,并将“并将“Y”或“

9、或“N”填入相应论断后面的括号中填入相应论断后面的括号中.(1)(2)(3)(4)()()()()()()()()Y Y Y Y Y Y N N B B.B B.B.B,B ,B.P(A)=.B=P(P(A)=,例如例如 A=a,b,c,不妨认为不妨认为a,b,c分别是第一分别是第一、二二、三个元素三个元素.于是可用三位二进制数做下标表示于是可用三位二进制数做下标表示A的任意子集的任意子集:二进制数的第二进制数的第i位表示第位表示第i个元素是否属于该子集个元素是否属于该子集,1表示属于表示属于,0表示否表示否.P()|,0,1,2,21niBASiJJ由此可知由此可知,n个元素的集合个元素的集

10、合A,其幂集的元素个数是其幂集的元素个数是 2n.如果如果A是无限集是无限集,则则B=P(A)的元素个数也是无限的的元素个数也是无限的.例如例如 S101=a,c,S011=b,c 三位二进制数可与其子集一一对应三位二进制数可与其子集一一对应.因而因而P(A)=Si|iJ,这里这里J=000,001,111.为了书写方便为了书写方便,可用十进制数代替二进制数可用十进制数代替二进制数,于于是是J=0,1,2,7.一般地一般地,n个元素的集合个元素的集合A,可用可用n位二进制数与其位二进制数与其子集一一对应子集一一对应.因而因而 3-2 集合的运算集合的运算(1)集合的交集合的交 定义定义3.2.

11、1 设任意两集合设任意两集合A和和B,由集合由集合A和和B的所有共同元素的所有共同元素 组成的集合组成的集合S,称为称为A和和B的的交集交集,记为记为AB.S=AB=x|xAxB A B AB AB A,AB B 例例1 设设 A B,求证求证 AC BC.交运算的性质交运算的性质 a)AAA b)A c)AEA d)ABBA e)(AB)CA(BC)121nniiAAAA n个集合的交可记为个集合的交可记为(2)集合的并集合的并 定义定义3.2.2 设任意两集合设任意两集合A和和B,所有属于所有属于A或属于或属于B的元素的元素 组成的集合组成的集合S,称为称为A和和B的的并集并集,记为记为A

12、B.S=AB=x|xAxB A B AB A AB，B AB 并运算的性质并运算的性质 a)AAA b)AA c)AEE d)ABBA e)(AB)CA(BC)例例2 设设 A B,C D,求证求证:A C B D.121nniiAAAA n个集合的个集合的并并可记为可记为 A(BC)=(AB)(AB)A(BC)=(AB)(AC)定理定理3.2.1 设设A、B、C为为三集合三集合,则下列分配律成立则下列分配律成立 A(AB)=A A(AB)=A 定理定理3.2.2(吸收律吸收律)设设A、B为任意为任意两集合两集合,则下列关系成立则下列关系成立 定理定理3.2.3 A B,当且仅当当且仅当 AB

13、=B或或 AB=A.(3)集合的补或差集合的补或差 定义定义3.2.3 设设A、B为任意两集合为任意两集合,所有属于所有属于A而不属于而不属于B的的 元素组成的集合元素组成的集合S,称为称为B对于对于A的的补集补集或或相对补相对补.记为记为A-B.S=A-B=x|xAx B ABB A A-B=A-(AB)=x|xA(xB)例例1 设设 A=a,b,c,d 和和B=b,c,e A-B=a,d B-A=e 定义定义3.2.4 设设E为全集为全集,对任一集合对任一集合A关于关于E的补的补 E-A 称为集合称为集合A的的绝对补绝对补.记为记为A.A=E-A=x|xEx A 例如例如 E=a,b,c,

14、d ,A=a,c A=b,d A E 补的性质补的性质 a)(A)=A b)E=c)=E d)AAE e)AA 定理定理3.2.4设设A,B为任意两个集合为任意两个集合,则下列关系成立则下列关系成立 (AB)=AB (AB)=AB 定理定理3.2.6 设设A,B,C 为三个集合为三个集合,则则 A(B-C)=(AB)-(AC)定理定理3.2.5 设设A,B为任意两个集合为任意两个集合,则下列关系成立则下列关系成立 A-B=AB A-B=A-(AB)定理定理3.2.7 设设A,B为两个集合为两个集合,若若A B,则则 B A (B-A)A=B(4)对称差运算对称差运算 定义定义3.2.5 设设A

15、、B为任意两集合为任意两集合,A和和B的的对称差对称差为集合为集合S,其中的元素或属于其中的元素或属于A，或属于，或属于B，但不能既属于，但不能既属于A又属于又属于B,A B=(A-B)(B-A)记为记为A B.()()x xAxBABBAA B A B 例如例如 A=a,b,c 和和B=b,d A B=a,c,d 对称差的性质对称差的性质 A B=B A A=A A A=A(B C)=(A B)C A B=(AB)(AB)=,-=,-=,-=练习：练习：确定以下各式确定以下各式 ,本节介绍了集合的基本概念、集合的运算和幂集的概念本节介绍了集合的基本概念、集合的运算和幂集的概念.小结小结 重点掌握集合的运算及幂集的概念重点掌握集合的运算及幂集的概念.