离散数学-集合论

2020/6/291离散数学计算机学院软件与理论教研室（313）DiscreteMathematicsEmail:[e-mail]:4994019－8082020/6/292第二部分集合论Set,RelationandMapping2020/6/293第三章集合、关系与映射关系即二元关系,它是集合直乘积的子集映射是特殊的二元关系19世纪末著名德国数学家康托(G.cantor)集合已经发展成为数学及其他各学科不可缺少的描述工具成为数学中最为基本的概念集合论分为两种体系朴素集合论体系(康托集合论体系).康托从抽象原则出发概括出:满足某性质的个体放在一起组成集合隐含矛盾,即罗素(Russell)悖论.公理集合论体系(属于数理逻辑范畴)2020/6/2943.1集合及其运算1.集合及其表示法用大写英文字母A,B,C,…表示集合并用x∈A表示x是集合A中的元素,读作“x属于A”用xA表示x不是A中的元素,读作“x不属于A”.一般,集合有两种表示法:列举法和描述元素性质法列举法A={a,b,c,d,e};B={书,笔记本,铅笔,课桌,黑板};C={0,1,-3,6};D={北京,天坛,故宫,地球,宇宙}.描述元素性质法Σ={x|x是英文字母};Z={x|x是整数};2020/6/295集合及其表示法需要注意以下几点：集合中的元素各不相同如{1,2,3,4}与{1,1,2,3,4,4}是相同的集合都是含元素1,2,3,4的集合集合中的元素不规定次序如：{1,2,3,4}={4,2,3,1}.有些集合的两种表示法能互相转换,有些则不能如：{x|x是英文字母}={a,b,c,d,e,f,g,…,x,y,z};{x|x是非负偶数}={0,2,4,6,8,10,…,2n,…};{x|x是实数}不能转换为列举法表示.2020/6/296集合及其表示法一些常用集合的表示法:N={x|x是自然数}={0,1,2,…,n,…}Z={x|x为整数}={…,-3,-2,-1,0,1,2,3,…}Z+={x|x∈Z∧x＞0}={1,2,3,…,n,…}Q={x|x是有理数}R={x|x为实数}还有：P表示素数集合O表示奇数集合E表示偶数集合2020/6/297集合间的包含与相等2.定义3.1.1.设A,B为集合，若B中的元素都是A中的元素,则称B是A的子集,记作BA,称A包含B,或B包含于A,并以BA表示B不是A的子集.即BA∀x(x∈B→x∈A)BAx(x∈B∧xA).定义3.1.2.设A,B为集合,若集合AB且A≠B,则称A为B的真子集,记作AB.即AB∀x(x∈A→x∈B)∧x(x∈B∧xA).例如：若A={1,2,4},B={1,2,3,4,5},则AB,而且AB.对任意集合A有:AA(自反性)对任意集合A,B,C,若AB且BC,则AC(传递性)2020/6/298空集与全集定义3.1.3.设A,B为集合,若AB且BA,则称A与B相等,记作A=B.定义3.1.4.称不拥有任何元素的集合为空集,记作.空集是任意集合的子集合,是任意非空集合的真子集合和{}的关系是？空集是任意集合的子集,可以形象地说:是“最小”的集合.但没有最大的集合.在讨论某些具体问题时,往往使用一个在相对的意义下是“最大”的集合”.2020/6/299空集与全集定义3.1.5.如果限定所讨论的集合都是某一集合E的子集,则称E为全集全集是一个相对的概念,不同的实际问题可以定义不同的全集.例如当被讨论的集合仅仅是{0,2,4},{6},{6,8}时,全集可设为{0,2,4,6,8}或{x|x是10以内的自然数}等2020/6/2910集合的幂集3.定义3.1.6.设A为一个集合,称由A的所有子集组成的集合为A的幂集,记作P(A),即P(A)={X|XA}.如：设A={1,2,3}则P(A)={,{1},{2},{3},{1,2},1,3},{2,3},A}.若|A|=n,则P(A)的元素个数|P(A)|=2n.元素个数有限的集合称有穷集,对其子集有一种编码方法:设A={a1,a2,a3}则A2=A010={a2},A5=A101={a1,a3}.2020/6/2911集合的运算4.定义3.1.7.设A,B为两个集合.①称由A与B的公共元素组成的集合为A与B的交集,记作A∩B即A∩B={x|xA∧xB}②称由A与B的全体元素组成的集合为A与B的并集,记作A∪B即A∪B={x|xA∨xB}③称属于A,但不属于B的元素组成的集合为A与B的相对补集记为A-B,即A-B={x|xA∧xB}④称属于A而不属于B,或属于B而不属于A的元素组成的集合为A与B的对称差集,记为A⊕B即A⊕B={x|(xA∧xB)∨(xB∧xA)}⑤设E为全集,AE,称E-A为A的绝对补集,记作～A即～A={x|xA}.2020/6/2912集合的运算例3.1.1设A={a,b,c,d,e}B={a,c,e,g}E={a,b,c,d,e,f,g,h}则:A∪B={a,b,c,d,e,g}A∩B={a,c,e}A-B={b,d}B-A={g}A⊕B={b,d,g}=(A-B)∪(B-A)=(A∪B)-(A∩B)～A={f,g,h}～B={b,d,f,h}.2020/6/2913集合的运算集合运算的Venn图表示：2020/6/2914基本恒等式5.集合运算的基本恒等式及其应用定理3.1.1设A,B,C是任意集合,E为全集,则有如下恒等式：①幂等律A∪A=A;A∩A=A.②交换律A∪B=B∪A;A∩B=B∩A.③结合律(A∪B)∪C=A∪(B∪C);(A∩B)∩C=A∩(B∩C).④分配律A∪(B∩C)=(A∪B)∩(A∪C);A∩(B∪C)=(A∩B)∪(A∩C).⑤德摩根律绝对形式～(A∪B)=～A∩～B;～(A∩B)=～A∪～B.相对形式A-(B∪C)=(A-B)∩(A-C);A-(B∩C)=(A-B)∪(A-C).2020/6/2915基本恒等式⑥吸收律A∪(A∩B)=A;A∩(A∪B)=A.⑦零律A∪E=E;A∩φ=φ.⑧同一律A∪φ=A;A∩E=A.⑨排中律A∪～A=E.⑩矛盾律A∩～A=φ.⑾余补律～φ=E;～E=φ.⑿双重否定律～(～A)=A.⒀补交转换律A-B=A∩～B.2020/6/2916基本恒等式关于对称差运算有以下恒等式:①交换律A⊕B=B⊕A②结合律A⊕(B⊕C)=(A⊕B)⊕C.③∩对⊕满足分配律A∩(B⊕C)=(A∩B)⊕(A∩C).④A⊕φ=A;A⊕E=～A.⑤A⊕A=φ;A⊕～A=E.证明集合等式或包含式主要有以下两种方法:①用集合的并、交、补、对称差等定义,通过逻辑等值演算证明新的等式或包含式②由已知的集合等式或包含式,通过集合演算证明新的集合等式或包含式2020/6/2917集合恒等式的应用例3.1.3证明:对任意集合A,B有A∪(A∩B)=A.证明:①∀x.x∈A∪(A∩B)x∈A∨(x∈A∧x∈B)x∈A例3.1.4证明:对任意集合A,B有A∩(A∪B)=A.证明:②A∩(A∪B)=(A∪φ)∩(A∪B)=A∪(φ∩B)=A∪φ=A(前式使用了并、交运算定义,后式运用了逻辑演算的吸收律)A=A∪φ=A∪(φ∩B)=(A∪φ)∩(A∪B)=A∩(A∪B).2020/6/2918续例3.1.5若A⊕B=A⊕C,则B=C.证明:采用方法②A⊕B=A⊕CA⊕(A⊕B)=A⊕(A⊕C)(A⊕A)⊕B=(A⊕A)⊕Cφ⊕B=φ⊕CB=C.按定义若AB且BA则B=C证明,并不容易2020/6/2919续例3.1.6证明:A∩(B⊕C)=(A∩B)⊕(A∩C).证明:(A∩B)⊕(A∩C)=((A∩B)∩～(A∩C))∪((A∩C)∩～(A∩B))=((A∩B)∩(～A∪～C))∪((A∩C)∩(～A∪～B))=(A∩B∩～C)∪(A∩C∩～B)=A∩((B-C)∪(C-B))=A∩(B⊕C)2020/6/2920续∩对⊕满足分配律,∪对⊕也满足分配律吗?即是否对任意集合A,B,C有A∪(B⊕C)=(A∪B)⊕(A∪C).设E={a,b,c,d,e,f},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}.∪对⊕不满足分配律2020/6/2921续(A∪B)⊕(A∪C)=((A∪B)∩～A∩～C)∪((A∪C)∩～A∩～B)=(B∩～A∩～C)∪(C∩～A∩～B)=～A∩((B-C)∪(C-B))=～A∩(B⊕C).(A∪B)⊕(A∪C)=～A∩(B⊕C)=(B⊕C)-A2020/6/2922有限集合并集的元素计数定理3.1.2.设A1,A2,…,An是n个有穷集合,则它们并集的元素个数可由包含排斥公式计算:证明:设A,B是两个有限集合,则结论显然成立,即有:设对n=k结论成立,即有:当n=k+1时,从由前两式代入整理即得要证结果2020/6/2923续例3.1.7设A,B,C是三家计算机公司，它们的固定客户分别有12，16和20家。已知A与B，B与C，C与A的公共固定客户分别为6，8和7家，三家的公共固定客户有5家，求三家计算机公司拥有的固定客户家数。解:以A,B,C分别表记A,B,C三家计算机公司的客户集合,知|A|=12,|B|=16,|C|=20,|A∩B|=6,|A∩C|=7,|B∩C|=8,|A∩B∩C|=5.求三家计算机公司拥有的固定客户家数,即要计算|A∪B∪C|的元素个数.由有限集合并集元素的计数公式包含排斥公式:|A∪B∪C|=(|A|+|B|+|C|)-(|A∩B|+|A∩C|+|B∩C|)+|A∩B∩C|=(12+16+20)-(6+7+8)+5=32.2020/6/2924罗素悖论在数理逻辑中,讨论过悖论,罗素悖论在集合论中,其表现形式是:罗素悖论在以所有集合为个体的论域上定义集合S={X|XX},即一切不是自身元素的集合的集合.问题是S∈S吗?若S∈S,由定义则SS;若SS,再由定义则S∈S.矛盾矛盾的本质在于康托的朴素集合论在刻画集合的方法上缺少限制,以为凡是一个性质就能概括一个集合2020/6/29253.2关系关系是离散数学中刻画元素之间相互联系的一个重要概念关系数据库模型最基本的关系是二元关系,即发生在两个个体之间的关系.竞赛中的胜负关系,如果每一场比赛都是在两个对手之间进行,不考虑平局,那么比赛x胜y就可以表示成〈x,y〉关系{〈a,b〉,〈c,b〉,〈c,a〉}记录了3场比赛的结果c是第一名,a是第二名,b是最后一名.该例是集合{a,b,c}上的一个二元关系2020/6/29263.2.1关系的定义及其表示有序对与笛卡尔积定义3.2.1.由两个元素,比如x和y,按照一定次序构成的二元组称为一个有序对,记作〈x,y〉.其中x是序对的第一元素,y是序对的第二元素.直角坐标系中点的坐标(1,-2),(0,5)有序对中,如果两个元素不相等,是不能交换次序的.(0,1)与(1,0)代表不同的有序对两个有序对〈x,y〉与〈u,v〉相等x=u且y=v.2020/6/2927续例3.2.1.设有序对〈x+y,3〉=〈3y-2,x+5〉根据有序对相等的充要条件,解由第一、第二元素对应相等组成的二元一次方程组得:x=-2,y=0.定义3.2.2.设A,B为集合,以A中元素作为第一元素,B中元素作为第二元素做有序对,所有这样的有序对构成的集合称为A与B的笛卡尔积,记作A×B.符号化表示为A×B={〈x,y〉|x∈A∧y∈B}.2020/6/2928续例3.2.2.设A={0,1},B={a,b}则A×B={〈0,a〉,〈0,b〉,〈1,a〉,1,b〉}B×A={〈a,0〉,〈a,1〉,〈b,0〉,〈b,1