离散数学-集合论基础

集合论基础内容提要•现代数学的基础•渗透到计算机科学的各个方面•典型的离散结构模型•基本内容：集合的概念、性质、运算、关系、函数等。集合论基础集合的概念注意：集合无法精确定义！说明•集合：把具有共同性质的一些组成一个整体，通常用大写字母表示，A，B，S•有限集与无限集集合论基础元素与集合•元素：组成集合的单个事物，通常用小写字母表示，a,b,c•若一个元素a在集合A内，称a属于A，记作a∈A。•若一个元素a不在集合A内，称a不属于A，记作aA。集合论基础集合的表示•枚举法把集合中的所有元素列举出来例:A={1,2,3,…N}•叙述法把集合中元素的共同性质刻划出来例:A={x|P(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)集合论基础空集不包含任何元素的集合称为空集.记作Φ.也就是说,Φ={x|P(x)∧¬P(x)}•注意:空集是任意集合的子集.•比较:Φ和{Φ}集合论基础全集•在一定范围内,如果所有集合都是一个集合的子集,那么此集合可作为全集,记作E.也就是说,E={x|P(x)∨¬P(x)}.•注意:全集的概念是相对的.集合论基础幂集•给定任意一个集合A,由A的所有子集作为元素所组成的集合记作Þ(A).•显然:(1)Φ和A是Þ(A)中的元素;(2)如果|A|=n,|Þ(A)|=2n.集合论基础基于幂集的二进制编码•把集合A中的元素按出现的次序作为二进制数的位,而各元素在A的每个子集中的出现编为1,不出现则为0.这样每个子集唯一地对应着一个二进制数编码.•若|A|=n,则Þ(A)={Ai|i∈J},J={j|j是n位二进制数,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•零一律:A∪E=E•交换律:A∪B=B∪A•结合律:(A∪B)∪C=A∪(B∪C)集合论基础集合的补•E是全集,A是一个集合,属于E而不属于A的元素所组成的集合.记作~A.•也就是说,~A={x|xA}.集合论基础集合补运算的性质•对合律:~(~A)=A•DeMorgan律:~(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)差运算和补运算.集合论基础集合差运算的性质•A-B=A∩~B•A-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∩B)=A•A∩(A∪B)=A集合论基础思考•集合运算有最小运算符集合吗?•如果有,是什么?A:{~,∩}或{~,∪}集合论基础集合的计数•包含与排斥原理:A和B是有限集,其元素个数分别为|A|和|B|,则|A∪B|=|A|+|B|-|A∩B|.特别地,当A和B不相交时,有|A∪B|=|A|+|B|.注:可以推广到n个集合的情形.集合论基础序偶•具有固定次序•表示两个个体之间的关系•记作a,b.显然,a,b≠b,a.•比较:序偶与集合的关系(序偶也称为有序集)•注意:可以推广到n元情形.集合论基础笛卡尔积•给定集合A和集合B,定义这样的序偶,其第一个元素属于A,第二个元素属于B.•上述序偶组成的集合称为集合A和B的笛卡尔积.记作AXB.•也就是说,AXB={x,y|(x∈A)∧(y∈B)}集合论基础笛卡尔积的性质•AXB≠BXA•若A=Φ或B=Φ,则AXB=Φ.•(AXB)XC≠AX(BXC)•AX(B∪C)=(AXB)∪(AXC)•AX(B∩C)=(AXB)∩(AXC)•(A∪B)XC=(AXC)∪(BXC)•(A∩B)XC=(AXC)∩(BXC)集合论基础二元关系•任一序偶的集合确定了一个二元关系.记作x,y∈R或xRy.•特别地,对于集合A和B,如果x∈A,y∈B,则序偶x,y所组成的关系R称为从集合A到集合B的二元关系.•注意:R是A和B的笛卡尔积的子集.•两个特殊二元关系:全域关系和空关系.集合论基础一个集合上的二元关系•如果序偶中的两个元素属于同一个集合A,那么称R为在集合A上的一个二元关系.•例子:恒等关系I={x,x|x∈A}.集合论基础二元关系的表示•集合方法:二元关系本身就是集合!•关系图:把集合的元素作为结点,若xRy,则标上从x到y的有向线段•矩阵表示:MR=[rij]mxn其中rij=1,当xi,yj∈R,xi∈A,yj∈B.否则rij=0.注意:各表示方法等价.而确定某种表示方法后需遵从相应的运算法则.集合论基础二元关系的性质•一般地,只讨论一个集合上的二元关系•某些特殊的性质需要进一步探讨•自反性(反自反性,非自反性)•对称性(反对称性,非对称性)•传递性集合论基础自反性与反自反性•自反:R是集合A上的一个二元关系,如果对所有的x∈A,都有xRx,则称R是自反的.否则R是非自反的.R自反iff(Vx)(x∈A→x,x∈R)•反自反:R是集合A上的一个二元关系,如果对所有的x∈A,都没有xRx,则称R是反自反的.R反自反iff(Vx)(x∈A→x,xR)•注意:自反与反自反可以同时存在集合论基础对称性与反对称性•R是集合A上的一个二元关系,如果对于所有的x,y,每当xRy,就有yRx,则称R是对称的.否则R是非对称的.R在A上对称iff(Vx)(Vy)((x∈A∧y∈A∧x,y∈R)→y,x∈R)•R是集合A上的一个二元关系,如果对于所有的x,y,每当xRy和yRx时必有x=y,则称R是反对称的.R在A上反对称iff(Vx)(Vy)((x∈A∧y∈A∧x,y∈R∧y,x∈R)→x=y)•注意:对称与反对称可以同时存在集合论基础传递性•R是集合A上的一个二元关系,如果对于任意的元素x,y,z,每当xRy和yRz时,都有xRz,那么R是传递的.否则R是非传递的.R在A上传递iff(Vx)(Vy)(Vz)((x∈A∧y∈A∧z∈A∧x,y∈R∧y,z∈R)→x,z∈R)集合论基础复合关系•设R是从集合A到集合B的一个二元关系,S是从集合B到集合C的另一个二元关系,则记RºS是R和S的复合关系.即RºS={x,z|x∈A∧z∈C∧(y)y∈B∧x,y∈R∧y,z∈S}•特别地,若R=S,则复合关系记为R(2).•推广到一般情形为RºRºR…RºR=R(n).集合论基础复合关系的性质•有序性:RºS≠SºR•结合律:(RºS)ºP=Rº(SºP)集合论基础复合关系的矩阵表示•设R的关系矩阵MR=[rij]mxn,S的关系矩阵Ms=[sjk]nxp,RºS的关系矩阵MRºS=[xik]mxp,其中,xik=∨j=1n(rij∧sjk).注:这里的∨和∧称为逻辑加和逻辑乘.即0∨0=0,0∨1=1,1∨0=1,1∨1=1.0∧0=0,0∧1=0,1∧0=0,1∧1=1.?怎么与数理逻辑中的真与假及运算相对应?集合论基础逆关系•R是从集合A到集合B的一个二元关系,将R中的每一序偶的元素顺序互换,得到R的逆关系R-1.R-1={y,x|x,y∈R}思考:逆关系的矩阵是原关系矩阵的转置.集合论基础逆关系的性质•(R-1)-1=R•(R1∪R2)-1=R1-1∪R2-1•(R1∩R2)-1=R1-1∩R2-1•(R1-R2)-1=R1-1-R2-1•(AXB)-1=BXA•(RºS)-1=S-1ºR-1•(~R)-1=~R-1注:~R=AXB-R集合论基础关系的闭包运算•自反闭包:把原关系R扩充成包含R的最小的自反的关系,记作r(R).•对称闭包:把原关系R扩充成包含R的最小的对称的关系,记作s(R).•传递闭包:把原关系R扩充成包含R的最小的传递的关系,记作t(R).集合论基础思考•R本身是自反的,它的自反闭包是什么?•R是对称的呢?•R是传递的呢?集合论基础自反闭包的计算•R是集合A上的一个二元关系,那么R的自反闭包r(R)=R∪IA为什么?集合论基础对称闭包的计算•R是集合A上的一个二元关系,那么R的对称闭包s(R)=R∪R-1为什么?集合论基础传递闭包的计算•R是集合A上的一个二元关系,那么R的传递闭包t(R)=∪i=1∞Ri,且存在一个正整数k≦|A|(=n),使得t(R)=∪i=1kRi,通常就当成t(R)=∪i=1nRi.为什么?集合论基础闭包运算之间的性质R是集合A上的一个二元关系,则有•rs(R)=sr(R)•rt(R)=tr(R)•st(R)ts(R)集合论基础集合的覆盖•把一个集合A分成若干个非空子集(称为分块)Si,使得A中的每一个元素至少属于其中一个分块,且A=∪i=1mSi.•令S={S1,S2,…,Sm},称集合S是集合A的一个覆盖.集合论基础集合的分划•令集合S={S1,S2,…,Sm}是集合A的一个覆盖,且Si∩Sj=Φ(i≠j),则称集合S是集合A的一个分划(或称为划分).•最小分划:A本身组成的集合;•最大分划:A中每个元素构成一个分块所组成的集合.集合论基础交叉分划与加细•若{A1,A2,…,Ar}和{B1,B2,…,Bs}是同一集合A的两种分划,而其中所有Ai∩Bj≠Φ组成的集合,称为原来两种分划的交叉分划.•可以证明:•交叉分划也是原集合的一种分划;•交叉分划也是原分划的加细.集合论基础等价关系•R是集合A上的一个二元关系,若R是自反的、对称的和传递的，则R为等价关系。•回忆：前面所述的二元关系特点。集合论基础等价类•R是集合A上的一个二元关系，对于任意A中的元素a，定义集合[a]R={x|x∈A,aRx}为元素a形成的关于等价关系R的等价类。集合论基础等价类的性质•等价类非空（为什么？）•R是集合A上的等价关系，a,b都是A中的元素，aRbiff[a]R=[b]R.(为什么？）集合论基础商集及性质•R上集合A上一个等价关系，其所定义的等价类所组成的集合{[a]R|a∈A}称为A关于R的商集。记作A/R。可以证明：•等价关系R决定了A的一个分划，即A/R；•A上的一个分划确定A上的一个等价关系R，且这个分划就是A/R。集合论基础偏序关系•R是集合A上的一个二元关系，若R是自反的、反对称的和传递的，则称R是A上的一个偏序关系。通常记作≤；•序偶〈A，≤〉称为A的偏序集集合论基础盖住•在偏序集〈A，≤〉中，如果x,y都是A中的元素，且x≤y，而x≠y，A中不存在元素