第一章集合-new.ppt

1、离散数学,侯 爱 民东莞理工学院计算机科学与技术系,前言,离散数学是计算机学科的基础理论的核心课程。是学好数据结构、数据库、操作系统、形式语言、并行处理、人工智能等知识的理论基础。 离散数学的特点内容广泛，抽象理论多。 离散数学的贡献提高学生的抽象思维、逻辑思维和创新思维。 离散数学的学习方法类似高等数学：清楚概念，多做习题。,第一章 集 合,学习重点： 1、集合、子集、空集、全集、补集、幂集等概念。 2、集合的基本运算：并、交、差、对称差。 3、集合代数的有关公式及证明。 4、在组合计数中广泛使用的包含排斥原理。,第1.1节 集合的基本概念,第1.1.1节 集合概念及表示方法 第1.1.2节

2、 子集和空集 第1.1.3节 全集和补集 第1.1.4节 幂集,第1.1.1节 集合概念及表示方法,集合的概念：只能给出说明性的描述。 集合就是具有某种特点的研究对象的聚合。 其中每一个研究对象称为这个集合的元素。 通常用大写字母表示集合，小写字母表示元素。 若a是集合A中的元素，则记为aA。称元素a属于集合A。 若a不 是集合A中的元素，则记为aA。称元素a不属于集合A。,第1.1.1节 集合概念及表示方法,列举法（也称枚举法） 是把集合中的所有元素置于花括号内，元素之间用逗号隔开。 即在集合中列举出所有的元素。 很显然，这种方法只能表示有穷集合。 例1：集合A含5个元素，它们分别是2,3,

3、5,7,13。用列举法可把A表示成： A= 2,3,5,7,13 显然，2A，而 4A。,第1.1.1节 集合概念及表示方法,特征法（也称谓词法） 是以某个小写的英文字母来统一表示该集合的元素，并指出这类元素的共同特征。 例2： B= x|x是素数，x15 花括号内的符号“|”读作“系指”，逗号读作“并且”。因此，集合B是由小于15的素数组成。集合B的元素就是2,3,5,7,13。可见集合B和列举法提到的集合A的元素完全相同。,第1.1.2节 子集和空集,定义1.1.1： 设A，B是集合，如果A中每一个元素又都是B中的元素，则称A是B的子集，也称B包含A或A包含于B中，记作 B A 或 A B

4、 说明： 1.如果A不是B的子集，即A中至少有一个元素不属于B，则称B不包含A或A不包含于B中，记作 B A 或 A B,第1.1.2节 子集和空集,2.如果A是B的子集，但A和B不相等，即在B中总有一些元素不属于A，则称A为B的真子集，记作 B A 或 A B 3.当两个集合X和Y的元素相同时，称这两个集合相等，记作X=Y。 定理1.1.1： 集合A和B相等的充分必要条件是： AB 且 AB。,第1.1.2节 子集和空集,说明： 1.不含有任何元素的集合称为空集，记作或。 2.空集是任何集合的子集。 3.集合中的元素也可以是另一个集合。 4.一般，属于关系“”是元素和集合之间的关系；包含关系

5、“ ”是集合和集合之间的关系。但集合也可以属于（）另一个集合。,第1.1.2节 子集和空集,例3：设A=a，b，B=a，b，a，b。 则：aA，bA。 aB，bB，a，bB。 A B，AB。,第1.1.3节 全集和补集,研究对象的全体称为全集，记作。 设A是集合，由属于全集但不属于集合A的元素构成的集合称为A的补集，记作A（或A）。,第1.1.3节 全集和补集,说明： 例1：全集是全体正整数构成的集合。 若集合A=x|x是正偶数。 则A的补集A=x|x是正奇数。 例2：全集=1,2,3,4,5,6,7,8,9,10。 若集合A=1,2,3,4 。 则A的补集A=5,6,7,8,9,10 。,第

6、1.1.4节 幂集,定义1.1.2： 设A是集合，由A的所有子集作为元素构成的集合称为A的幂集，记作(A)。 例1：设A=a，b，则 A的子集: ,a,b,a,b。 A的幂集：(A)=,a,b,a,b 当一个集合的元素个数为有限时，称该集合为有限集，集合中的元素个数为无限时，称该集合为无限集。有限集A中元素的个数称为有限集A的基。记作|A|。,第1.1.4节 幂集,定理1.1.2： 设A是有限集，且|A|=n，则|(A)|= 2n。 证明：由排列组合的知识可知 |(A)|= C0n+ C1n + C2n + + Cn-1n + Cnn 又由二项式定理可知 (a+b)n= C0n an+C1n

7、an-1b+C2n an-2b2+ Cn-1n a1bn-1 + Cnnbn 若取a=b=1,则有: (1+1)n= C0n+ C1n + Cnn 由此证得 |(A)|= 2n。,第1.1.4节 幂集,例2：A=a，b，c，其幂集(A)=？,第1.2节 集合的基本运算,第1.2.1节 并 第1.2.2节 交 第1.2.3节 差 第1.2.4节 对称差,第1.2.1节 并,定义1.2.1：设A和B是集合，由属于集合A或者属于集合B的所有元素构成的集合，称为A和B的并，记作AB，也即 AB=x | xA或xB 例1：A=1，3，5，B=2，3，4，则： AB=1，2，3，4，5。 例2：A=a，b

8、，c，B=b，c，d，e，则： AB=a，b，c，d，e。,第1.2.1节 并,“并”运算的文氏图：,第1.2.1节 并,“并”运算的性质：1、AB= BA2、A(BC)= (AB)C3、AA= A4、A= A5、AU= U,第1.2.2节 交,定义1.2.2：设A和B是集合，由属于A，B两集合的所有共同元素构成的集合，称为A和B的交，记作AB，也即 AB=x | xA且xB 例1：A=1，3，5，B=2，3，4，则： AB=3。 例2：A=a，b，c，B=b，c，d，e，则： AB=b，c。,第1.2.2节 交,“交”运算的文氏图：,第1.2.2节 交,“交”运算的性质：1、AB= BA2、

9、A(BC)= (AB)C3、AA= A4、A = 5、AU= A,第1.2.2节 交,集合的并、交运算规律： 设A,B,C为任意集合,则: 幂等律 AA=A , AA=A 交换律 AB=BA , AB=BA 结合律 (AB)C = A(BC) (AB)C = A(BC) 同一律 A=A , AU =A 零律 AU=U , A= ,第1.2.2节 交,并和交运算有着密切联系分配律： 定理1.2.1：设A，B，C是集合，则下列分配律成立 A(BC) = (AB)(AC) A(BC) = (AB)(AC) 证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）,第1.2.2节 交,并和交运算有

10、着密切联系吸收律： 定理1.2.2： 设A，B是集合，则下列吸收律成立 A(AB) = A A(AB) = A 证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）,第1.2.2节 交,并和交运算有着密切联系迪摩根律： 定理1.2.3： 设A，B是集合，则下列迪摩根律成立 (AB)=AB (AB)=AB 证明：只证第一等式，第二等式的证明方法相同。（在黑板上演算）,第1.2.2节 交,迪摩根律的推广应用： 对于3个集合A，B，C，则有： (ABC)=ABC (ABC)=ABC 对于n个集合A1，A2，An，则有： (A1A2An)=A1A2An (A1A2An)=A1A2An,第1.2

11、.2节 交,以上的运算规律在证明其它等式中可直接引用,使得集合等式的运算可用代数的方式进行。 例3：设A，B是集合，证明下列等式。 （1） A(AB) =AB （2） (AB)(BA)(AB)=(AB) （3） (AB)(AB)=(AB)(AB) (在黑板上演算第(2)等式的证明过程）,第1.2.3节 差,定义1.2.3: 设A和B是集合，由所有属于A但不属于B的元素构成的集合，称为A减B的差，记作A-B，即AB =x | xA且xB 例1：对于下列集合 A=1，2，3，4，B=3，4，5，则： 差集 A-B=1，2，B-A=5 例2：A=1，2，3，B=4，5，6，则： 差集 A-B=1，2

12、，3,第1.2.3节 差,“差”运算的文氏图：,第1.2.3节 差,定理1.2.4: 设A，B是集合，则A-B=AB。 证明：（在黑板上演算） 例3：设A、B、C是集合，证明 (1) A-(BC) = (A-B)(A-C) (2)(A-B)(B-C)(C-A)=(ABC) (ABC) （在黑板上演算）,第1.2.4节 对称差,定义1.2.4: 设A，B是集合，由所有属于A但不属于B或者属于B但不属于A的元素构成的集合，称为A和B的对称差，记作A B，也即 AB = (AB) (BA) 例1：A=1，2，3，4，B=3，4，5，6， 则： AB=1，2，5，6， BA=1，2，5，6。,第1.2

13、.4节 对称差,“对称差”运算的文氏图：,第1.2.4节 对称差,“对称差”运算的性质： 1）AB = BA 2）(AB)C = A(BC) 3）AA = 4）A = A 5）AU = A,第1.2.4节 对称差,定理1.2.5: 设A，B是集合，则: AB = (AB) (AB)。 证明：（在黑板上演算） 例2：(1)证明A(BC)=(AB)(AC) (2)设A，B是集合，若AB=，证明A=B。 （在黑板上演算）,集合运算性质的一些重要结果：,1）AA=A，AA=A。等幂律 2）AB=BA，AB=BA， AB=BA。交换律 3）(AB)C =A(BC)，(AB)C = A(BC)，(AB)C

14、 =A(BC)。结合律 4）A(BC) =(AB)(AC) A(BC) =(AB)(AC)。分配律 5）AB=AB，AB=AB。迪摩根律 6）A=A。,集合运算性质的一些重要结果：,7）AA=U，AA=。补余律 8）A=A，AU=A。同一律 9）AU=U，A=。零一律 10）A-B=AB。 11）AB=(A-B)(B-A)=(AB)-(AB)。 12）AA= 。 13） = U。 14）U = 。,第1.3节 包含排斥原理,定理1.3.1:(容斥原理)设A，B为有限集合，则 |AB|=|A|+|B|-|AB| 证明: （用文氏图理解） a)当A和B不相交，即AB=，则： |AB|=|A|+|B

15、|,第1.3节 包含排斥原理,证明: b)当A和B相交不空，即AB，则： 由，AB=A(B-A)，且A和(B-A)不相交， 所以：|AB|=|A|+|B-A|。 由，B=(B-A)(AB)，且B-A和AB不相交， 所以：|B|=|(B-A)(AB)| =|(B-A)|+|(AB)|。 于是有：|(B-A)|=|B|-|(AB)|。 所以： |AB|=|A|+ |B|-|(AB)|。,第1.3节 包含排斥原理,三个有限集合A、B、C的包含排斥原理： |ABC|=|A|+|B|+|C|-|AB|-|AC| -|BC|+|ABC| 四个有限集合A、B、C、D的包含排斥原理： |ABCD|=|A|+|

16、B|+|C|+|D|-|AB| -|AC|-|AD|-|BC|-|BD|-|CD| +|ABC|+|ABD|+|ACD| +|BCD|-|ABCD|,第1.3节 包含排斥原理,例1：某班有学生38人，其中有20人参加合唱队，有16人参加话剧队，有8人既参加合唱队又参加话剧队。问有多少人既不参加合唱队也不参加话剧队？ 解：设A表示参加合唱队的学生的集合， B表示参加话剧队的学生的集合。 则：|A|=20，|B|=16，|AB|=8 所以，|AB|=|A|+|B|-|AB|=20+16-8=28 所以，参加了活动（指合唱队或话剧队）的学生人数为28人，剩下者=38-28=10,第1.3节 包含排斥

17、原理,例2：某班有72人，其中选学PASCAL语言的有30人，选学C语言的有36人，选学FORTRAN语言的有29人；选学PASCAL和C语言的有12人；3门语言都选学的有5人；仅仅选学FORTRAN语言的有7人，试求： （1）仅选学两门语言的人数。 （2）这3门语言都不选学的人数。 解： (黑板上演算),第1.3节 包含排斥原理,例3：求1250间能被2，3，5，7中任一个数整除的整数的个数。 解:设A表示1250间能被2整除的整数的集合， B表示1250间能被3整除的整数的集合， C表示1250间能被5整除的整数的集合， D表示1250间能被7整除的整数的集合。 用符号x表示对数x做取整运

18、算，如3.7=3 (黑板上演算),小 结,1.掌握集合、子集、空集、全集、补集等概念，熟悉常用的表示集合的方法以及用文氏图来表示集合的方法，能判定元素与集合之间的关系。懂得两集合间相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。 2.掌握集合的四种基本运算：并、交、差和对称差的定义并熟记集合运算的基本等式，能够利用他们来证明更复杂的集合等式。 3.掌握幂集的定义及计算有限集的幂集所含元素个数所使用的方法和思想。 4.熟记简单情形的包含排斥原理并进行计算。,补充内容,第1.4节 抽象公理和罗素悖论 第1.5节 外延公理和子集公理 第1.6节 偶集公理和联集公理 第1.7节 正则公理

19、和极小元 第1.8节 无穷公理和自然数 第1.9节 幂集公理,第1.4节 抽象公理和罗素悖论,抽象公理：任给一个性质，都有一个满足该性质的客体所组成的集合。 (y)(x)(xy (x) 其中，(x)是不以y为自由变元的公式。 罗素悖论：“由不为自身的成员这一性质的所有客体组成的集合”，会导出矛盾。 在抽象公理中，令(x)= (xx) (y)(x)(xy (xx) 取x=y，则(y)(yy (yy) 而 AB (AB)(AB),第1.4节 抽象公理和罗素悖论,对罗素悖论的理解：通过构造一个性质，使得根据“抽象公理”构造的集合，存在问题。因此，抽象公理是不完备的。 从另一个角度看，“由不为自身的成

20、员”这一性质所决定的客体是不存在的，所以对应的集合应该是空集。这样理解“抽象公理”，就没有问题了。 对于(x)= (xx)来说， 若x仅是元素，则xx无意义 若x是集合，则xx为假命题(aa?) (x)= (xx)本身就存在问题,第1.4节 抽象公理和罗素悖论,定义3.1.3：xy := (xy) 这里，“xy”表示“x不属于y”，或“x属于y为假”。 定义3.1.4：y为集合 := (x)(xyy=) 这里，“(xyy=)”表示“集合y具有成员”，或“集合y是空集”。,第1.5节 外延公理和子集公理,外延公理：如果两个集合中各个元素都是相同的，则它们相等。 (x)(xA xB) = A=B

21、定义3.2.1：若A、B是任何两个集合，当且仅当A、B两个集合恰有相同的各成员时，则称A、B是相等的两个集合，记为A=B。 A=B (x)(xA xB),第1.5节 外延公理和子集公理,子集公理：对于任给一个集合A和集合的每一种性质，存在一个集合B，它的成员恰是A中那些具有性质的成员。 (B)(x)(xB xA (x) 其中，B不可在(x)中出现。 定义3.2.2：集合B是集合A的一个子集，当且仅当B的每个成员也是A的一个成员，记为BA。 BA := (x)(xB xA),第1.5节 外延公理和子集公理,定理3.2.1：x。 定理3.2.2：(x)(xA) A=。 定理3.2.3：AA。 AB

22、 BA = A=B。 AB BC = AC。 定理3.2.4：(AA)。 AB = (BA)。 AB BC = AC。,第1.6节 偶集公理和联集公理,偶集公理：对于给定的任何两个集合A、B，存在一个集合C，其成员恰是A和B。 (C)(x)(xC x=A x=B) 即： C=A，B 定义3.4.1：设集合A，B是一个偶集（即二元集），当且仅当A、B是集合。 A，B=y (x)(xy x=A x=B),第1.6节 偶集公理和联集公理,联集公理：对于任何一个集合A，存在一个集合C，C的成员恰是A的成员的成员。 (C)(x)(xC (B)(BA xB) 定义3.4.2：集合C是集合A的一个联集，当且

23、仅当(x)(xC (B)(BA xB) 定义3.4.3：A := x|(B)(BA xB) 定义3.4.4：AB := x|xA xB 定义3.4.5：A := x|(B)(BA xB) 定义3.4.6：AB := x|xA xB,第1.6节 偶集公理和联集公理,定理3.4.1：xA (B)(BAxB) xAB xA xB = = A=A (AB)=(A)(B) AB = AB AB = AB (A)(ABAC) = BC,第1.6节 偶集公理和联集公理,定理3.4.2：AA=A AB=BA A(BC)=(AB)C A=A AAB AB = ACBC AC BC ABC AB AB=B,第1.

24、6节 偶集公理和联集公理,定理3.4.3：xA (B)(BAxB)(B)(BA) = = A=A A,B=AB AB (C)(CA) = BA AB = BA,第1.6节 偶集公理和联集公理,定理3.4.3：ABAC = BC (C)(CA)(D)(DB) = (AB)=(A)(B) AA (AB)C = (AC)(BC) (AB)C = (AC)(BC),第1.6节 偶集公理和联集公理,定理3.4.4：xA-B xAxB A-A= A-(AB)=A-B A(A-B)=A-B (A-B)B=AB (AB)-B=A-B (AB)-B= (A-B)B= A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C),第1.7