离散数学-集合论.ppt

《离散数学-集合论.ppt》由会员分享，可在线阅读，更多相关《离散数学-集合论.ppt（105页珍藏版）》请在金锄头文库上搜索。

1、2019/3/23,1,离 散 数 学,计算机学院 软件与理论教研室（313）,Discrete Mathematics,Email:,Tel:4994019808,2019/3/23,2,第二部分,集 合 论,Set ,Relation and Mapping,2019/3/23,3,第三章 集合、关系与映射,关系即二元关系,它是集合直乘积的子集 映射是特殊的二元关系 19世纪末著名德国数学家康托(G.cantor) 集合已经发展成为数学及其他各学科不可缺少的描述工具 成为数学中最为基本的概念 集合论分为两种体系 朴素集合论体系(康托集合论体系). 康托从抽象原则出发 概括出:满足某性质的个

2、体放在一起组成集合 隐含矛盾,即罗素(Russell)悖论. 公理集合论体系(属于数理逻辑范畴),2019/3/23,4,3.1 集合及其运算,1. 集合及其表示法 用大写英文字母A,B,C,表示集合 并用xA表示x是集合A中的元素,读作“x属于A” 用xA表示x不是A中的元素,读作“x不属于A”. 一般,集合有两种表示法:列举法和描述元素性质法 列举法 A=a,b,c,d,e; B=书,笔记本,铅笔,课桌,黑板; C=0,1,-3,6; D=北京,天坛,故宫,地球,宇宙. 描述元素性质法 =x|x是英文字母; Z=x|x是整数;,2019/3/23,5,集合及其表示法,需要注意以下几点： 集

3、合中的元素各不相同 如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是实数不能转换为列举法表示.,2019/3/23,6,集合及其表示法,一些常用集合的表示法: N=x|x是自然数=0,1,2,n, Z=x|x为整数=,-3,-2,-1,0,1,2,3, Z+=x|xZx0=1,2,3,n, Q=x|x是有理数 R=x|x为实数

4、还有： P表示素数集合 O表示奇数集合 E表示偶数集合,2019/3/23,7,集合间的包含与相等,2.定义3.1.1.设A,B为集合，若B中的元素都是A中的元素,则称 B是A的子集,记作BA,称A包含B,或B包含于A, 并以B A表示B不是A的子集. 即BAx(xBxA) B Ax(xBxA). 定义3.1.2.设A,B为集合,若集合AB且AB,则称A为B的真子 集,记作AB. 即ABx(xAxB)x(xBxA). 例如：若A=1,2,4,B=1,2,3,4,5,则AB, 而且AB. 对任意集合A有:AA(自反性) 对任意集合A,B,C,若AB且BC,则AC(传递性),2019/3/23,8

5、,空集与全集,定义3.1.3.设A,B为集合,若AB且BA,则称A与B相等,记作A=B. 定义3.1.4.称不拥有任何元素的集合为空集,记作. 空集是任意集合的子集合,是任意非空集合的真子集合 和 的关系是？ 空集是任意集合的子集,可以形象地说:是“最小”的集合. 但没有最大的集合. 在讨论某些具体问题时,往往使用一个在相对的意义下是“最 大”的集合”.,2019/3/23,9,空集与全集,定义3.1.5.如果限定所讨论的集合都是某一集合E的 子集,则称E为全集 全集是一个相对的概念,不同的实际问题可以定 义不同的全集. 例如当被讨论的集合仅仅是0,2,4,6,6,8 时,全集可设为0,2,4

6、,6,8 或x|x是10以内的自然数等,2019/3/23,10,集合的幂集,3.定义3.1.6. 设A为一个集合,称由A的所有子集组成的集合为 A的幂集,记作P(A),即P(A)=X|XA. 如：设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.,2019/3/23,11,集合的运算,4.定义3.1.7. 设A,B为两个集合. 称由A与B的公共元素组成的集合为A与B的交集,记作AB 即AB

7、=x|xAxB 称由A与B的全体元素组成的集合为A与B的并集,记作AB 即AB=x|xAxB 称属于A,但不属于B的元素组成的集合为A与B的相对补集 记为A-B,即A-B=x|xAxB 称属于A而不属于B,或属于B而不属于A的元素组成的集合为A 与B的对称差集,记为AB 即AB=x|(xAxB)(xBxA) 设E为全集, AE, 称E-A为A的绝对补集,记作A 即A=x|xA.,2019/3/23,12,集合的运算,例3.1.1 设A=a,b,c,d,e B=a,c,e,g E=a,b,c,d,e,f,g,h 则:AB=a,b,c,d,e,g AB=a,c,e A-B=b,d B-A=g AB

8、=b,d,g=(A-B)(B-A)=(AB)-(AB) A=f,g,h B=b,d,f,h.,2019/3/23,13,集合的运算,集合运算的Venn图表示：,2019/3/23,14,基本恒等式,5. 集合运算的基本恒等式及其应用 定理3.1.1 设A,B,C是任意集合,E为全集,则有如下恒等式： 幂等律 AA=A;AA=A. 交换律 AB=BA;AB=BA. 结合律 (AB)C=A(BC);(AB)C=A(BC). 分配律 A(BC)=(AB)(AC); A(BC)=(AB)(AC). 德摩根律 绝对形式 (AB)=AB;(AB)=AB. 相对形式 A-(BC)=(A-B)(A-C); A

9、-(BC)=(A-B)(A-C).,2019/3/23,15,基本恒等式,吸收律 A(AB)=A; A(AB)=A. 零律 AE=E; A=. 同一律 A=A; AE=A. 排中律 AA=E. 矛盾律 AA=. 余补律 =E;E=. 双重否定律 (A)=A. 补交转换律 A-B=AB.,2019/3/23,16,基本恒等式,关于对称差运算有以下恒等式: 交换律AB=BA 结合律A(BC)=(AB)C. 对满足分配律 A(BC)=(AB)(AC). A=A; AE=A. AA=; AA=E. 证明集合等式或包含式主要有以下两种方法: 用集合的并、交、补、对称差等定义, 通过逻辑等值 演算证明新的

10、等式或包含式 由已知的集合等式或包含式, 通过集合演算证明新的 集合等式或包含式,2019/3/23,17,集合恒等式的应用,例3.1.3证明:对任意集合A,B有A(AB)=A. 证明: x. xA(AB) xA(xAxB) xA 例3.1.4 证明: 对任意集合A,B有A(AB)=A. 证明: A(AB) =(A)(AB) =A(B) =A =A,(前式使用了并、交运算定义,后式运用了逻辑演算的吸收律),A=A =A(B) =(A)(AB) =A(AB).,2019/3/23,18,续,例3.1.5 若AB=AC,则B=C. 证明: 采用方法 AB=AC A(AB)=A(AC) (AA)B=

11、(AA)C B=C B=C.,按定义若AB且BA则B=C证明,并不容易,2019/3/23,19,续,例3.1.6 证明: A(BC)=(AB)(AC). 证明:(AB)(AC) =(AB)(AC) (AC)(AB) =(AB)(AC) (AC)(AB) =(ABC)(ACB) =A(B-C)(C-B) =A(BC),2019/3/23,20,续,对满足分配律,对也满足分配律吗? 即是否对任意集合A,B,C有A(BC)=(AB)(AC).,设E=a,b,c,d,e,f, A=a,b,c B=b,c,d C=c,d,e A(BC)=a,b,cb,e=a,b,c,e (AB)(AC) =a,b,c

12、,da,b,c,d,e=e.,对不满足分配律,2019/3/23,21,续,(AB)(AC) =(AB)AC)(AC)AB) =(BAC)(CAB) =A(B-C)(C-B) =A(BC).,(AB)(AC)=A(BC) =(BC)-A,2019/3/23,22,有限集合并集的元素计数,定理3.1.2.设A1,A2,An是n个有穷集合,则它们并集的元素个数可由包含排斥公式计算: 证明:设A,B是两个有限集合,则结论显然成立,即有: 设对n=k结论成立,即有: 当n=k+1时,从 由前两式代入整理即得要证结果,2019/3/23,23,续,例3.1.7 设A,B,C是三家计算机公司，它们的固定客

13、户分别有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,|AB|=6,|AC|=7, |BC|=8,|ABC|=5. 求三家计算机公司拥有的固定客户家数,即要计算|ABC|的元素个数. 由有限集合并集元素的计数公式包含排斥公式: |ABC| =(|A|+|B|+|C|)-(|AB|+|AC|+|BC|)+|ABC| =(12+16+20)-(6+7+8)+5=32.,2019/3/23,24,罗

14、素悖论,在数理逻辑中,讨论过悖论,罗素悖论 在集合论中,其表现形式是: 罗素悖论在以所有集合为个体的论域上 定义集合S=X|XX,即一切不是自身元素的集合的集合. 问题是SS吗? 若SS,由定义则SS;若SS,再由定义则SS.矛盾 矛盾的本质在于康托的朴素集合论在刻画集合的方法上缺少限制,以为凡是一个性质就能概括一个集合,2019/3/23,25,3.2 关系,关系是离散数学中刻画元素之间相互联系的一个重要概念 关系数据库模型 最基本的关系是二元关系, 即发生在两个个体之间的关系. 竞赛中的胜负关系,如果每一场比赛都是在两个对手之间 进行,不考虑平局,那么比赛x胜y就可以表示成x,y 关系a,b,c,b,c,a记录了3 场比赛的结果 c是第一名,a是第二名,b是最后一名. 该例是集合a,b,c上的一个二元关系,2019/3/23,26,3.2.1 关系的定义及其表示,有序对与笛卡尔积 定义3.2.1.由两个元素,比如x和y,按照一定次序构成的二 元组称为一个有序对, 记作x,y.