《离散数学教案》PPT课件.ppt

第一篇 预备知识,第一章 集合论,1.0 内容提要,1.1 本章学习要求,1.2 集合,一、集合的概念,集合（SET）由指定范围内的某些特定对象聚集在一起构成。,指定范围内的每一个对象称为这个集合的元素(element),中国所有真皮沙发的聚集,指定范围,特定对象,二、集合的记法,通常用带(不带)标号的大写字母A、B、C、.、A1、B1、C1、.、X、Y、Z、.表示集合；通常用带（不带）标号的小写字母a、b、c、.、a1、b1、c1、.、x、y、z、.表示元素。,固定的符号,1.2.1 集合的表示方法,集合是由它包含的元素完全确定的，为了表示一个集合，通常有：枚举法 隐式法（叙述法）归纳法 递归指定文氏图,1、枚举法（显示法）,-列出集合中全部元素或部分元素的方法叫枚举法,例（1）Aa，b，c，d（2）B=0,1,4,9,16,n2,适用场景：一个集合仅含有限个元素一个集合的元素之间有明显关系,枚举法的优缺点,是一种显式表示法优点：具有透明性缺点：在表示具有某种特性的集合或集合中元素过多时受到了一定的局限，而且，从计算机的角度看，显式法是一种“静态”表示法，如果一下子将这么多的“数据”输入到计算机中去，那将占据大量的“内存”。,2、隐式法（叙述法）,通过刻画集合中元素所具备的某种特性来表示集合的方法称为叙述法（隐式法）一般表示方法：Px|P(x)适用场景：一个集合含有很多或无穷多个元素；一个集合的元素之间有容易刻画的共同特征其突出优点是原则上不要求列出集合中全部元素，而只要给出该集合中元素的特性。,代表元,X所具有的性质p,例,（1）A=x|x是“discrete mathematics”中的所有字母；（2）Z=x|x是一个整数；（3）S=x|x是整数，并且x21=0；（4）Q+=x|x是一个正有理数。,3、归纳法,归纳法是通过归纳定义集合，主要由三部分组成：第一部分：基础。指出某些最基本的元素属于某集合；第二部分：归纳。指出由基本元素造出新元素的方法；第三部分：极小性。指出该集合的界限。,注意：第一部分和第二部分指出一个集合至少包括的元素，第三部分指出一个集合至多要包含的元素,例,集合A按如下方式定义：（1）0和1都是A中的元素；（2）如果a,b是A中的元素，则ab,ba也是A中的元素；（3）有限次使用(1)、(2)后所得到的字符串都是A中的元素。试指出其定义方式。并举出集合A中的3个元素,4、递归指定集合,通过计算规则定义集合中的元素,例 设 a0 1，ai+1 2ai（i0）定义Sa0，a1，a2，.ak|k0，试写出集合S中的所有元素。,5、文氏图解法,文氏图解法是一种利用平面上点的集合作成的对集合的图解。一般用平面上的圆形或方形表示一个集合。,A,A,1.2.2 集合与元素的关系,元素与集合之间的“属于关系”是“明确”的。对某个集合A和元素a来说，a属于集合A，记为aA或者a不属于集合A，记为aA 两者必居其一且仅居其一。,例如，对元素2和N，就有2属于N，即2N，对元素-2和N，就有-2不属于N，即-2N。,罗素悖论,例 在一个很僻静的孤岛上，住着一些人家，岛上只有一位理发师，该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么，谁给这位理发师刮脸？,解：设Cx|x是不给自己刮脸的人 b是这位理发师如 bC，则 bC；如 bC，则 bC。,1.2.3 集合与集合的关系,1、互异性集合中的元素都是不同的，凡是相同的元素，均视为同一个元素；1,1,2=1,22、确定性能够明确加以“区分的”对象；3、无序性集合中的元素是没有顺序的。2,1=1,2,一、集合的三大特征,例,设E=x|(x-1)(x-2)(x-3)=0,xR F=x|(x Z+)且(x212)。试指出集合E和F中的元素。解 集合E=1,2,3，F=1,2,3。,显然，集合E,F中的元素完全相同，我们称这样的两个集合相等,二、外延性原理AB当且仅当A与B具有相同的元素，否则，AB。,例1.2.6,设A=BASIC,PASCAL,ADA，B=ADA,BASIC,PASCAL，请判断A和B的关系。解 根据集合元素的无序性和外延性原理可得，A=B。,因为集合A=B，所以B中的每个元素都是A中的元素，我们称集合A包含集合B。,三、包含和真包含关系,定义 设A,B是任意两个集合，如果B的每个元素都是A的元素，则称B是A的子集合，简称子集(Subset)，这时也称A包含B，或B被A包含，记作AB 或BA，称“”或“”为包含关系(Inclusion Relation)。如果B不被A所包含，则记作B A。,上述包含定义的数学语言描述为：BA对任意x，如xB，则xA。,显然，对任意集合A，都有AA。,例,设A=BASIC,PASCAL,ADA，B=ADA,BASIC,PASCAL，请判断A和B之间的包含关系。解 根据集合间包含关系的定义知，AB 且AB。,又从例知，集合A=B，于是我们有：,定理 设A、B是任意两个集合，则AB，BA A=B,真包含关系,定义 设A,B是任意两个集合，如果 BA并且AB,则称B是A的真子集(Proper Subset)，记作BA，称“”为真包含关系(Properly Inclusion Relation)。如果B不是A的真子集，则记作B A。,上述真子集的数学语言描述为：BA对任意x，如xB，则xA,并且，yA，但是yB,判断下列集合之间是否具有真包含关系。（1）a,b和a,b,c,d；（2）a,b,c,d和a,b,c,d。,解 根据真子集的定义，有（1）a,b a,b,c,d；（2）因为a,b,c,da,b,c,d，所以a,b,c,d不是a,b,c,d 的真子集。,例,例,设A=a是一个集合，B=a,a，试问AB和AB同时成立吗？A=a，aB AB成立；A=a，aB AB成立。解 AB和AB同时成立。,分析,1.2.4 几个特殊集合,定义 不含任何元素的集合叫做空集(Empty Set)，记作。空集可以符号化为=x|xx空集是客观存在的。,1、空集,例 设A=x|(xR)且(x20)，试列举集合A中的所有元素。解 A=。,定理1.2.3（1）空集是一切集合的子集；（2）空集是绝对唯一的。,定理1.2.3（2）的证明,对“唯一性”的证明通常采用反证法。即假设“不唯一”，得出矛盾，从而说明结论正确假设1和2是两个空集，且12，再证明12，出现矛盾，从而说明结论成立。,那么怎么证明12？,分析,根据定理1.2.3（1）空集是一切集合的子集 1 2，2 1，,根据定理，12 12，21,与12矛盾,定义 在一个相对固定的范围内，包含此范围内所有元素的集合，称为全集或论集(Universal Set)，用U或E表示。用文氏图描述如下:,U,2、全集,例,（1）在立体几何中，全集是由空间的全体点组成；（2）在我国的人口普查中，全集是由我国所有人组成。,定理 全集是相对唯一的.,集合A中元素的数目称为集合A的基数（base number)，记为|A|。如|A|是有限的，则称集合A为有限集，如|A|是无限的，则称集合A为无限集。,例 求下列集合的基数。（1）A=；（2）B=；（3）C=a,b,c；（4）D=a,b,c。解|A|=0，|B|=1，|C|=3，|D|=2。,有限集和无限集,m元子集,定义1.2.6 如果一个集合A含有n个元素，则称集合A为n元集，称A的含有m个(0mn)元素的子集为A的m元子集。任给一个n元集，怎样求出它的全部m元子集？例1.2.14 设A=1,2，求出A的全部m元子集。n=|A|=2，mn m=0,1,2。当 m=0 时，得到0元子集：；当 m=1 时，得到1元子集：1,2；当 m=2 时，得到2元子集：1,2。解 A的全部m元子集是、1、2和1,2。,分析,子集总数,一般来说，对于n元集A，它的m（0mn）元子集有 个，所以不同的子集总数有：(1+1)n2n所以，n元集共有2n个子集。,幂集,定义 设A为任意集合，把A的所有不同子集构成的集合叫做A的幂集(power set)，记为P(A)或2A。其符号化表示为 P(A)x|一切xA该集合又称为集族(family of set)。,对集族的研究在数学方面、知识库和表处理语言以及人工智能等方面都有十分重要的意义。,例1.2.15 计算下列幂集,（1）P()；（2）P()；（3）P(a,b,c)。解（1）P()=；（2）P()=,；（3）P(a,b,c)=,a,b,c,a,b,c。,显然，若集合有个元素，则集合共有2|A|个子集，即：|P(A)|2|A|。,1.2.5 集合的运算,定义 设A、B是两个集合，(1)并集 AB=x|xA或xB(2)交集 AB=x|xA且xB(3)差集 A-B=x|xA且xB(4)补集=U-A=x|xU且xA(,AC)(5)对称差集 AB=x|(xA)且(xB)或(xB)且(xA),推广,A1A2A3An,=x|(xA1)或(xA2)或或(xAn),A1A2A3An,x|(xA1)且(xA2)且且(xAn),当n无限增大时，可以记为：,A1A2A3,A1A2A3,定理,1.等幂律:=；=；2.交换律:=;=3.结合律:()=()；()=()；4.恒等律:=；=；5.零律:=；=；6.分配律:()=()()()=()()7.吸收律:A(AB)=A;A(AB)=A；,定理1.2.5(续）,8.A-A=；9.A-B=A-(AB)；10.(A-B)-C=A-(BC)；11.A(B-A)=AB；12.A-B=A；13.否定律：；14.DeMorgan：；15.矛盾律：A；16.排中律：A U。,证明：,DeMorgan律：,分析 定理 设A、B是任意两个集合，则AB，BA A=B,证明（a）：,由、知，,证明（b）：,（b）在 中，用 和 分别取代A和B，则有,1.3 无限集,质 变,无限集合无法用确切的个数来描述，因此，无限集合有许多有限集合所没有的一些特征，而有限集合的一些特征也不能任意推广到无限集合中去，即使有的能推广，也要做某些意义上的修改。,有限集,无限集,量 变,1.3.1 可数集合与不可数集合,问题1,2,3,与12,22,32,哪个集合的元素更多？引入：自然数集合 二十世纪初，集合成为数学的基本概念之后，由冯诺依曼（Von Neumann，J.）用集合的方式来定义自然数取得了成功，提出了用序列，,，,，来定义自然数。,自然数集合N的定义,N，若nN，则n:nnN。也即：0:，1:0，2:,0,1.n:0,1,2,3,.n-1.故 N0,1,2,3,.,n,.,等势的概念,定义 设A，B是两个集合，若在A，B之间存在1-1对应的关系：AB则称A与B是等势的(equipotential)，记为：AB。也称集合A与B等势(equipotent)。,注意：若AB，则 AB。,若AB，则 AB,（）,（）,可数集合(可列集）,定义 凡是与自然数集合等势的集合，统称为可数集合(可列集)(Countable Set)。记为：0(读作阿列夫零)。,例 下列集合都是可数集合：1)O+x|xN，x是奇数;2)Px|xN，x是素数;,解：1）,在O+与N之间建立1-1对应的关系 f：NO+如下：N.O+.2n+1.所以，O+是可数集合。,2）,在P与N之间建立1-1对应的关系f：NP如下：N.P 11.所以，P是可数集合。,定理,两个有限集合等势当且仅当它们有相同的元素个数；有限集合不和其任何真子集等势；可数集合可以和其可数的真子集等势。,不可数集合,定义开区间(0,1)称为不可数集合，其基数设为(读作阿列夫)；凡是与开区间(0,1)等势的集合都是不可数集合。,例(1)闭区间0,1 是不可数集合；(2)实数集合R是不可数集合。,