离散数学第三章集合.ppt

《离散数学第三章集合.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章集合.ppt（50页珍藏版）》请在三一办公上搜索。

1、2023/9/14,1,第三章 集 合,3.1 集合论基础3.2 集合运算及其性质,2023/9/14,2,例 在一个住着一些人家的僻静孤岛上,岛上只有一个理发师a,a给且只给岛上所有不能自己理发的人理发。问谁给a理发？解:设 S=x|x 是不能自己理发的人。(1)若aS,则a给自己a理发。又由题意知,a只给不能自己理发的人理发,所以a是不能自己理发的人,即aS,矛盾。(2)若aS,则a是不能自己理发的人。又由题意知,a只给集合S中的人理发,所以a要给a理发,即aS,矛盾。无论如何,都有aS和aS同时成立。这是著名的罗素悖论paradox。,2023/9/14,3,集合的特性,集合论依赖于三大

2、基本原理,它们从根本上规定了集合概念的意义。集合的元素一旦给定,这一集合便完全确定,这一事实被形式地叙述为外延性公理。,2023/9/14,4,1.外延(extension)公理-两个集合A和B相等的充分必要条件是它们有相同的元素。外延公理刻划了集合的下列特性:A.互异性:一个集合的各元素是可以互相区分开的,即每一元素只出现一次。B.无序性:集合中元素排列次序无关紧要,即集合表示形式的不唯一性。,2023/9/14,5,2.概括(comprehension)公理-构成一个集合应符合两个要求:I.纯粹性:凡该集合中的元素都具有某种性质II.完备性:凡具有某种性质的元素都在该集合中概括公理规定了集

3、合描述法的理论依据和集合元素的确定性。,2023/9/14,6,C.确定性:任一事物是否属于一个集合,回答是确定的。对于界限不分明的情况,在经典集合论中绝对不容许存在。不确定的事物构成的集合属于模糊(fuzzy)集合的研究范畴。例：“好书”的全体不构成集合,因为难以对每一本书的好坏作出确定的判断。,2023/9/14,7,3.正则(regularity)公理:不存在集合A,B,C,使得 CBA。(即任何一个非空集合都有一个极小元)正则公理的一个自然推论是:对任何集合S,S S(否则有SSS),从而规定了集合S与 S的不同层次性。,2023/9/14,8,集合与其成员是两个截然不同的概念,集合的

4、元素可以是任何具体或抽象事物,包括别的集合,但不能是本集合自身。因为一个集合是由它的成员构成的,是先有成员后才形成集合,所以一个正在形成中的集合便不能作为一个实体充当本集合的成员。否则在概念上将产生循环,从而导致悖论。正则公理也消除了悖论。,2023/9/14,9,3.1 集合论基础,1.集合与元素 所谓集合，是指某些可辨别的不同对象的全体，将用大写字母A，B，X，Y，表示之。组成集合的对象称为集合的元素或成员，将用小写字母a，b，x，y，表示之。a是A的元素或a属于A，记作aA；a不属于A或a不是A的元素，记作aA，或者(aA)。,2023/9/14,10,集合的元素一旦给定，这一集合便完全

5、确立。这一事实被形式地叙述为外延公理。外延公理：两集合A和B相等，当且仅当它们有相同的元素。若A与B相等，记为A=B；否则，记为AB。,2023/9/14,11,外延公理可形式表为：A=B(x)(xAxB)或者A=B(x)(xAxB)(x)(xBxA)顺便指出，在应用外延公理证明集合A与B相等时，只需考察：对于任意元素x，应有下式xAxB成立即可。这就是说，证明两集合相等时可按此法行事。,2023/9/14,12,表示一个特定集合，基本上有两种方法：一是枚举法，在可能时列出它的元素，元素之间用逗号分开，再用花括号括起。如A=a,e,i,o,u表明集合A是由字母a,e,I,o和u为元素构成的。,

6、2023/9/14,13,二是谓词法，用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素，确定了一个集合，因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的谓词公式，则x|P(x)定义了集合S，并可表为S=x|P(x)由此可见，P(c)为真当且仅当cS。从而有xSxP(x),2023/9/14,14,例如，A=a,e,i,o,u 可表为A=x|x是英文字母表中元音字母,2023/9/14,15,应该指出的是：集合的元素可以是具体事物，可以是抽象概念，也可以是集体，不是集合的元素称为本元。如，一本书，一支笔，集合1,2,3可以组成集合B=一本书，一支笔，1,2,3。特别地，以集

7、合为元素的集合称为集合族或集合类，如A=1,2,3,8,9,6。,2023/9/14,16,2.子集、全集与空集 子集是描述一个集合与另一个集合之间的关系，其定义如下。定义 设A和B是任意两个集合，如果集合A的每个元素，都是集合B中的一个元素，则称A是B的子集，或称A被包含于B中，或者说B包含A，并记为AB。,2023/9/14,17,子集定义也可表成AB(x)(xAxB)这表明，要证明AB，只需对任意元素x，有下式xAxB成立即可。此外，若集合B不包含集合A，记为AB。,/,2023/9/14,18,定义 设A和B是两个集合，若AB且AB，则称A是B的真子集，记为AB，也称B真包含A。该定义

8、也可表为AB(ABAB),2023/9/14,19,定义 如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记为U或E。它可形式地表为U=x|P(x)P(x)其中P(x)为任何谓词公式。,2023/9/14,20,显然，全集U即是第二章中的全总论域。于是，每个元素x都属于全集U，即命题(x)(xU)为真。由定义易知，对任意集合A，都有AU。在实际应用中，常常把某个适当大的集合看成全集U。,2023/9/14,21,定义 没有任何元素的集合，称为空集，记为，它可形式地表为：=x|P(x)P(x)其中P(x)为任何谓词公式。由定义可知，对任何集合A，有A。,2023/9/14,22,注意，

9、与是不同的。是以为元素的集合，而没有任何元素，能用构成集合的无限序列：(1)，该序列除第一项外，每项均以前一项为元素的集合。,2023/9/14,23,(2)，该序列除第一项外，每项均以前面各项为元素的集合。它即是冯诺依曼在1924年使用空集给出自然数的集合表示：0:=，1:=，2:=,，这里,:=表示“定义符”定理 空集是唯一的定理()对任一集合A，有AA。()若AB且BC，则AC。,2023/9/14,24,3集合的基数 表示集合中元素多少或度量集合大小的数，称作集合的基数或势。一个集合A的基数，记为|A|。如果一个集合恰有m个不同的元素，且m是某个非负整数，称该集合是有限的或有穷的，否则

10、称这个集合为无限的或无穷的。例如，常用有穷集有：Nm=0,1,2,m-1,2023/9/14,25,常见的无穷集合有：N=0,1,2,3,，即自然数集合。Z=,-2,-1,0,1,2,3,，即整数集合。Z+=1,2,3,，即正整数集合。Q=有理数集合。R=实数集合。C=复数集合。,2023/9/14,26,4集合的幂集 一个集合的幂集是指该集合所有子集组成的集合，即是由这些子集所组成的集合族。定义 设A为一集合，A的幂集是一集合族，记为P(A)，P(A)=B|BA由定义可知，P(A)，AP(A)。,2023/9/14,27,例：试写出集合A1,2,3的幂集P(A)，1，2，3，1,2，1,3，

11、2,3，1,2,3,2023/9/14,28,5文氏图 文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法。全集U用一个矩形的内部表示，其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。,2023/9/14,29,如果AB，则表示A的圆面一般将完全落在表示B的圆面内，如图1中(a)。如果A与B没有公共元素，那么表示A的圆面将同表示B的圆面分开，如图3-1中(b)。当A和B是两个任意的集合时，可能会是：有些元素在A中但不在B中，有些元素在B中却不在A中，有些元素同时在A和B中，有些元素则既不在A中也不在B中，因此用图1中(c)表示任意两个集合A和B。,2023/9/14,

12、30,图 3-1,2023/9/14,31,最后给出集合的形式定义结束本节。定义 A为集合:=(x)(xAA=)。该定义与直观想法是一致的，一个集合或是具有成员的客体或是空集。,2023/9/14,32,3.2 集合运算及其性质,集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集U的子集，即这些集合是利用子集公理得到的。下面依次介绍常见的集合运算。,2023/9/14,33,1并、交和差运算定义 设A和B是任意两个集合，A和B的并是集合，记为AB，AB=x|xAxB A和B的交是集合，记为AB，AB=x|xAxB A和B的差，或B关于A的相对补是集合，记为A-B，A-B=x|xAxB

13、A B=AB(B 表示集合B的补集),2023/9/14,34,例：已知A1,2,3，B1,4，C=3，则A-B=2,3B-A=4C-A=,A-B,2023/9/14,35,定理 任给集合A，B和C，则：AB=BA AB=BA(AB)C=A(BC)(AB)C=A(BC)该定理表明，集合并和交运算满足交换律和结合律。,2023/9/14,36,定理 任给集合A、B和C，则 A(BC)=(AB)(AC)A(BC)=(AB)(AC)该定理表明，集合运算并对交、交对并都是可分配的。,2023/9/14,37,定理3.2.3 任给集合A，B，C和D，则 若AB，则AB=B，AB=A若AB和CD，则ACB

14、D，ACBD,2023/9/14,38,推论 AU=U，AU=A定理 任给集合A，B和C，则 A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C),2023/9/14,39,定义 设A是含有元素为集合的集合，或者集合族。A的并是集合，记为A，A=x|(B)(BAxB)=B A的交是集合，记为A，A=x|(B)(BAxB)=B,B A,B A,2023/9/14,40,例 令A=1,2,3,4,B=4,5,5,6,则A=1,23=1,2,3,B=55,6=5,6,A=1,23=,B=55,6=5,2023/9/14,41,集合A的补是集合，记为A，A=U-A=x|xUxA=x|x

15、A 任给集合A，则 AA=U，AA=。,2023/9/14,42,定理3.2.6 任给集合A和B，则B=A iff AB=U 且 AB=该定理表明了若A的补是B，则B的补是A，即A和B互补。补的唯一性。U=，=U 任给集合A，则A=A。该定理表明了，A的补的补是A。,2023/9/14,43,任给集合A和B，则(AB)=AB，(AB)=AB。任给集合A和B，A和B的对称差是集合,记为AB，AB=(A-B)(B-A)=x|(xAxB)(xBxA)AB=(AB)(AB),2023/9/14,44,例:A0,1,2，B2，3，则有 AB0,130,1,3或AB0,1,2,32=0,1,3,AB,20

16、23/9/14,45,任给集合A和B，则AB=(AB)(AB)=(AB)-(AB)AB=AB AB=BA AA=,2023/9/14,46,2集合运算定律与对偶原理 任何代数运算都遵从一定的定律,集合运算也不例外。下面列出集合性质中最主要的几条基本定律,对于全集合U的任意子集A、B、C,有：,2023/9/14,47,（1）等幂律AA=A AA=A（2）结合律(AB)C=A(BC)(AB)C=A(BC)（3）交换律 AB=BA AB=BA（4）分配律 A(BC)=(AB)(AC)A(BC)=(AB)(AC)（5）幺律 A=A AU=A,2023/9/14,48,（6）零律AU=U A=（7）补律 AA=U AA=（8）吸收律 A(AB)=A A(AB)=A（9）德摩根律(AB)=AB(AB)=AB（10）对合律(A)=A,2023/9/14,49,下面介绍集合代数中的对偶原理，它与命题逻辑中对偶原理也很相似。对偶原理 设E是集合代数中等式，将E中的，U和的每一个出现分别代以，和U后得到一等式E*，称E*为E的对偶式。,2023/9/14,50,显然，E也是E*的对偶式，即E与E*互为对偶。如果E是一集合恒等式，则E*也是一集合恒等式.可见，上述的集合定律中，凡成对的定律都是为对偶的。,