离散数学集合论基础

离散数学集合论基础第1页，共72页，2023年，2月20日，星期一集合论基础集合的概念注意：集合无法精确定义！说明集合：把具有共同性质的一些组成一个整体，通常用大写字母表示，A，B，S有限集与无限集第2页，共72页，2023年，2月20日，星期一集合论基础元素与集合元素：组成集合的单个事物，通常用小写字母表示，a,b,c若一个元素a在集合A内，称a属于A，记作a∈A。若一个元素a不在集合A内，称a不属于A，记作aA。第3页，共72页，2023年，2月20日，星期一集合论基础集合的表示枚举法把集合中的所有元素列举出来例:A={1,2,3,…N}叙述法把集合中元素的共同性质刻划出来例:A={x|P(x)},P为一谓词.第4页，共72页，2023年，2月20日，星期一集合论基础外延性原理两个集合相等,当且仅当它们有相同的成员.记作A=B.也就是说,Vx(x∈A↔x∈B)第5页，共72页，2023年，2月20日，星期一集合论基础子集子集:集合A的每一个元素都是集合B的元素,则称A是B的子集.记作AB.

也就是说,Vx(x∈A→x∈B).回忆:两个集合相等的充要条件是互为子集!第6页，共72页，2023年，2月20日，星期一集合论基础真子集集合A是集合B的子集,且A与B不相等,则称A是B的真子集.也就是说,(Vx)(x∈A→x∈B)∧(y)(y∈B∧y

A)第7页，共72页，2023年，2月20日，星期一集合论基础空集不包含任何元素的集合称为空集.记作Φ.也就是说,Φ={x|P(x)∧¬P(x)}注意:空集是任意集合的子集.比较:Φ和{Φ}第8页，共72页，2023年，2月20日，星期一集合论基础全集在一定范围内,如果所有集合都是一个集合的子集,那么此集合可作为全集,记作E.

也就是说,E={x|P(x)∨¬P(x)}.注意:全集的概念是相对的.第9页，共72页，2023年，2月20日，星期一集合论基础幂集给定任意一个集合A,由A的所有子集作为元素所组成的集合记作Þ(A).显然:(1)Φ和A是Þ(A)中的元素;(2)如果|A|=n,|Þ(A)|=2n.第10页，共72页，2023年，2月20日，星期一集合论基础基于幂集的二进制编码把集合A中的元素按出现的次序作为二进制数的位,而各元素在A的每个子集中的出现编为1,不出现则为0.这样每个子集唯一地对应着一个二进制数编码.若|A|=n,则Þ(A)={Ai|i∈J},J={j|j是n位二进制数,000…0≦j≦111…1}.

为什么?第11页，共72页，2023年，2月20日，星期一集合论基础集合的运算集合的交集合的并集合的补集合的差集合的对称差第12页，共72页，2023年，2月20日，星期一集合论基础集合的交集合A和集合B的所有共同元素所组成的集合.记作A∩B.也就是说,A∩B={x|(x∈A∧x∈B)}.第13页，共72页，2023年，2月20日，星期一集合论基础集合交运算的性质幂等律:A∩A=A零一律:A∩Φ=Φ同一律:A∩E=A交换律:A∩B=B∩A结合律:(A∩B)∩C=A∩(B∩C)第14页，共72页，2023年，2月20日，星期一集合论基础集合的并集合A和集合B中所有属于A或属于B的元素组成的集合,记作A∪B.也就是说,A∪B={x|(x∈A∨x∈B)}.第15页，共72页，2023年，2月20日，星期一集合论基础集合并运算的性质幂等律:A∪A=A同一律:A∪Φ=A零一律:A∪E=E交换律:A∪B=B∪A结合律:(A∪B)∪C=A∪(B∪C)第16页，共72页，2023年，2月20日，星期一集合论基础集合的补E是全集,A是一个集合,属于E而不属于A的元素所组成的集合.记作~A.也就是说,~A={x|x

A}.第17页，共72页，2023年，2月20日，星期一集合论基础集合补运算的性质对合律:~(~A)=ADeMorgan律:~(A∪B)=~A∩~B,~(A∩B)=~A∪~B否定律:~E=Φ,~Φ=E

A∪~A=E,A∩~A=Φ第18页，共72页，2023年，2月20日，星期一集合论基础集合的差所有属于集合A而不属于集合B的元素组成的集合.记作A-B.

也就是说,A-B={x|(x∈A∧x

B)}.比较(1)A-B和B-A; (2)差运算和补运算.第19页，共72页，2023年，2月20日，星期一集合论基础集合差运算的性质A-B=A∩~BA-B=A-(A∩B)第20页，共72页，2023年，2月20日，星期一集合论基础集合的对称差或者属于集合A,或者属于集合B,但不能同时属于A和B.记作A⊕B.也就是说,A⊕B={x|(x∈A∧xB)∨

(x∈B∧xA)},即,

A⊕B=(A-B)∪(B-A)第21页，共72页，2023年，2月20日，星期一集合论基础集合对称差运算的性质交换律:A⊕B=B⊕A同一律:A⊕Φ=A

零一律:A⊕A=Φ结合律:(A⊕B)⊕C=A⊕(B⊕C)A⊕B=(A∩~B)∪(~A∩B)第22页，共72页，2023年，2月20日，星期一集合论基础集合运算的其它性质分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)A∩(B-C)=(A∩B)-(A∩C)吸收律:A∪(A∩B)=AA∩(A∪B)=A

第23页，共72页，2023年，2月20日，星期一集合论基础思考集合运算有最小运算符集合吗?如果有,是什么?A:{~,∩}或{~,∪}第24页，共72页，2023年，2月20日，星期一集合论基础集合的计数包含与排斥原理:A和B是有限集,其元素个数分别为|A|和|B|,则

|A∪B|=|A|+|B|-|A∩B|.

特别地,当A和B不相交时,有

|A∪B|=|A|+|B|.注:可以推广到n个集合的情形.第25页，共72页，2023年，2月20日，星期一集合论基础序偶具有固定次序表示两个个体之间的关系记作<a,b>.显然,<a,b>≠<b,a>.比较:序偶与集合的关系

(序偶也称为有序集)注意:可以推广到n元情形.第26页，共72页，2023年，2月20日，星期一集合论基础笛卡尔积给定集合A和集合B,定义这样的序偶,其第一个元素属于A,第二个元素属于B.上述序偶组成的集合称为集合A和B的笛卡尔积.记作AXB.也就是说,AXB={<x,y>|(x∈A)∧(y∈B)}第27页，共72页，2023年，2月20日，星期一集合论基础笛卡尔积的性质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)第28页，共72页，2023年，2月20日，星期一集合论基础二元关系任一序偶的集合确定了一个二元关系.

记作<x,y>∈R或xRy.特别地,对于集合A和B,如果x∈A,y∈B,则序偶<x,y>所组成的关系R称为从集合A到集合B的二元关系.注意:R是A和B的笛卡尔积的子集.两个特殊二元关系:全域关系和空关系.第29页，共72页，2023年，2月20日，星期一集合论基础一个集合上的二元关系如果序偶中的两个元素属于同一个集合A,那么称R为在集合A上的一个二元关系.例子:恒等关系I={<x,x>|x∈A}.第30页，共72页，2023年，2月20日，星期一集合论基础二元关系的表示集合方法:二元关系本身就是集合!关系图:把集合的元素作为结点,若xRy,则标上从x到y的有向线段矩阵表示:MR=[rij]mxn

其中rij=1,当<xi,yj>∈R,xi∈A,yj∈B.

否则rij=0.注意:各表示方法等价.而确定某种表示方法后需遵从相应的运算法则.第31页，共72页，2023年，2月20日，星期一集合论基础二元关系的性质一般地,只讨论一个集合上的二元关系某些特殊的性质需要进一步探讨自反性(反自反性,非自反性)对称性(反对称性,非对称性)传递性第32页，共72页，2023年，2月20日，星期一集合论基础自反性与反自反性自反: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)注意:自反与反自反可以同时存在第33页，共72页，2023年，2月20日，星期一集合论基础对称性与反对称性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)注意:对称与反对称可以同时存在第34页，共72页，2023年，2月20日，星期一集合论基础传递性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)第35页，共72页，2023年，2月20日，星期一集合论基础复合关系设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).第36页，共72页，2023年，2月20日，星期一集合论基础复合关系的性质有序性:RºS≠SºR结合律:(RºS)ºP=Rº(SºP)第37页，共72页，2023年，2月20日，星期一集合论基础复合关系的矩阵表示设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.?怎么与数理逻辑中的真与假及运算相对应?第38页，共72页，2023年，2月20日，星期一集合论基础逆关系R是从集合A到集合B的一个二元关系,将R中的每一序偶的元素顺序互换,得到R的逆关系R-1.R-1={<y,x>|<x,y>∈R}思考:逆关系的矩阵是原关系矩阵的转置.第39页，共72页，2023年，2月20日，星期一集合论基础逆关系的性质(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第40页，共72页，2023年，2月20日，星期一集合论基础关系的闭包运算自反闭包:把原关系R扩充成包含R的最小的自反的关系,记作r(R).对称闭包:把原关系R扩充成包含R的最小的对称的关系,记作s(R).传递闭包:把原关系R扩充成包含R的最小的传递的关系,记作t(R).第41页，共72页，2023年，2月20日，星期一集合论基础思考R本身是自反的,它的自反闭包是什么?R是对称的呢?R是传递的呢?第42页，共72页，2023年，2月20日，星期一集合论基础自反闭包的计算R是集合A上的一个二元关系,那么R的自反闭包

r(R)=R∪IA

为什么?第43页，共72页，2023年，2月20日，星期一集合论基础对称闭包的计算R是集合A上的一个二元关系,那么R的对称闭包

s(R)=R∪R-1

为什么?第44页，共72页，2023年，2月20日，星期一集合论基础传递闭包的计算R是集合A上的一个二元关系,那么R的传递闭包

t(R)=∪i=1∞Ri,

且存在一个正整数k≦|A|(=n),使得

t(R)=∪i=1kRi,

通常就当成t(R)=∪i=1nRi.为什么?第45页，共72页，2023年，2月20日，星期一集合论基础闭包运算之间的性质R是集合A上的一个二元关系,则有rs(R)=sr(R)rt(R)=tr(R)st(R)

ts(R)第46页，共72页，2023年，2月20日，星期一集合论基础集合的覆盖把一个集合A分成若干个非空子集(称为分块)Si,使得A中的每一个元素至少属于其中一个分块,且A=∪i=1mSi.令S={S1,S2,…,Sm},称集合S是集合A的一个覆盖.第47页，共72页，2023年，2月20日，星期一集合论基础集合的分划令集合S={S1,S2,…,Sm}是集合A的一个覆盖,且Si∩

Sj=Φ(i≠j),

则称集合S是集合A的一个分划(或称为划分).最小分划:A本身组成的集合;最大分划:A中每个元素构成一个分块所组成的集合.第48页，共72页，2023年，2月20日，星期一集合论基础交叉分划与加细若{A1,A2,…,Ar}和{B1,B2,…,Bs}是同一集合A的两种分划,而其中所有Ai∩

Bj≠Φ组成的集合,称为原来两种分划的交叉分划.可以证明:交叉分划也是原集合的一种分划;交叉分划也是原分划的加细.

第49页，共72页，2023年，2月20日，星期一集合论基础等价关系R是集合A上的一个二元关系,若R是自反的、对称的和传递的，则R为等价关系。回忆：前面所述的二元关系特点。第50页，共72页，2023年，2月20日，星期一集合论基础等价类R是集合A上的一个二元关系，对于任意A中的元素a，定义集合

[a]R={x|x∈A,aRx}

为元素a形成的关于等价关系R的等价类。第51页，共72页，2023年，2月20日，星期一集合论基础等价类的性质等价类非空（为什么？）R是集合A上的等价关系，a,b都是A中的元素，aRbiff[a]R=[b]R.(为什么？）第52页，共72页，2023年，2月20日，星期一集合论基础商集及性质R上集合A上一个等价关系，其所定义的等价类所组成的集合{[a]R|a∈A}称为A关于R的商集。记作A/R。可以证明：等价关系R决定了A的一个分划，即A/R；A上的一个分划确定A上的一个等价关系R，且这个分划就是A/R。第53页，共72页，2023年，2月20日，星期一集合论基础偏序关系R是集合A上的一个二元关系，若R是自反的、反对称的和传递的，则称R是A上的一个偏序关系。通常记作≤；序偶〈A，≤〉称为A的偏序集第54页，共72页，2023年，2月20日，星期一集合论基础盖住在偏序集〈A，≤〉中，如果x,y都是A中的元素，且x≤y，而x≠y，A中不存在元素z,满足x≤z,z≤y，则称元素y盖住元素x.记作COVA={<x,y>|x,y∈A,y盖住x}.即y是满足偏序关系的紧跟在x后面的那个元素！显然，盖住关系是唯一的。第55页，共72页，2023年，2月20日，星期一集合论基础Hasse图根据盖住的性质画出Hasse图作图规则：（1）用小圆圈代表集合中的元素；（2）根据盖住关系连接两个元素，被盖住的元素在下，盖的元素在上；（3）把COVA中的序偶全部按（2）中的方法画出来。第56页，共72页，2023年，2月20日，星期一集合论基础链与反链〈A，≤〉是偏序集，B是A的一个子集，如果B中的元素都有偏序关系，则称B为链；〈A，≤〉是偏序集，B是A的一个子集，如果B中的元素都没有偏序关系，则称B为反链；注意：单个元素所组成的子集既是链又是反链。第57页，共72页，2023年，2月20日，星期一集合论基础链与反链的长度链中元素的个数称为链的长度，其最大值为|A|。注意：在Hasse图中，链中的元素按照盖住关系从下往上连成一线。反链中元素的个数称为反链的长度.最长反链的长度即链的个数。注意：反链中的元素分属于不同的链。为什么？第58页，共72页，2023年，2月20日，星期一集合论基础全序关系〈A，≤〉是偏序集，如果A本身是链，则称〈A，≤〉为全序集。二元关系≤为全序关系或线序关系。在Hasse图中全序关系表示成一条直线。〈A，≤〉中只有一条链，其长度为|A|。第59页，共72页，2023年，2月20日，星期一集合论基础极大元〈A，≤〉是偏序集，B是A的子集，对于B中的一个元素b，如果B中没有任何不同于b的元素x，满足b≤x，则称b是B的极大元。元素b是子集B的链中最大的去盖的元素（最顶层元素）。注意：极大元不是唯一的！第60页，共72页，2023年，2月20日，星期一集合论基础极小元〈A，≤〉是偏序集，B是A的子集，对于B中的一个元素b，如果B中没有任何不同于b的元素x，满足x≤b，则称b是B的极小元。元素b是子集B的链中最小的被盖住的元素（最底层元素）。注意：极小元不是唯一的！第61页，共72页，2023年，2月20日，星期一集合论基础最大元〈A，≤〉是偏序集，B是A的子集，对于B中的一个元素b，如果B中任何不同于b的元素x，都满足x≤b，则称b是B的最大元。元素b是子集B的不同链中共同的极大元，所以最大元是唯一的。第62页，共72页，2023年，2月20日，星期一集合论基础最小元〈A，≤〉是偏序集，B是A的子集，对于B中的一个元素b，如果B中任何不同于b的元素x，都满足b≤x，则称b是B的最小元。元素b是子集B的不同链中共同的极小元，所以最小元是唯一的。第63页，共72页，2023年，2月20日，星期一集合论基础思考当〈A，≤〉是全序集时，它的极大元、极小元、最大元、最小元怎样？第64页，共72页，2023年，2月20日，星期一集合论基础上界与下界〈A，≤〉是偏序集，B是A的子集，存在A中的一个元素a，对于B中的任何元素x，都满足x≤a，则称a是B的上界。〈A，≤〉是偏序集，B是A的子集，存在A中的一个元素a，对于B中的任何元素x，都满足a≤x，则称a是B的下界。显然