离散数论-第五章

1、第五章 集合的基本概念及其运算5.1 集合与元素5.2 集合间的相等和包含关系5.3 幂集5.4 集合的运算5.5 有穷集的计数原理 5.6 集合的归纳定义法5.7 有序偶和笛卡儿乘积1 5.1 集合与元素目标要求： 会用抽象法表示集合 掌握集合的抽象表示和枚举表示的互相转换重点难点: 集合的抽象表示 抽象原则2 集合是人们能够明确区分的一些对象(客体)构成的一个整体。 例如：“全体中国人”，“所有英文字母”都构成集合。 但“全校高个子学生”不能构成集合，因为“高个子”是一个模糊概念。 集合通常用大写英文字母表示，其中用: N 表示自然数集合(含0)， R 表示实数集合， Q 表示有理数集合，

2、 I (Z) 表示整数集合。 集合：集合是一个原始概念,无精确定义。1875年康托尔给其定义如下：3 如果 a是集合A 中的元素，就写成 aA，读作: a 属于A。 如果 b 不是A中的元素，就写成 bA，读作:b不属于A。集合的表示方法（1）枚举法（2）抽象法枚举法：把集合中所有元素全部列举出来，用 括起来，元素之间用逗号分开。 元素：集合里含有的 对象 称为该集合的元素。通常用小写英文字母 表示元素。4例如: A = a, e, i, o, u抽象法: 用 谓词 概括集合中元素的属性. 其描述形式为 S = x | P(x) 例: S1 = x | x是中国的省 S2 = x | x=2k

3、+1 且 kN = x | x是正奇数 S3 = x | x = an, n N 可见 ， 一个集合的抽象描述形式不唯一。S = a0, a1, a2, , an,，其中 n为自然数。5例: A = x | x是英文元音字母 由抽象原则可知，对任意x: x A x是英文元音字母其中, 表示当且仅当。 定义5.1(抽象原则): 任给一个性质 P，就确定 了一个集合A , A 的元素恰好是具有性质 P的对象，即: A = x | P(x) 也就是说 x ( P(x) xA )6抽象原则的限制:(1) 谓词 P(x) 要明确清楚 反例：A = x | p(x) , p(x)：x是公园里美丽的花朵 “

4、美丽” 是一模糊概念。因此A不能够成集合。 (2) 不能取 P(x) 为 x x 这样的谓词来定义集合，否则就会产生悖论 。 例：设 T = x | x x , 由抽象原则，就有: x: x T x x， 把 T 代入 x 得， T T T T ， 矛盾!75.2 集合间的相等和包含关系目标要求： 掌握集合相等（=）、包含（）的定义。 掌握 、=、 之间的联系与区别。 掌握空集的性质 重点难点： 集合间的相等与包含关系 空集的性质 证明集合相等8一 、集合的相等 定义5.2 (集合相等)（外延性公理）：设 A, B 为任意两集合，若A和B含有相同的元素，则称 A和B相等, 记作：A=B A =

5、 B x ( xA xB )或 A = B x (xAxB) x (xBxA)9例：2. x | x-1 = 0 = -1，1 3. 1，2，3 = 3，1，2 表明 集合与其元素排列次序无关 。a, b, a = a, a, b, b, a = a, b 表明 集合与其元素重复出现次数无关a, a, b, b, a 称为多重集, 也称为 bag x | x4且x是正整数 = 1,2,3,4 = x | x0，则 A= X | X =0例：证明AB=AB25 证：对任意X XA （A B） XA XA B XA （XA XB ） XA （X A X B ） （XA X A）（XA X B） X

6、A X B XAB 所以 A（A B）= AB 根据外延性公理 AB = A B 。因此，A + B又可以定义为： A + B = （A B）（ B A ）例：试证A（A B）= AB 26把两个集合的，运算可推广到n个集合的，运算。 设A1,A2, , An为集合，则: A1A2An= X|XA1 X A2X An A1A2An=X|XA1 X A2X An i=1ni=1ni=1i=1也可将上述n个集合的，分别记作 Ai 和 Ai 同理可把无穷多个集合的 ， 分别记为 ： Ai =A1A2An Ai =A1A2An 27设集合的聚合： A=AS1,AS2, J=S1,S2,S3，则A可以简

7、写成： A=Ai | iJ其中称A为加标集合，J为标码集合。定义5.13（集合族或集合的聚合）:如果一个集合的所有元素都是集合，则称该集合为集合族或集合的聚合。28定义5.14(集合的聚合上的运算) 设A是全集U的子集的聚合 A=ASi|SiJ J=S1,S2, （1）A的元素的并集表示为 A或 Asi SiJ A= ASi=x|ASi（ASiAxASi） SiJ（2）若A ,A的元素的交集表示为A或 Asi SiJ A= Asi =x|ASi （Asi AxAsi） SiJ29因为若A=,则蕴涵式ASi A x ASi的前件为假， ASi（ ASi A x ASi ）为真，这就定义了全集U，

8、因此要求A 。例：设C=0, 0,1, 0,1,2 则 C=0 0,1 0,1,2=0,1,2 C=0 0,1 0,1,2=0例：设 A=Ai| i J, J=a,b,c, Aa=0,1,2, Ab=4,5,6, Ac=2则 Ai=AaAbAc=0,1,2,4,5,6 Ai=AaAbAc=iJiJ注意: 定义（2）中要求A 。303132集合恒等式幂等律： AA=A 交换律：AB= B A AA=A AB= B A结合律：（AB）C= A （BC） （AB）C= A（BC）分配律： A（B C）= （AB） （AC） A（B C）= （AB） （AC）同一律： A= A AU= A33零律：

9、AU=U A=否定律： A A =U A A=吸收律： A（ A B）= A A（ A B）= A德摩根律： （ A B）= AB （ A B）= AB对合律： （ A）= A =U U=34对集合恒等式的说明在不含 和+ 的集合恒等式中，将 和 互换， 和 U 互换，得到的仍然是集合恒等式。 将不含 、 和 的命题逻辑等值式中的 换为 ， 换为 ， 换为 ，0 换为 ，1 换为 U， 换为 = ，就得到集合恒等式。 35 除了上述性质外，常用的性质还有 A-B=AB和下面两个性质定理定理：设A和B是全集U的子集，B=A 当且仅当 AB=U和AB=证明：必要性 若B=A ，则AB= AA= U

10、AB = A A = 充分性 若AB=U和AB =，则B= U B = （A A） B= （A B ）（A B）=（AB）= （A A） （A B）= A （AB）=A U= A 36定理：设A和B是全集U的子集，下列四个命题等价：（1）AB（2）AB=B（3）AB=A（4）A-B=证明：（1）（2） （3） （4） （1）37（1）（2）：对于任意x，由“”定义可知x B，x AB，因此B AB对于任意x， x ABxA x B xB x BxB所以 AB=B（2） （3）： AB= A（AB）=A （吸收律）（3） （4）：A-B= （AB）-B= AB B=（4） （1）：反证法， 假设

11、AB不成立，则存在 x，xA但xB，因此xA-B，即A-B，与已知 条件（4）矛盾。故必有AB 该定理常用于证明两个集合的包含关系。38例：设A，B，C是任意集合，试证： 若AB且CD ，则ACBD证明：因为AB且CD ，则AB=B 且 C D= D （四个等价命题） AB C D= B D 即（ A C）（B D）= B D 所以 ACBD （四个等价命题）39证明两个集合相等常用以下两种方法：（1）集合相等定义 （2）集合恒等式40例：试证：A(BC)(AB)(AC)。证明 ：方法一，对任意x, xA(BC) xAx (B C) xA(xB C) xA(xB x C) xA(x BxC)

12、(xAxB) (xAxC) xABxA C x(AB) (A C)所以，A(B C)(AB) (A C) 。 41例： 试证：A(BC)(AB)(AC)。证明 ：方法二 A(BC) A(BC)A(BC)德摩根律(AA)(BC)幂等律(AB)(AC)结合律，交换律(AB)(AC) 42例 设A,B,C是任意集合, 试证： (A-B) +B=(A-B)B证明：（A-B）+ B=(A-B)-B)(B-(A-B) (“+” 定义)=（ABB)(B(AB) =(AB)(B(BA)=（A-B）B （吸收律） 435.5 有穷集的计数原理 引理5.1：若A和B是有穷集合，且AB，则 （AB)= AB 定理5

13、.12：若A和B是有穷集合，则 （AB)= AB （AB)证明： 显然AB和AB是有穷集。 AB= BA =（BA）（B B) = B (A B) （分配律）44由于B (A B) ，根据引理5.1得（AB)B（AB) (1)又 AA(B B) (AB) (A B) （分配律） 同样(AB) (A B) ，根据引理5.1得 A（AB) （AB) （AB)A- （AB)代入(1)式得 （AB) A+ B -（AB)45推论：若A，B和C是有穷集合，则 （AB C)ABC (AB) (AC)(BC) （AB C)有穷集合计数问题的求解，可利用上述定理或推论，还可利用文氏图和代数相结合的方法。举例如

14、下：46例：外语系120名学生中，其中有100名学生至少学习英语、德语、法语这三门外语中的一种，有65人学英语，45人学德语，42人学法语，20人既学英语又学德语，25人既学英语又学法语，15人既学德语又学法语。求同时学这三种外语的人数和仅学其中一门外语的人数。解：方法一 。 （EG F)EGF (EG)(EF)(GF)（EG F) , 其中（EG F) =100,E=65,G=45,F=42， (EG)=20,(EF)=25,(GF)=15，因此得 (EG F)=8,即同时学三种外语有8人仅学英语和德语的人数为208=12，仅学英语和法语的人数为258=17，仅学德语和法语的人数为158=7

15、,因此仅学其中一门外语的人数为100-12-17-7-8=5647方法二设同时学这三种外语的人数为x，仅学英语、德语、法语的学生人数分别为y1,y2,y3 。因此，仅学英语和德语的人数为20 x仅学英语和法语的人数为25x仅学德语和法语的人数为15x由学英语的有65人得 y120 xx25x65,由学德语的有45人得 y220 xx15x45,由学法语的有42人得 y325xx15x42,y120 xx25xy215xy310048 解方程组得： x8 ，y128, y218, y310 因此，同时学这三门外语的有8人， 仅学这三门外语中一门的有28181056人。 495.6 集合的归纳定义

16、法前面介绍了集合的表示方法有 1. 枚举法：常用于有穷集合的表示。2. 抽象法：用于有穷集或无穷集的表示。但抽象法表示集合时，有时不可能清楚地表示某些 集合。例如算术表达式集合，某高级语言程序集合等等，这时可用集合归纳定义法来描述。502.归纳语句：规定由已知元素构成集合中新元素的规则（集合生成算法） 一般表述为“若x,y,z,是集合中的元素，则根据某些规则进行有限次的组合，其结果也是集合中的元素”。3.极限语句：限定集合的范围。（是满足1和2的最小集合，注：这步有时省略）一般表述为“只有有限次应用基础语句和归纳语句得到的元素才是该集合中的元素”。集合的归纳定义有三部分组成 1.基础语句：规定

17、集合生成元（集合的原子元素），表明集合非空。51例：非负偶数集合 E=xx0y(yI x=2y)或E=x y(yN x=2y) E的归纳定义如下： . 0 E . 若n E，则(n+2 )E . 只有有限次应用、得到的数才是E中的元素。例：求下列归纳定义的集合P .3 P .若x,yP,则(x+y)P .只有有限次应用. 得到的元素才在P中。 显然，P是由3的倍数的正整数组成。52字符串在计算机科学中有重要作用，下面引入有关术语字母表是字母(或称符号)的非空有限集合，通常记作。字母表上的字符串是由中的字母所组成的有穷序列。字符串长度 ：字符串x所含字母的个数，称为字符串。x的长度,记作|x|，

18、例如：| ab |=2 , | an | = n 。若|x|=0，则称x为空串，记做。53字符串相等：设 x 和y 是任意两个字符串，则 x =y 当且仅当 | x | = | y |，并且组成x的诸字符与组成y的诸字符依次相同。例如：若x = ab,y= ab, 则x=y；若x= ab, y= ba, 则x y。 字符串的连接：设是一个字母表，x、y是 上的字符串， x=a1a2 an ， y=b1 b2 bn ，x和y的连接记作xy，xy = a1 a2 an b1 b2 bn 。特别地： x = x=x， n个x的连接记作xn ， x0= ，x n+1 = xn x。显然：| xy |

19、= | x | + | y | ，字符串的连接运算满足结合律。 54设 x ，y，z是任意字符串，则称 x是字符串xy的前缀， y是后缀。称 x ，y，z分别是字符串 xyz的子串。是每个字符串的前缀、后缀、子串。若x 是 y 的子串（前缀，后缀）并且xy ，则称x是y 的真子串（真前缀，真后缀）上的所有字符串构成的集合记做 * ，其归纳法定义如下：（1） * （2）若x *和a ，则xa *（3） *中的每一个元素都可通过有限次应用上述（1）、（2）规则得到。55上的语言： *的子集例如：a，ab，cba，bba 是 =a，b，c上的语言。语言的运算如下：语言的乘积（连接）：设A和B是上的语

20、言， A和B的乘积记作 AB ， AB=zx y ( z=xy x Ay B) 例：A=，a，ab，B=a，bb，则AB=a，bb，aa，abb，aba，abbb语言的幂运算An :（ 1）A0=,（2）An+1=AnA, nN语言的闭包运算A* :A* =A A2A的正闭包A+ ：A+ =A A2例：令 B=a，bb，则B2 =aa，abb，bba，bbbbB* =，a，bb， aa，abb，bba，bbbb， 56定理：设A、B、C、D是上的任意语言，则下列关系成立：A =A =A= A =A(AB)C=A(BC)若AB和CD, 则AC BDA(BC)=ABAC(BC) A =BACAA(

21、BC) ABAC(BC) A BACA57试证：若AB和CD, 则AC BD证明：对于任意zzAC x y ( z=xy x Ay C)x y ( z=xy x B (y D) (AB和CD ) z BD所以， AC BD58证明A(BC)=ABAC证明：对于任意zzA（B C) x y（ z=xy x Ay (BC) x y （ z=xy x A(y B y C) x y (（ z=xy x Ay B) (z=xy x A y C) x y (（ z=xy x Ay B) x y (z=xy x A y C) zAB zAC zAB AC 59定理：设A、B是上的任意语言，m、n是任意自然数

22、，则下列关系成立：（1）Am An =Am+n（2）（ Am ） n =Amn（3）若AB则An Bn 定理：设A、B是上的任意语言，nN，则下列关系成立：（1）A* =A+ （2）AnA* ，n0（3）An A + ， n160（4）AAB*（5） AB*A（6）若 AB，则 A*B*（7）若AB， 则A+ B+（8）AA* = A*A =A+ （9） 若 A，则 A* = A+ （10）（ A* ）* =A* A*=A* （11）（ A* ）* =（A+ ） *=A* （12）（ A +）+ =A+ 证明略。61 5.7 有序偶和笛卡儿乘积 掌握有序偶和笛卡儿乘积的定义和性质 熟练掌握求两

23、个集合的笛卡儿乘积62定义5.22：（有序偶）任给两个对象x和y，将它们按规定的顺序构成的序列，称之为有序偶，记为 x，y 。其中x称为有序偶的第一元，y称为第二元。 显然有序偶与二元集在概念和性质上都有根本的不同。如： a，b b，a a，a a 而 a，b = b，a a，a = a 63 1921年波兰数学家库拉托夫斯基（Kuratovski）给出了一种有序偶的集合表示 x，y = x ， x，y 。 定理5.16 有序偶的唯一性定理： u，v = x，y ，当且仅当u=x和v=y。证：充分性 当u=x，v=y时，有 u = x 和 u，v = x，y ， 因此有 u ， u，v = x ， x，y 。 即 u，v = x，y 64 必要性 分两种情况来证u=