离散数学-集合论基础.ppt

《离散数学-集合论基础.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、集合论基础内容提要现代数学的基础渗透到计算机科学的各个方面典型的离散结构模型基本内容：集合的概念、性质、运算、关系、函数等。集合论基础集合的概念注意：集合无法精确定义！说明集合：把具有共同性质的一些组成一个整体，通常用大写字母表示，A，B，S有限集与无限集集合论基础元素与集合元素：组成集合的单个事物，通常用小写字母表示，a,b,c若一个元素a在集合A内，称a属于A，记作a∈A。若一个元素a不在集合A内，称a不属于A，记作aA。集合论基础集合的表示枚举法把集合中的所有元素列举出来例:A={1,2,3,…N}叙述法把集合中元素的共同性质刻划出来例:A

2、={xP(x)},P为一谓词.集合论基础外延性原理两个集合相等,当且仅当它们有相同的成员.记作A=B.也就是说,Vx(x∈A↔x∈B)集合论基础子集子集:集合A的每一个元素都是集合B的元素,则称A是B的子集.记作AB.也就是说,Vx(x∈A→x∈B).回忆:两个集合相等的充要条件是互为子集!集合论基础真子集集合A是集合B的子集,且A与B不相等,则称A是B的真子集.也就是说,(Vx)(x∈A→x∈B)∧(y)(y∈B∧yA)集合论基础空集不包含任何元素的集合称为空集.记作Φ.也就是说,Φ={xP(x)∧¬P(x)}注意:空集是任意集合的子集.比

3、较:Φ和{Φ}集合论基础全集在一定范围内,如果所有集合都是一个集合的子集,那么此集合可作为全集,记作E.也就是说,E={xP(x)∨¬P(x)}.注意:全集的概念是相对的.集合论基础幂集给定任意一个集合A,由A的所有子集作为元素所组成的集合记作Þ(A).显然:(1)Φ和A是Þ(A)中的元素;(2)如果A=n,Þ(A)=2n.集合论基础基于幂集的二进制编码把集合A中的元素按出现的次序作为二进制数的位,而各元素在A的每个子集中的出现编为1,不出现则为0.这样每个子集唯一地对应着一个二进制数编码.若A=n,则Þ(A)={Aii∈J},J={jj是n位二进

4、制数,000…0≦j≦111…1}.为什么?集合论基础集合的运算集合的交集合的并集合的补集合的差集合的对称差集合论基础集合的交集合A和集合B的所有共同元素所组成的集合.记作A∩B.也就是说,A∩B={x(x∈A∧x∈B)}.集合论基础集合交运算的性质幂等律:A∩A=A零一律:A∩Φ=Φ同一律:A∩E=A交换律:A∩B=B∩A结合律:(A∩B)∩C=A∩(B∩C)集合论基础集合的并集合A和集合B中所有属于A或属于B的元素组成的集合,记作A∪B.也就是说,A∪B={x(x∈A∨x∈B)}.集合论基础集合并运算的性质幂等律:A∪A=A同一律:A∪Φ=A零

5、一律:A∪E=E交换律:A∪B=B∪A结合律:(A∪B)∪C=A∪(B∪C)集合论基础集合的补E是全集,A是一个集合,属于E而不属于A的元素所组成的集合.记作~A.也就是说,~A={xxA}.集合论基础集合补运算的性质对合律:~(~A)=ADeMorgan律:~(A∪B)=~A∩~B,~(A∩B)=~A∪~B否定律:~E=Φ,~Φ=EA∪~A=E,A∩~A=Φ集合论基础集合的差所有属于集合A而不属于集合B的元素组成的集合.记作A-B.也就是说,A-B={x(x∈A∧xB)}.比较(1)A-B和B-A;(2)差运算和补运算.集合论基础集合差运算的

6、性质A-B=A∩~BA-B=A-(A∩B)集合论基础集合的对称差或者属于集合A,或者属于集合B,但不能同时属于A和B.记作A⊕B.也就是说,A⊕B={x(x∈A∧xB)∨(x∈B∧xA)},即,A⊕B=(A-B)∪(B-A)集合论基础集合对称差运算的性质交换律:A⊕B=B⊕A同一律:A⊕Φ=A零一律:A⊕A=Φ结合律:(A⊕B)⊕C=A⊕(B⊕C)A⊕B=(A∩~B)∪(~A∩B)集合论基础集合运算的其它性质分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)A∩(B-C)=(A∩B)-(A∩C)吸收律:A∪(A

7、∩B)=AA∩(A∪B)=A集合论基础思考集合运算有最小运算符集合吗?如果有,是什么?A:{~,∩}或{~,∪}集合论基础集合的计数包含与排斥原理:A和B是有限集,其元素个数分别为A和B,则A∪B=A+B-A∩B.特别地,当A和B不相交时,有A∪B=A+B.注:可以推广到n个集合的情形.集合论基础序偶具有固定次序表示两个个体之间的关系记作.显然,≠.比较:序偶与集合的关系(序偶也称为有序集)注意:可以推广到n元情形.集合论基础笛卡尔积给定集合A和集合B,定义这样的序偶,其第一个元素属于A,第二个元素属于B.上述序偶组成

8、的集合称为集合A和B的笛卡尔积.记作AXB.也就是说,AXB={(x∈A)∧(y∈B)}集合论基础笛卡尔积的性质