离散数学讲义

1、离散数学讲义离散数学讲义数学教研室李家林制作数学教研室李家林制作离散数学绪论离散数学绪论 离散数学是计算机科学中基础理论的核心课程离散数学是计算机科学中基础理论的核心课程离散数学以研究离散量相互间的关系为主要目标离散数学以研究离散量相互间的关系为主要目标,其其研究的主要对象一般是有限或可数个元素构成的集研究的主要对象一般是有限或可数个元素构成的集合合.因此它充分地描述了计算机科学离散性的特点因此它充分地描述了计算机科学离散性的特点. 离散数学对计算机科学与技术的发展离散数学对计算机科学与技术的发展,一直起着一直起着重要的作用重要的作用. 在计算机科学中普遍采用了离散数学中在计算机科学中普遍采用

2、了离散数学中的基本概念的基本概念,基本思想和基本方法基本思想和基本方法.把离散数学作为自把离散数学作为自己的理论和重要的数学工具己的理论和重要的数学工具;同时又不断地给离散数同时又不断地给离散数学提出一些新的课题学提出一些新的课题. 此外此外,离散数学在计算机科学与技术的教育中离散数学在计算机科学与技术的教育中也是一门必不可少的课程也是一门必不可少的课程.它不仅是计算机的专业它不仅是计算机的专业基础课基础课,是数据结构是数据结构,操作系统操作系统,编译原理编译原理,数据库原数据库原理以及人工智能的必备基础理以及人工智能的必备基础,而且对培养同学们的而且对培养同学们的抽象思维和逻辑推理能力有重要

3、的作用。抽象思维和逻辑推理能力有重要的作用。 离散数学以集合论、代数系统、图论、数理逻离散数学以集合论、代数系统、图论、数理逻辑为主要内容。辑为主要内容。1.1 集合集合a.概念概念 集合是数学中最基本的概念集合是数学中最基本的概念,只给予一种描述只给予一种描述:把一些确定的、彼此不同的事物作为一个整体来考虑把一些确定的、彼此不同的事物作为一个整体来考虑时时,这个整体称为一个这个整体称为一个集合集合.集合中的事物即个体称为集合中的事物即个体称为元素元素. 注意两点注意两点:1.每个元素一般各不相同每个元素一般各不相同; 2.每个元素有确定的性质每个元素有确定的性质.几个常见的集合的表示符号几个

4、常见的集合的表示符号:N: 自然数集自然数集 1, 2 ,3 ,Z: 非负整数集非负整数集 0, 1, 2 ,3 ,I: 整数集整数集 0,-1, 1, -2, 2 , -3, 3 ,P: 素数集素数集(只能被只能被1和自身整除和自身整除,不能被其他正不能被其他正 整数整除的大于整数整除的大于1的正整数称为素数的正整数称为素数)Nm (m1 ) :1, 2 , 3 ,mZm (m1) : 0, 1, 2 , 3 , m-1R: 全体实数全体实数.C: 全体复数全体复数(形如形如a+bi的数的数, aR, bR)Q: 全体有理数全体有理数(形如形如i/j的数的数, iI, jI )b.集合的表示

5、法集合的表示法: 1. 列举法列举法: 把集合的元素按任意顺序写在一个花把集合的元素按任意顺序写在一个花括号里括号里,并用逗号分开的方法称为列举法并用逗号分开的方法称为列举法.有限集及有限集及可数集可以用这种方法表示可数集可以用这种方法表示. 2. 描述法描述法: 将集合中的元素以定义的形式给出的将集合中的元素以定义的形式给出的.即给定一个条件即给定一个条件p(x),当且仅当当且仅当a使条件使条件p(x)成立时成立时,aA.一般形式一般形式A=a | p(a) . p(a) 描述了一个规则或描述了一个规则或公式公式.表示的意义可以非常广泛表示的意义可以非常广泛. 如如 S =a| aI , 且

6、且4a14. 又如又如B=a| a是中国是中国的省会城市的省会城市. 注意注意:用描述法表示集合用描述法表示集合,其方式并不是唯一的其方式并不是唯一的.c.关于集合中的悖论关于集合中的悖论:一般集合元素无限制一般集合元素无限制,元素本身也可是集合元素本身也可是集合.如如. A=3,1,2,1,d,q,B=1,3,1,3最重要的是把集合最重要的是把集合a元素元素a区别开区别开.如集合如集合qA.而而q是是q 的元素的元素, qq,但但q不是不是A的元素的元素. q是是q AdAdddAdAqAq ,；但但，还还有有，且且也也不不能能有有例例: 指明下列命题的真假指明下列命题的真假: 设设S=2,

7、a,3,4, R= a,3,4,1 1.aS; 2. aR ; 3. a,3,4,1 R; 4.S=R.1. 否否; 2. 对对; 3.对对; 4.否否. 要注意不能使用要注意不能使用“包含一切集合的集合包含一切集合的集合”之类的之类的语语言言.否则会导致矛盾否则会导致矛盾.下面是著名的罗素悖论下面是著名的罗素悖论: 设设c集合的集合集合的集合:使使c=A|A是一个集合是一个集合,A A那么那么cc,还是还是c c呢呢?(罗素悖论罗素悖论). 因为若因为若cc,由由c的定义的定义c c,若若c c由由c的定义的定义cc.显然这样的显然这样的c是不存在的是不存在的. 还有一个更通俗的例还有一个更

8、通俗的例:一个小镇上有一个理发师一个小镇上有一个理发师他他只给那些不为自己理发的人理发只给那些不为自己理发的人理发.(其余的人他都不理其余的人他都不理发发).这个悖论说的是理发师的头无论由谁理都是矛盾这个悖论说的是理发师的头无论由谁理都是矛盾.d.基数基数: 定义定义1: 不含任何元素的集合称为空集不含任何元素的集合称为空集.记为记为.我们要证明命题我们要证明命题p(x )对一切对一切x不真不真.可证可证x|p(x)= . 定义定义2: 集合集合A中不同元素的数目称为集合中不同元素的数目称为集合A的基的基数数.记为记为 A. 当当 A为有限数时为有限数时,称称A为有限集为有限集.否则称否则称A

9、为无限为无限集集.更详细的以后再讨论更详细的以后再讨论.1.2集合的包含和相等集合的包含和相等 定义定义1: A. B为二集合为二集合,A中的每一元素均在中的每一元素均在B中中,称称B包含包含A;或或A含于含于B.记为记为A B. 若若A B ,且且B A. 称称A与与B相等相等,记为记为A=B. 例例A=a.b.c, B=a.b.c,a,b,c, A B且且AB.此例此例说明包含说明包含 、属于并不是相排斥的、属于并不是相排斥的. 定义定义2: A. B为二集合为二集合, A B且且AB.称称A是是B的真的真子集子集. 定理定理1: 空集是任何集合的子集空集是任何集合的子集.(反证法反证法,

10、注意否定注意否定定义定义) 定理定理2: 空集是唯一的空集是唯一的. ( 假设有两个假设有两个,证明这两个证明这两个相等相等). 1.3 幂集幂集 定义定义: 集合集合A的所有子集构成的集合称为的所有子集构成的集合称为A的幂集的幂集.记为记为2A. 例例 写出集合写出集合A=1,2,3的幂集的幂集 定理定理 若若A是有限集是有限集,且且A = n,则则2 A=2 A=2n nkknnknknkknncyxyxcyx0021，有有令令）证证明明：（ 我们注意到集合我们注意到集合A 中元素为中元素为k个的子集恰有个的子集恰有 个个.于是于是 2A= =2n=2 (A)knc nKknc0关于幂集的

11、二进制表示关于幂集的二进制表示: 当当A的元素较多时的元素较多时,无遗漏的无遗漏的A较困难较困难,下面引进一下面引进一种表示法可以无遗漏的表出种表示法可以无遗漏的表出2A的每一元素的每一元素.为此为此,我们我们不妨对所给集合规定某种次序不妨对所给集合规定某种次序,即给该集合中的每个即给该集合中的每个元素附加一个标号元素附加一个标号,以使描述这个元素在该集合中的以使描述这个元素在该集合中的相应位置相应位置.如如A=a,b,c分别是一、二、三元素，在分别是一、二、三元素，在A的子集中，常有一些元素出现，另一些元素不出现。的子集中，常有一些元素出现，另一些元素不出现。 我们根据这一情况来指定集合中元

12、素的次序我们根据这一情况来指定集合中元素的次序,用用如下方式表示如下方式表示.如如A的各子集表为的各子集表为:B000=, B 001=c, B010=b, B011=b,c, B100=a,B101=a,c, B110=a,b, B111=a,b,c 则有则有2A=B000, B 001, B010, B011, B100, B101, B110, B111 = B0, B 1, B2, B3, B4, B5, B6, B7 其中前一括号其中前一括号B的下标是三位二进制数的下标是三位二进制数,每一每一位对应集合位对应集合A中的一个元素中的一个元素,左边的第一位是左边的第一位是1还是还是0表表

13、A中元素中元素a在子集中出现与否在子集中出现与否.第二第二.三位刻划三位刻划b.c是否在是否在A的子集中是否出现的子集中是否出现.在此意义下在此意义下,A的子集的子集可由可由000111中的一个数来表示中的一个数来表示. 若设集合若设集合J=j|j是二进制数是二进制数000j111,则有则有2A=Bj| jJ,这里主要是下标确定子集元素这里主要是下标确定子集元素,与表示与表示子集用的字母子集用的字母B无关无关. 一般地一般地,表示任意表示任意n个元素的各个子集个元素的各个子集,用来表示这些用来表示这些子集的下标是十进制数子集的下标是十进制数02n-1的二进制表示的二进制表示,为了凑足为了凑足n

14、个数位个数位,一定要在这些二进制数左边添入所需个数的零一定要在这些二进制数左边添入所需个数的零.我们也可以用从我们也可以用从02n-1的十进制数来作为子集的下标的十进制数来作为子集的下标.而只在要确定所对应子集的元素时才转换为二进制数而只在要确定所对应子集的元素时才转换为二进制数. 令令A=a1 ,a2, a3, a4,a5 ,a6而而2A有有64个元素个元素,我们可称为我们可称为B0, B1, B2, ,A中的子集的各元素是如何确定的中的子集的各元素是如何确定的呢呢? 如如B7=B000111=a4 ,a5 ,a6 B12=B001100=a3 ,a4.126B而而a2 ,a4=B01010

15、0= (010100)2 =(22 +24 )10 例例:若若B C, 则则2B 2C成立与否成立与否?讨论讨论: 该结论是正确的该结论是正确的.证明如下证明如下: 任意任意x2B ,即即x B可有可有x C,即即x2C 所以所以2B 2C202224BB1.4 集合的运算集合的运算一一.全集全集定义定义1: 若某集包含了某个问题所论及的一切对象若某集包含了某个问题所论及的一切对象.称该集为全集称该集为全集.记为记为U. 全集因所讨论的问题不同可相异全集因所讨论的问题不同可相异.例如例如: 讨论正整数范围内讨论正整数范围内U可取作可取作N;实数讨论问题实数讨论问题U可取可取作作R. 定义定义2

16、: 设设A.B为二集合为二集合.属于属于A或或B的所有元素构的所有元素构成的集合称为成的集合称为A与与B的并的并.记为记为AB.即即 AB=u | uAoruB 既属于既属于A又属于又属于B的所有元素构成的集合称为的所有元素构成的集合称为A与与B的交的交. 记为记为AB.即即 AB=u | uA且且uB 例例 ( 略略) 若若AB=,称称A.B不相交不相交.如如A1 =1,2,3 A2=1,2,3 A3=1,1,2 则则Aj Ai= 基本运算规律基本运算规律: 1.A AB B AB A AB B AB 2. 若若 A B, 则则 A=AB B=AB 定义定义3: 设设A.B为二集合为二集合.

17、属于属于B而不属于而不属于A 的元素构成的元素构成的集合的集合,称为称为A关于关于B的相对补集的相对补集.记为记为BA. 即即BA=u|u B ，u ABA也称为也称为B与与A的差集的差集. 例如例如 A=3,4,6,7 B=1,2,3,4 则则 B A =1,2 A - B =6,7定义定义4: A关于全集关于全集U的相对补集的相对补集.称为称为A的绝对补集的绝对补集.记为记为A. A=U A=u|uU，u A 例例: U=Z A=2K| KZ A=U-A=2K+1|K Z U = =U定义定义5 设设 是集合是集合U的一组子集的一组子集,把对把对,A1,A2, Ar ,U 任意施加任意施加

18、“”“”“”运算有限次而产生的运算有限次而产生的集合集合 称为由称为由A1,A2, Ar ,所产生的集合所产生的集合.,U,A(B C)等均为等均为A.B.C所产生的集合所产生的集合.例例:设设A.B是任意集合是任意集合,等式等式2A-B=2A-2B能否成立能否成立? 解解: 如如A=a,c B=b,c 有有A-B=a , 2 A-B=,a 2A=,a,c,a,c 2B= ,b,c,b,c 2A-2B= a,a,c 与与2A-B互不包含互不包含.进一步可看到进一步可看到:riiA12A 2B 但但2A-B 所以所以 2A-B 2A-2B 进一步探讨进一步探讨: 2A-B 2A-2B 一般也不成

19、立一般也不成立,如如s 2A-2B 有有s 2A , s 2B s A , s B .但但s中可能有元素中可能有元素在在(只要求不是所有元素都在只要求不是所有元素都在B中中) 如可能有如可能有y s, y B则则s A-B(S中可能有中可能有B的元素的元素) 即即s 2A-B . 所以所以 2A-B 2A-2B也不成立也不成立 参阅参阅P32习题习题16BA22 1.5文氏图文氏图 文氏图是用来表示集合关系及运算的示意图文氏图是用来表示集合关系及运算的示意图.全集全集U用矩形区域来表示用矩形区域来表示,U的子集在文图中用圆形来表示的子集在文图中用圆形来表示,ABBA直观上直观上: BABAAA

20、ABBAABBA)(AB 文图对较复杂的运算及关系反映不甚准确文图对较复杂的运算及关系反映不甚准确,(有时有时关系较多不易想清楚关系较多不易想清楚,文图用来证明关于集合的命题文图用来证明关于集合的命题也不合适只能起提示作用也不合适只能起提示作用).如下图如下图A B = (A B ) (B A ) (A B) (1.2)A B = (A B ) (B A ) (3)因此不能说因此不能说(1.2)式与式与(3)式总是相等的式总是相等的.ABABAB(1)(2)(3) 1.6集合成员表集合成员表 前面定义的集合运算的交前面定义的集合运算的交.并并.补补.显然对全集显然对全集U运算运算是封闭的是封闭

21、的.下面对这些概念以新的形式定义下面对这些概念以新的形式定义,使之数量使之数量化化.能够更新能够更新,更清晰更清晰,更具理论价值更具理论价值.先讨论基本成员表先讨论基本成员表. a.集合集合A的补集可如下定义的补集可如下定义: A的成员表的成员表 A A 0 1 1 0AuAuAuAu 则则若若则则若若 对集合对集合S(AorA)所在的列中所在的列中,数字数字0或或1表示元素表示元素u不属于不属于S或或u属于属于S. b.集合集合A与与B的并集可如下定义的并集可如下定义: A B的成员表的成员表 A B A B 0 0 0 0 1 1 1 0 1 1 1 1BAuBuAuBAuBuAuBAuB

22、uAuBAuBuAu 则则，若若则则，若若则则，若若则则，若若C .集合集合A与与B的交集可如下定义的交集可如下定义: A B的成员表的成员表 A B A B 0 0 0 0 1 0 1 0 0 表中反映元素是否属于表中反映元素是否属于A.B交交. 并的情形并的情形 . 1 1 1.BAuBuAuBAuBuAuBAuBuAuBAuBuAu 则则，若若则则，若若则则，若若则则，若若 A.,B产生的集合成员表产生的集合成员表.可以推广到可以推广到A1,A2, Ar 所产生的集所产生的集 合合S上去上去,一般由一般由A1,A2, Ar 所产生的集合所产生的集合S的成员表具体的成员表具体表示如下表示如

23、下: 该成员表的前该成员表的前r列标记列标记 A1,A2, Ar ,最后一列标记最后一列标记为为S ; 标记为标记为Ai的列中数字的列中数字1表示表示u Ai,数字数字0表示表示u Ai,若若在第在第K行上。前行上。前r列所指明的条件有列所指明的条件有u S ,则在则在S的位置的位置(第第S列第列第K行行)记记0.否则否则uS,则在则在S的位置的位置(第第S列第列第K行行)记记1. 集合成员表共有集合成员表共有2r行行,它相应于它相应于A1,A2, Ar 中的中的2r种可能种可能成员成员/非成员情况非成员情况.为简化为简化,有时把标记有时把标记A1,A2, Ar 列中的一行列中的一行标记数字标

24、记数字1,2,3,r(i1或或0)称为行称为行1,2,3,r.下面给出下面给出 S=(AB)(AC)(BC)的成员表的成员表. S=(AB)(AC)(BC) A B C A AB A C BC(AB) (A C) S 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 上表中S是由A.B.C产生的集合,S的成员表构造其中的前r列列出了A.B.C八种可能成员/非成

25、员的情况.而最后一列列出了u在S中的成员/非成员的情况,这一列是通 过集合A, AB, A C, BC,(AB) (A C)的中的成员表相继构造出来的,除前三列外,后面的每一列都是由前面的列参照, 成员表构造出来的. 关于表的说明关于表的说明: 若某列记值全为若某列记值全为0,则该列对应的集合为空集则该列对应的集合为空集.若全若全为为1,则该列对应的集合为全集则该列对应的集合为全集U,如果成员表中两列标如果成员表中两列标记的集合记的集合T.S全相同全相同.这时这时S.T相互重合相互重合.S=T. 前表中前表中(AB) (A C) = (AB)(AC)(BC) 于是集合成员表可用来证明集合相等于

26、是集合成员表可用来证明集合相等,包含包含.S与与T对对应的两列应的两列,S的列对应的列对应1对于对于T也是也是1,而而T中的中的1S不一定是不一定是1,这时这时 . 练习练习:1.用两种方法证明用两种方法证明:A(BC)=(AB)(AC) 2. 判断判断A(BC)=(AB)C能否成立能否成立? (可画文图讨论可画文图讨论)（1。7略）略）ST 定义定义1: 设设=AiiK是集合是集合A的某些非空子集的集合的某些非空子集的集合.如果集合如果集合A的每一元素在且只在其中的某一的每一元素在且只在其中的某一Ai中即若中即若 1).AiAj = i j i, jK 2). 则称集合则称集合是集合是集合A

27、的一个分划的一个分划.而每个而每个Ai称为这个分称为这个分划的分划块划的分划块. 例例: A=1,2,3 则则 1=1,2,3 ;2=1,2,33=2,1,3 4=3,1,2 5=1,2,3均为均为A的的分划分划,分划一般不是唯一的分划一般不是唯一的.AAKii 1. 8分划分划例例: A=I(整数集整数集,A是是A中被中被5除余数为除余数为i的所有整数的的所有整数的集合集合) 则则 A0=-10, -5, 0, 5, 10 A1=-9,-4, 1, 6, 11 A2= -8, -3, 2, 7,12 A3=-7, -2, 3, 8, 13 A4=-6, -1,4, 9, 14 构成的集合构成

28、的集合A的一个的一个分划分划,由于被由于被5除的每一整数余数唯一除的每一整数余数唯一,所以所以A中的每中的每一元素在且只在某一一元素在且只在某一Ai中中, 即上述元素构成的集合是即上述元素构成的集合是A的一个分划的一个分划.定义定义: 设设 与与 均为均为A的分划的分划,如果如果中的每一中的每一Ai 都是都是中的某一个中的某一个Aj的子集，则的子集，则称分划是分划的一个细分称分划是分划的一个细分; 若若是是的细分的细分,且且中中至少有一个至少有一个Ai 为某个为某个Aj的真子的真子 集集, 则称则称是是的的真细分真细分. 分划全集分划全集U常用常用,事实上分划是事实上分划是U划分分界线划分分界

29、线,若分划若分划的分界线是在分划已有的分界线上添加新的分界线的分界线是在分划已有的分界线上添加新的分界线,则则是是 的真细分的真细分. 练习练习: 1).P33.习题习题25. 2).在在11000000之间之间,(包括包括1和和1000000)有多少整有多少整数既不是平方数数既不是平方数,也不是立方数也不是立方数.KiiAKiiA解解: 设设S=x| xN且且1x1000000 A=x| xS且且x是完全平方数是完全平方数. B=x| xS且且x是完全立方数是完全立方数.则则S=1000000 A=1000 B=100 (AB)=10 (AB) = S - ( A+ B)+ (AB) =10

30、0000-(1000+100)+10 =998910(注意到注意到1000000=10002=1003 确定确定A与与B,最后最后的等式可由文图确定的等式可由文图确定) 1.9 集合的标准形式集合的标准形式一一.最小集的标准形式最小集的标准形式 定义定义: 设设A1,A2, Ar 是全集是全集U的子集的子集,形如形如 的集合称为由的集合称为由A1,A2, Ar所产生的最小集所产生的最小集,其中每个其中每个 为为Ai 或或Ai (注意每个注意每个 中中Ai 或或Ai至少出现且只至少出现且只出现一个出现一个). 例如由例如由A.B.C产生的最小集为产生的最小集为:A B C A BC A BC A

31、 BC A BC A B C ABC AB 由乘法原理及定义知由乘法原理及定义知:由由A1,A2, Ar所产生的最小集所产生的最小集共有共有2r个个.仔细观察下列两图仔细观察下列两图.iriA1iAiA ABCABC ABCABCABCABCABCABC ABCABC ABCABCABC =ABC =ABCABC=定理定理1: 由由A1,A2, Ar 所产生的非空最小集的集合构成所产生的非空最小集的集合构成U的一个分划的一个分划.证明证明: 只证只证 1). (其中其中Si是由是由A1,A2, Ar 所产生的最小集所产生的最小集i=1,2,2r) 2).SiSj= ij 证证: 1)只证只证

32、U Si 并集符号上的上下标省略并集符号上的上下标省略.任任意意u U, 则则uA1或或uA1 u Ai或或 uAi.所以必有所以必有 u 是某个是某个Sjo ，所以，所以U 1)成立成立.Usiir21iriA1iisr212).反证法反证法: 设设uU uS1S2 S1 , .S2是是A1,A2, Ar 所产生的两个所产生的两个不同不同的最小集的最小集,则必存在一个则必存在一个i0(1 i0r)使使uAi0, 同时同时uAi0(S1 与与S2中对应因子至少有一个中对应因子至少有一个不同不同), 但这与但这与Ai0Ai0=矛盾矛盾,所以所以SiSj= ij 所以由所以由A1,A2, Ar 所

33、产生的非空最小集的集合构成所产生的非空最小集的集合构成U的一个分划的一个分划.证毕证毕 为了讨论方便为了讨论方便,我们用我们用 表示最小集表示最小集 ,其中其中如如A1A2A3 A4=M1101rM 21 rAAA21 iiiiiAAAA当当当当10 A1A2A3A4=M0011 ,显然显然 表最表最小集是唯一的小集是唯一的. 关于最小集的成员表关于最小集的成员表 对于任一最小集对于任一最小集 = 的的 成员表中成员表中,由由定义可知定义可知:当且仅当当且仅当时时u ,故在最小集故在最小集 中中,对应所标记对应所标记的列中有且只有一个的列中有且只有一个1,其余均为其余均为0.(观察成员表观察成

34、员表) 因为成员表的前因为成员表的前r列列A1,A2, Ar 中取中取0,1值值,恒为恒为 对对应应Ai与与Ai,故每一行对应一个最小集故每一行对应一个最小集. A1,A2, Ar 中取中取0,1值对应值对应123r,相应的最小集相应的最小集 在在rM21rM21iriA1rAuAuAu,21rM21rM21iArM21行行123r取值为取值为1,其余行为其余行为0,如表如表A B C A AB C A BC AB CABC S =M001 =M011 =M110 =M111 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1

35、 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 1 1其中其中S=M001M011M110M111. 标记的列中只有一个标记的列中只有一个1,只在只在123r取值为取值为1,其余行为其余行为0, 理论上及实际计算都有这个结果理论上及实际计算都有这个结果.如如最小集最小集M001=ABC当且仅当当且仅当uB,uA, uC,rM21uM110,这时这时M110所处的列中仅在行所处的列中仅在行110处取处取1,而其余而其余行均为行均为0. 进一步研究由进一步研究由A1,A2, Ar 所产

36、生所产生i个个(i2r)不同的最小不同的最小集的并集集的并集(集合构造集合构造): 并集并集及其成员表及其成员表:作出其列为作出其列为A1,A2, Ar ,(j=1,2,i)及及 所标记的成员所标记的成员表表.jrjjirirrMMMMij 211221112111 jrjjM 21jijjMij 211 其中最后一列由前其中最后一列由前i列借助运算列借助运算得到得到.参阅前表可知参阅前表可知,上述并集所对应的列仅在上述并集所对应的列仅在11 2r,21 2r,i1ir这这i,行处为行处为1,其余行为其余行为0.上表还表明成员表上表还表明成员表S的构造的构造.其中其中 S=(ABC)(ABC)

37、(ABC)(ABC)定理定理2 由由A1,A2, Ar 所产生每个非空集所产生每个非空集S恒可表示为若恒可表示为若干个不同的最小集的并集干个不同的最小集的并集.证明证明 S,因此因此S的成员表中所对应的列必有的成员表中所对应的列必有L个个1,其其中中1L2r ,设这设这L个个1分别在行分别在行11 2r, 21 2r, L1 Lr,作如下最小集之并作如下最小集之并,用用T表示表示:T=将将T植于成员表的最后一列可知植于成员表的最后一列可知,这必有与这必有与S所在的列恒同所在的列恒同.LrLirrMMM 122111211即即T=S.证毕证毕 定理的证明不仅说明由定理的证明不仅说明由A1,A2,

38、 Ar 所产生每个非所产生每个非空集空集S恒可表示为若干个不同的最小集的并集恒可表示为若干个不同的最小集的并集.还指明还指明找到是哪些最小集的并找到是哪些最小集的并. 练习练习:作出作出(AB)(AC)的成员表，并求其最小的成员表，并求其最小集的标准形式。集的标准形式。如如(AB)(AC)所标记的列所标记的列(可算出可算出)在行在行001,011,110,111处取处取1故故: (AB)(AC)=M001M011M110M111= (ABC)(ABC)(ABC)(ABC)二二.最大集的标准形式最大集的标准形式 定义定义: 设设A1,A2, Ar 是全集是全集U的子集的子集,形如形如 的集合称为

39、由的集合称为由A1,A2, Ar所产生的最大集所产生的最大集,其中每个其中每个 为为Ai 或或Ai (注意每个注意每个 中中Ai 或或Ai至少出现且只至少出现且只出现一个出现一个). 例如由例如由A.B.C产生的最大集为产生的最大集为:A B C A BC A BC A BC A BC A B C ABC ABC由乘法原理及定义知由乘法原理及定义知:由由A1,A2, Ar所产生的最大集所产生的最大集共有共有2r个个.但所有的最大集不能构成但所有的最大集不能构成U的分划的分划,交集非空交集非空.iriA1iAiA一般用一般用 表示最大集表示最大集 如如A1A2A3A4= A1A2A3A4 = 一

40、般一般下面讨论最大集的成员表下面讨论最大集的成员表: 按并集定义按并集定义 = 当且仅当当且仅当故故 只在行只在行123r处取处取0,而其余行处而其余行处取取1,如对如对 仅当仅当uA(记记0) uB(记记1)uC (记记0) 时时, u =A B C,故只在行故只在行010处取处取0,而其余而其余行都取行都取1,参阅下表参阅下表rM21rAAA210011M0010iiiiiAAAA10当当rM21iriA1rMuAuAur211,rM21010M010M下面看下面看 成员成员 表表A B C ABC A BC A BCAB C S =M000 =M010 =M100 =M101 0 0 0

41、 0 1 1 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1其中其中S=进一步考察进一步考察A1,A2, Ar任意任意i个不同最大集的交个不同最大集的交101100010000MMMM101100010000MMMMirirrMMM122111211及其成员表及其成员表,上述交集仅在行上述交集仅在行111r,212r,i1ir处为处为0,其它行为其它行为1,这也这也表明了构造集合表明了构造集合 (ABC)(ABC

42、)(ABC)(ABC)成员表的方法成员表的方法.定理定理3 由由A1,A2, Ar 所产生任一集合所产生任一集合S或为全集或为由或为全集或为由A1,A2, Ar 所产生的若干不同的最大集的交所产生的若干不同的最大集的交.证明证明: 因此因此S的成员表中所对应的列必有的成员表中所对应的列必有K个个0,不为全集不为全集其中其中1K2r ,设这设这K个个0分别在行分别在行11 2r, 21 2r, K1 Kr,作如下最大集之交作如下最大集之交,用用T表示表示:T=将将T植于成员表的最后一列可知植于成员表的最后一列可知,这必有与这必有与S所在的列恒同所在的列恒同.krkrrMMM122111211则则

43、T=S,若若K=2r 则则T=U例例 求求S=(AB)(AB)最大集的标准形式最大集的标准形式,其中其中S由由A.B.C所产生所产生.解解:S的成员表为的成员表为A B C AB AC (AB)(AB) 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 1 所以所以S=(AB)(AB)=M000M010M100M101三三.关于集合的标准形式的进一步说明关于集合的标准形式的进一步说明: 由前两段的讨论可知由前两段的讨论可知:若把空集看作自身的最若把空集看作自

44、身的最小集的标准形式小集的标准形式(空集不能表为非空集合的并空集不能表为非空集合的并),把把全集全集U看作自身的最大集的标准形式看作自身的最大集的标准形式(全集不能表全集不能表为若干集合的交为若干集合的交),则可说则可说:每个集合都能表为最小每个集合都能表为最小集的标准形式和最大集的标准形式集的标准形式和最大集的标准形式. 讨论集合讨论集合S=B(A(BC)的最大集及最小的最大集及最小集的标准形式集的标准形式,由由A.B.C产生产生.先讨论集合的成员表先讨论集合的成员表:A B C CB A (B C ) B (A (B C ) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1

45、1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 S=M000M001M011M100M101 =(ABC)(ABC)(ABC) (ABC)(ABC)S=M010M110M111(ABC)(ABC)(ABC) 一般一般:若集合若集合S最小集和最大集的标准形式为最小集和最大集的标准形式为 S= S= 则集合则集合=11121r,l1l2 lr的交集为空集的交集为空集. 定理定理4 S是是A1,A2 , Ar产生的集合产生的集合,不记次序不记次序,则其则其最大最大(小小)集的标准形式是唯一的集的标准形式是唯一的. 定理定

46、理5 由由A1,A2 , Ar产生的集合相等的充要条件产生的集合相等的充要条件是它们的最大是它们的最大(小小)集的标准形式是一样的集的标准形式是一样的lrlrrMMM122111211mrmrrMMM122111211,2111211mrmmr下面用运算规律求集合的标准形式下面用运算规律求集合的标准形式:其中其中 S=B(A(BC)1.最小集最小集: S=B(A(BC)=(BA)(BBC) =(BAC) (BAC) (ABC)(ABC) = M111M110M0102.最大集最大集:S=B(A(BC)=(B(AA) (A B)(AC)=(BA)(B A) (A B C) (A B C ) (AB C) (AB C)=(BA C) (BA C)(B A C) (B A C) (A B C) (A B C )(AB C) =M000M001M100 M101 M011这与前面的结果相同这与前面的结果相同.1.P32.16T.2.P33.20T.3.设集合设集合A的基数的基数A=55 ,试问试问: 1.A有多少个子集有多少个子集; 2.有多少个子