离散数学 集合论初步

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二篇 集合论,主要包括如下内容：,集合论基础,二元关系,函数,第三章 集合论基础,本章主要介绍如下内容：,基本概念及集合的表示方法,集合间的关系,特殊集合,集合的运算,包含排斥原理,3-1 基本概念,1.集合与元素,集合是个最基本的概念。,集合,：是由确定的对象(客体)构成的集体。用大写的英文字母表示。,这里所谓“确定”是指：论域内任何客体，要么属于这个集合，要么不属于这个集合，是唯一确定的。,元素,：集合中的对象，称之为元素。,：表示元素与集合的属于关系。,例如，N表示自然数集合，2N，而不属于N,写成(,1.5N), 或写成,N。,2. 有限集合与无限集合,这里对有限集合与无限集合只给出朴素的定义，以后再给出严格的形式定义。,有限集合,：元素是有限个的集合。,如果A是有限集合，用|A|表示A中元素个数。例如，A=1,2,3, 则|A|=3。,无限集合,：元素是无限个的集合。,对无限集合的所谓大小的讨论，以后再进行。,3.集合的表示方法,列举法,：将集合中的元素一一列出，写在大括号内。,例如，N=1,2,3,4, A=a,b,c,d,描述法,：用句子(或,谓词公式,)描述元素 的属性。,例如，B=x| x是偶数,C=x|x是实数且2x5,一般地，A=x|P(x), 其中P(x)是谓词公式，如果论域内客体a使得P(a)为真，则aA，否则a,A。,4. 说明,集合中的元素间次序是无关紧要的，但是必须是可以区分的，即是不同的。例如A=a,b,c,a，B=c,b,a,，则A与B是一样的。,对集合中的元素无任何限制，例如令,A=人，石头，1，, B=,本书中常用的几个集合符号的约定：,自然数集合N= 1,2,3,整数集合I，实数集合R，有理数集合Q,集合中的元素也可以是集合，下面的集合的含义不同：,如 a：,张书记,a: 党支部(只有一个书记),a： 分党委(只有一个支部),a： 党委 (只有一个分党委),a： 市党委(只有一个党委),3-2 集合间的关系,一.被包含关系(子集),1.,定义,：A、B是集合，如果A中元素都是B中元素，则称B包含A，A包含于B，也称A是B的子集。记作AB。,文氏图表示如右下图。,例如，N是自然数集合，,R是实数集合，则NR,谓词定义,：,ABx(x,Ax,B),A,B,2.,性质,：,有自反性，对任何集合A有A,A。,有传递性，对任何集合A、B、C，有A,B且 B,C ，则A,C。,有反对称性，对任何集合A、B，有A,B且 B,A ，则A,=,B。,二. 相等关系,1.,定义,：A、B是集合，如果它们的元素完全相同，则称A与B相等。记作A=B。,定理,：A=B，当且仅当,AB且 BA。,证明,：,充分性,，已知AB且 BA，假设AB，则至少有一个元素a,使得a,A而aB；或者a,B而aA。如果a,A而 aB，则与AB矛盾。如果a,B而aA，则与 BA矛盾。所以A=B。,必要性,显然成立，因为如果A=B，则必有AB且 BA。,谓词定义,：,A=B,ABBA,x(x,Ax,B)x(x,Bx,A),x(x,Ax,B)(x,Bx,A),x(x,Ax,B),2.,性质,有自反性，对任何集合A，有A,=,A。,有传递性，对任何集合A、B、C，如果有A,=,B且 B,=,C ，则A,=,C。,有对称性，对任何集合A、B，如果有A,=,B，则B,=,A。,三. 真被包含关系(真子集) ,1.,定义,：A、B是集合，如果,AB且AB,，则称,B真包含A，A真包含于B，也称A是B的真子集。记作AB。,谓词定义：,ABA BAB,x(x,Ax,B)x(x,Ax,B),x(x,Ax,B),(x(x,Ax,B)x(x,Bx,A),(x(x,Ax,B)x(x,Ax,B), (x(x,Ax,B) x(x,Bx,A), x(x,Ax,B) x(xBxA),2.,性质,有传递性，对任何集合A、B、C，如果有A,B且 B,C ，则A,C。,练习题,：设A=a,a,a,b,a,b,c判断下面命题的真值。, aA ,(a,A), cA a,a,b,c, a,A a,ba,b,c, a,b,A a,b,a,b,c, c,a,b,c (c,A)(a,),3-3 特殊集合,一.全集 E,定义,：包含所讨论的所有集合的集合，称之为全集，记作E。,实际上，就是论域。,它的文氏图如右图。,由于讨论的问题不同，,全集也不同。所以全集不唯一。例如，,若讨论数，可以把实数集看成全集。,若讨论人，可以把人类看成全集。,E,由于论域内任何客体x都属于E，所以xE为永真,式。所以需要用永真式定义E。,E=x| P(x),P(x),性质,：对于任何集合A，都有A,E。,二.空集 ,定义,：没有元素的集合，称之为空集，记作。,因为论域内如何客体x是矛盾式，所以,要用一个矛盾式定义。,=x| P(x),P(x),性质,：,1.对于如何集合A，都有,A。,因为x(x,x,A)为永真式，所以,A。,2.空集是唯一的。,证明,假设有两个空集,1,、,2,，则,因为是,1,空集，则由性质1得 ,1,2,。,因为是,2,空集，则由性质1得 ,2,1,。,所以,1,=,2,。,三.集合的幂集,定义:,A是集合，由A的所有子集构成的集合，称之为A的幂集。记作P(A)或2,A,。,P(A)=B| B,A,例如， A P(A), ,a ,a,a,b ,a,b,a,b,a,b,c 则,P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c,C,3,3,C,3,2,C,3,1,C,3,0,|P(A)|,C,n,2,C,n,0,C,n,1,C,n,n,C,n,2,C,n,0,C,n,1,C,n,n,x,n-1,y,x,n-2,y,2,x,n,y,n,C,n,2,C,n,0,C,n,1,C,n,n,性质,：,1.给定有限集合A，如果|A|=n, 则|P(A)|=2,n,。,证明：因为有n个元素，故P(A)中元素个数为,而,(x+y),n,=,令x=y=1时得,2,n,=,所以|P(A)|= 2,n,|2,A,|= 2,|A|,= 2,n,幂集元素的编码,：,a,b,c 则,P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c,A的八个子集分别表示成：B,0,B,1,B,2,B,3,B,4,B,5,B,6,B,7,再将它们的下标写成二进制形式得:B,000,B,001,B,010,B,011, B,100,B,101,B,110,B,111, c b b,c a a,c a,b a,b,c,B,000,B,001,B,010,B,011,B,100,B,101,B,110,B,111,B,0,B,1,B,2,B,3,B,4,B,5,B,6,B,7,子集B,ijk,编码的写法： a,b,c,i、j、k的,确定,：,B,i j k,A,如果aB,ijk, 则 i=1; bB,ijk, 则 j=1; cB,ijk, 则 k=1;否则为0。,如a,b,c,d 子集 B,9,= B,1001,=a,d a,c,d= B,1011,= B,11,作业86页(4) (7 ),练习,P86 (7) 设A=， B=P(P(A),P(A)= ,在求P(P(A),时，一些同学对集合,难理解，实际,上你就将,中的元素分别看成,=a ,=b, 于是,=a,b,B=P(P(A)=P(a,b) =B,0,B,1, B,2, B,3,=B,00,B,01,B,10,B,11,=, b, a, a,b,然后再将a,b代回即可,B=P(P(A)=P(,)=, , ,以后熟悉后就可以直接写出。,a),B ,B,b),B ,B,c),B ,B,a)、b)、c)中命题均为真。,3-4 集合的运算,介绍五种运算：- ,一.交运算,1.,定义：,A、B是集合，由既属于A，也属于B的,元素构成的集合 ,称之为A与B的交集,记作AB。,例如A=1,2,3 B=2,3,4,A,B=2,3,谓词定义,：,A,B=x|x,Ax,B,x,AB,x,Ax,B,如果A,B=，则称A与B不相交。,A,B,A,B,2.,性质,幂等律,对任何集合A，有AA=A。,交换律,对任何集合A、B，有AB=BA。,结合律,对任何集合A、B、C，有,(AB)C=A(BC)。,同一律,对任何集合A，有AE=A。,零律,对任何集合A，有A=。, A,B,AB=A。,前5个公式高中都学过，下面只证明。,证明：,AB=A, x(x,A,B,x,A),x(x,A,B, x,A),(x,A x,AB,),x(aA,B,x,A),(xA,x,AB,),x(,xAxB),x,A),(xA,(,xAxB,),x(,x,Ax,B),x,A),(xA,(,xAxB),),x(T,(,T,(,xA, xB),),x(,xA, xB),x(x,A,xB),A,B,二.,并运算,1.,定义：,A、B是集合，由或属于A，或属于B的,元素构成的集合 ,称之为A与B的并集,记作AB。,例如A=1,2,3 B=2,3,4,AB=1,2,3,4,谓词定义,：,AB =x|xAxB,xAB,xAxB,2.,性质,幂等律,对任何集合A，有AA=A。,交换律,对任何集合A、B，有AB=BA。,结合律,对任何集合A、B、C，有,(AB)C=A(BC)。,A,B,A,B,同一律,对任何集合A，有A=A。,零律,对任何集合A，有AE =E 。,分配律,对任何集合A、B、C，有,A(BC) =(AB)(AC)。,A(BC) =(AB)(AC)。,吸收律,对任何集合A、B，有,A(AB)=A A(AB),=A,。,证明,A(AB)= (AE)(AB) (同一),= A(EB) (分配),= AE=A (零律) (同一),A,B,AB=B。,三. 差运算- (相对补集),1.,定义：,A、B是集合，由属于A，而不属于B的,元素构成的集合 ,称之为A与B的差集,或B对A的,相对补集，记作A-B。,例如A=1,2,3 B=2,3,4,A-B=1,谓词定义,：,A-B =x|xAx,B,xA-B,xAx,B,2.,性质,设A、B、C是任意集合，则,A-=A -A=,A-A= A-B,A,A,B,A-B,A,B ,A-B=,(A-B)-C=(A-C)-(B-C),证明：任取x,(A-C)-(B-C),x,(A-C),x,(B-C),(x,A,x,C),(,x,B,x,C),(x,A,x,C),(,x,B,x,C),(x,A,x,C,x,B),(x,A,x,C, x,C),x,A,x,C,x,B,x,A,x,B,x,C,(x,A,x,B),x,C,x,A,-,B,x,Cx,(,A,-,B)-C,所以 (A-B)-C=(A-C)-(B-C),A-(B,C)=(A-B),(A-C), A-(B,C)=(A-B),(A-C),证明：任取x,A-(BC),x,A,x,(BC),x,A,(,x,B,x,C),x,A,(x,B,x,C),(x,A,x,B),(x,A,x,C ),x,A-B,x,A-C,x,(,A-B)(A-C),所以 A-(BC)=(A-B)(A-C),A,(B-,C)=(AB)-(AC), 但,对- 是不可分配的，如A(A-B)=A,而(AA)-(AB)=,注意:这不是分配律,四. 绝对补集,1.,定义：,A是集合,由不属于A的元素构成的集合 ,称之为A的绝对补集,记作A。,实际上A=E-A。,例如，E=1,2,3,4,A=2,3,A=1,4,谓词定义,：,A =E-A=x|xEx,A,= x|x,A,xA,x,A,2.,性质,设A、B、C是任意集合，则, E= =E (A)=A, A,A= AA=E A-B=AB,A,A,E,(AB)=AB (AB)=AB,这两个公式称之为底-摩根定律。,证明,：任取,x, (AB),x, (AB),xA,B(,x,A,x,B),(x,A,x,B)x,AxB,x AB (AB)=AB,A,B,B,A,证明,： A,B,x(x,Ax,B),x(xBxA)x(x,Bx,A),B,A, A=B 当且仅当AB=E且 A,B=,证明：,AB=EA,B=,x(x,A,B,x,E),(P,T=P),x(x,A,B,x,),(PF=P),x(x,A,B,T,),x(x,A,B,F,),x(x,A,B,(x,A,B),x(x,A,xB),(x,A,xB),x(x,A,xB),(xA,x,B),x(xA,xB),(,xB,xA,),x(x,A,xB),(,xB,x,A,),x(x,A,xB),A,=B,五. 对称差,1.,定义：,A、B是集合,由属于A而不属于B，,或者属于B而不属于A的元素构成的集合,称,之为A与B的对称差,记作A,B。,例如A=1,2,3 B=2,3,4,A,B=1,4,谓词定义,：,A,B=(A-B),(B-A),=x|(x,Ax,B)(x,Bx,A),A,B=(A,B)-(AB),A,B,A,B,E,2.,性质,交换律,对任何集合A、B，有A,B=B,A。,结合律,对任何集合A、B、C，有,(A,B),C=A,(B,C)。,此式证明较繁，教材里有证明，这里从略。,同一律,对任何集合A，有A,=A。, 对任何集合A，有A,A,=。,对,可分配,A,(B,C)=(AB),(AC),证明：,(AB),(AC),= (AB),(AC)-(AB)(AC),= (A(B,C)-(ABC),= A,(,(B,C)-(BC),),(对-分配),= A(B,C),*3-5. 包含排斥原理,这节主要解决,集合的计数,问题。例如有AB两个商店，A,店经营1000种商品，B店经营1200种商品，其中有100种,商品两个商店都经营，问两个商店共经营多少种商品？,显然,|A,B|=|A|+|B|-|AB,|,如果有ABC三个有限集合，则,|A,B,C|=|A,B|+|C|-|(A,B)C|,=|A|+|B|-|AB|+|C|-|(AC),(,BC)|,=|A|+|B|-|AB|+|C|-,(|AC|+|BC|-|ABC|),=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|,A,B,AB,A,B,一般地,，有n,个有限集合A,1, A,2,. A,n,则,例1,某个研究所有170名职工，其中120人会英语，80人,会法语，60人会日语，50人会英语和法语，25人会英语,和日语，30人会法语和日语，10人会英语、日语和法语。,问有多少人不会这三种语言？,令U为全集，E、F、J分别为会英语、,法语和日语人的集合。|U|=170,|E|=120 |F|=80 |J|=60 |EF|=50,|EJ|=25 |FJ|=30 |EFJ|=10,|E,F,J|=|E|+|F|+|J|-|EF|-|EJ|-|FJ|+|EFJ|,=,120806050253010165,|U-(EFJ)|=170-165=5 即有5人不会这三种语言。,E,F,J,10,U,例2.求1到1000之间不能被5、6、8整除的数的个数。,解,.设全集 Ex| x,是1到1000的整数 |E|=1000,A,5,、 A,6,、 A,8,是E的子集并分别表示可被5、6、8整除,的数的集合。,x 表示小于或等于x,的最大整数。,LCM(x,y):表示x,y两个数的最小公倍数。,(Least Common Multiple ),不能被5、6、8整除的数的集合为(A,5,A,6,A,8,),|(A,5,A,6,A,8,)|=|E|A,5,A,6,A,8,|=|E|(,|,A,5,|+|,A,6,|+|,A,8,|,A,5,A,6,|,A,5,A,8,|,A,6,A,8,|+|,A,5,A,6,A,8,|),1000(200+166+1253325418)600,例3,.对24名科技人员掌握外语的情况进行调查结果如下：,英、日、德、法四种外语中，每个人至少会一种；,会英、日、德、法语的人数分别是13、5、10、9人；,同时会英、日语的有2人；,同时会英、法语的有4人；,同时会德、法语的有4人；,同时会英、德语的有4人；,会日语的人不会德语，也不会法语；,问这24人中，只会一种外语的人各是多少人？,同时会英、法、德三种语言的人有多少人？,解,：设全集为U，E,F,G,J,分别表示会英、法、德、日语,人的集合。 |U|24 |EF|=|GF|=|EG|=4,又设 |EFG|=x 只会英、日、德、法一种外语的人分,别是y,1, y,2, y,3, y,4,。,于是可以画出文氏图及方程如下：,y,1,+2(4-x)+x+2=13,y,2,+2(4-x)+x=9,y,3,+2(4-x)+x=10,y,4,+2=5,y,1,+,y,2,+,y,3,+y,4,+3(4-x)+x+2=24,解得： y,1,4， y,2,2， y,3,3， y,4,3 x=1,E,F,G,J,x,4-x,4-x,4-x,2,y,1,y,2,y,3,y,4,作业：,第94页d) b) c) ,本章小结,：,1.掌握集合间三种关系的定义、谓词定义、证明方法。,2.掌握三个特殊集合，会求集合的幂集。,3.掌握集合的五种运算定义、计算方法、性质。,*4.,会用包含排斥原理解决集合计数问题.,习题课,(此课在以后讲),第86页(4),判断下面命题的真值：,a),如果AB，B,C ，则 A C。,T,证明：因为B,C ， AB，所以A C。,b),如果AB，B,C，则 A,C 。,F,举反例A=1 B=,1, C=1,2,满足AB, B,C ，,但是不满足A,C (1A,但1,C,)。,c),如果A,B，BC，则 AC。,F,举反例A=1 B=1,2 C=1,2,满足A,B, BC ，,但是A,C 。,d),如果A,B，BC，则 A,C。,F,举反例A=1 B=1,2 C=1,2,满足A,B, BC ，,但是不满足A,C 。,e)、f),的真值都为,F,，类似举反例。,(7),设A=， B=P(P(A),B=P(P(A)=P(,)=, , ,a),B ,B,b),B ,B,c),B ,B,a)、b)、c)中命题均为真。,第94页(3),全集=N=1,2,3,4,.,解. A=1,2,7,8 B=1,2,3,4,5,6,7,C=3,6,9,12,15,18,21,24,27,30,D=2,4,8,16,32,64 A=3,4,5,6,9,10,11,12.,c) B-(AC),=1,2,3,4,5,6,7-1,2,3,6,7,8,9,12,15,18,21,24,27,30,=4,5,d) (AB)D=3,4,5,6D=2,3,4,5,6,8,16,32,64,(4),.证明 (AB)C=A(BC) iff C,A.,证明；充分性 已知C,A,(AB)C=(AC)(BC),=A(BC) ( C,A AC=A),必要性 已知(AB)C=A(BC),任取 xC,x(AB)C,xA(BC),xA,所以 C,A.,(5)b),证明 (A-B)-C=(A-C)-B,方法1,.,任取 x(A-B)-C,x(A-B)x,C,(,xAx,B)x,C,(,xAx,C)x,B,x(A-C)x,B,x(A-C)-B,所以(A-B)-C=(A-C)-B,方法2,(A-B)-C=(AB)C =(AC) B =(A-C)-B,c),课堂已讲,(6),计算= = , -=, ,-=,-=,(7),证明各式彼此等价。,c)AB=E, A,B, BA.,证明,. AB=E,x(x,AB,x,E,),x(x,AB),(,因x,E 为T,) (,PTP,),x(x,A,x,B),x(x,A,x,B),x(x,A,x,B),A,B,同理AB=E, . x(x,A,x,B),x(x,B,x,A),x(x,B,x,A),B,A,所以,AB=E,A,B BA.,(9),.,在什么条件下，下面命题为真？,a),(A-B),(A-C)=A,解.(A-B),(A-C)= (A,B),(A,C)=A,(,B,C),= A,(,B,C)=A-(B,C)=A,所以满足此式的,充要条件,是：,A,B,C=,b),(A-B),(A-C)=,解.(A-B),(A-C)= A-(B,C)=,所以满足此式的,充要条件,是：,A B,C,c),(A-B),(A-C)=,解.(A-B),(A-C)= (A,B),(A,C)=A,(,B,C),= A,(,B,C)=A-(B,C)=,所以满足此式的,充要条件,是:,A B,C,d),(A-B)(A-C)=,解. 因为 当且仅当A=B ，才有AB=,所以满足此式的,充要条件,是:,A-B=A-C,补充题,1,.A,B是有限集合, P(A)表示A的幂集,已知|A|=3,|P(B)|=64,|P(AB)|=256, 则|B|=( ),|AB|=( ),|A-B|=( ),|A,B|=( )。,解.,由|P(B)|=64=2,6,，得 |B|=6,由|P(AB)|=2562,8,，得|AB|=8,由包含排斥原理得 |A,B|=|A|+|B |A,B|=|A|+|B|AB,|,得83+6|AB,| ，,所以 |AB,|1,|A-B|=,|A|AB,|=3,1=2,|A,B|=,|A,B|AB,|=8,2=6,2,.设F表示一年级大学生的集合,S表示二年级大学生的集合,M表示数学专业学生的集合,C表示计算机专业学生的集合,D表示听离散数学课学生的集合,G表示星期六晚上参加音乐会的学生的集合,H表示星期六晚上很迟才睡觉的学生集合,则将下面各个句子所对应的集合表达式分别写在句子后面的括号内:,(1)所有计算机专业二年级的学生在学离散数学课.,( ).,(2)这些且只有这些学离散数学课的学生或者星期六晚上去听音乐会的学生在星期六晚上很晚才睡觉。,( ),(3) 星期六晚上的音乐会只有大学一、二年级的学生参加.( ),(4)除去数学专业和计算机专业以外的二年级的学生都去参加星期六晚上的音乐会.,( ),C,S,D,D,G=H,G,F,S,(M,C),S,G,第三章 集合论,到此结束,更多资料请访问：,