集合论与图论精选文档.ppt

《集合论与图论精选文档.ppt》由会员分享，可在线阅读，更多相关《集合论与图论精选文档.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、集合论与图论本讲稿第一页，共二十二页2第三章 目录第3-1讲 集合的概念和集合的运算第3-2讲 笛卡儿积与关系第3-3讲 复合关系、逆关系与闭包运算第3-4讲 等价关系第3-5讲 序关系本讲稿第二页，共二十二页3第3-1讲 集合的概念和运算1.集合的概念2.集合的表示3.集合间的关系4.幂集5.集合的运算6.集合运算的性质7.课堂练习8.第3-1讲 作业本讲稿第三页，共二十二页41、集合的概念n将一些确定的、彼此不同的事物的全体称之为集合。对于给定的集合和事物，应能判断这个特定的事物是否属于给定的集合。集合中的事物称为该集合的元素。通常，用大写的英文字母表示集合，用小写英文字母表示集合的元素。

2、例如，习惯上用表示非负整数的集合，用表示有理数集合，表示实数集合等等。如果是集合的元素,记作,读作“属于”。如不是的元素，记作 b，读作“不属于”，它等价于它等价于 （bsbs）。若一个集合的元素个数是有限的，则称为有限集，否则称为无限集。本讲稿第四页，共二十二页52、集合的表示n列举法：列出集合的所有元素，并用花括号括起来，元素之间用逗号隔开。例如：S=e1,e2,en (具有n个元素的有限集)a,b,c,d（a,b,c,d是该集合的元素）0,1,2,3,.(N是非负整数集)在一个集合中，元素是彼此不同的，相同的元素被认为是一个元素，而且元素之间没有次序关系，例如集合1,2,3，3,1,2和

3、3,3,1,2被视为同一个集合。n叙述法（或描述法）用谓词概括出集合中元素的特性，以确定集合的元素。Sx|(x)，如果(e)为真，那麽eS，否则eS。例如，设Ax|x3x8，则A4,5,6,7,8。本讲稿第五页，共二十二页62、集合的表示（续）n空集 定义1 不含任何元素的集合叫空集，记作。x|P(x)P(x)，P(x)是任意谓词。例如，A=xRx210是空集，式中表示实数集合。n全集 定义2 在研究某一问题时，如果所有涉及的集合都是某一集合的部分元素组成的，则称该集合为全集，记作。即 x|P(x)P(x)。（P(x)是任意谓词）显然，全集的概念相当于论域，它是一个相对概念。本讲稿第六页，共二

4、十二页73、集合间的关系n两个两个集合相等集合相等，当且仅当它们有相同的成员。，当且仅当它们有相同的成员。集合与相等，记作。集合与相等，记作。集合与不相等，记作集合与不相等，记作。n定义 给定集合和，如果中每个元素都是中的元素，则称为的子集，记作 或，读作“包含于”或“包含”。如果且，则称为的真子集，记作。AB (x)(xAxB)AB (x)(xAxB)(x)(xBxA)按按子子集集的的定定义义，对对于于任任何何集集合合A A、B B、C C都都有有A A A A(自自反反性性)，(A(A B)(BB)(B C)C)(A(A C)(C)(传递性传递性)本讲稿第七页，共二十二页83、集合间的关系

5、（续1）n定理 设设、为为两两个个集集合合，当当且且仅仅当当 且且。即即(AB)A BB A。证明：两个集合相等，则它们有相同的元素。(AB)(x)(xAxB)(x)(xBxA)(AB)(BA)。反之，若(AB)(BA)，如果AB，则A与B的元素不完全相同。设xA但xB，这与AB矛盾；或xB但xA，这与BA矛盾，故A与B的元素必相同，即AB。n 定理 空集是任意集合的子集。空集是任意集合的子集。证明：任给集合，是空集。则（x)(xxA)永真。这是因为条件式的前件(x)永假，所以该条件式对一切皆为真。按子集的定义，A为真。本讲稿第八页，共二十二页93、集合间的关系（续2）例1 证明对于任何集合证

6、明对于任何集合A A、B B、C C都有都有 (A(A B)(BB)(B C)C)(A(A C)C)证：证：(A(A B)(BB)(B C)C)(x)(xAxB)(x)(xAxB)(x)(xBxC)x)(xBxC)(x)x)（(xAxB)(xBxC)(xAxB)(xBxC)）(x)(xAxC)x)(xAxC)A A C C例2 确定下列命题的真值确定下列命题的真值 ；。解：解：、为真；为真；（因为空集是任何集合的子集，所以（因为空集是任何集合的子集，所以、为真。）为真。）为假。（因为空集不含任何元素。）为假。（因为空集不含任何元素。）本讲稿第九页，共二十二页103、集合间的关系（续3）例3 证

7、明证明空集是唯一的证：假定证：假定1 1和和2 2为二空集。为二空集。由定理由定理2 2，1 1 2 2，2 2 1 1。再根据定理再根据定理1 1，1 12 2 。例4 设集合设集合a,b,c，写出它的所有可能的子集。，写出它的所有可能的子集。解：集合解：集合a,b,ca,b,c的所有可能的子集是：的所有可能的子集是：S0=，S1=a，S2=b，S3=c，S4=a,b，S5=a,c，S6=b,c，S7=a,b,c。本讲稿第十页，共二十二页114、幂集n定义 集合的所有子集构成的集合叫的幂集，记作(A)。根据定义，根据定义，(A)=X|X A。例如。例如,设设a,b,c,a,b,c,则则 (A

8、),a,b,c,a,b,a,c,b,c,a,b,c例5 设设B B,求求 (B)(B)。解：解：(B)(B)，,本讲稿第十一页，共二十二页124、幂集（续）n定理 设A有个元素，则(A)有2n个元素。证证明明：A的的所所有有由由个个元元素素组组成成的的子子集集个个数数为为从从个个元元素素中取个元素的组合数中取个元素的组合数：在在(x+y)2的展开式中令的展开式中令x=y=1得：得：另外，因另外，因 A，故，故(A)中元素的个数可表示为：中元素的个数可表示为：本讲稿第十二页，共二十二页135、集合的运算定义1 设设、为为两两个个集集合合，则则与与的的交交集集、并并集集、差差集集（也也称称对对的的

9、相相对对补补集集）和和对对称称差差A B分别定义如下：分别定义如下：ABxxAxB ABxxAxB ABxxAx B A B（AB）（BA）xxA xB用文氏图可将集合表示如下：用文氏图可将集合表示如下：本讲稿第十三页，共二十二页145、集合的运算（续）定义2 设为全集，为任一集合，称为的绝对补，记作A 。AEAxxExA例6 设设a,b,c,d,Aa,b,c,d,Aa,c,Ba,c,Ba,b,c,d,ca,b,c,d,c,求求 A,B,C。解解：A b,d，B ，C a,b,c,dE。例7 设A1,2,3，B1,4，C3。求AB,BA，AB,BA,AB,AB,CA,BC。解解:AB1,2,3

10、,4BA AB1BA AB2,3 AB2,3,4 CA,BC 本讲稿第十四页，共二十二页156、集合运算的性质(1)交运算的性质nAA=AnA=nAE=AnAB=BAn(AB)C=A(BC)例8 证明证明(AB)C=A(BC)(AB)C=A(BC)证：证：(AB)C=x|x(AB)(AB)C=x|x(AB)xCxC =x|xA =x|xA xBxB xCxC =x|xA =x|xA(xB(xB xC)xC)=x|xA =x|xA xBC)xBC)=A(BC)本讲稿第十五页，共二十二页166、集合运算的性质(续1)(2)并运算的性质nAA=AnAE=EnAB=BAn(AB)C=A(BC)nA A

11、B，B AB例9 设设A B，C D，则，则AC BD。证证:对任意对任意xAC，则，则xA或或xC。若。若xA，因，因A B，xB，故，故xBD；若；若xC，因，因C D，所以，所以xD 亦有亦有xBD。按子集的定义可知原式成立。按子集的定义可知原式成立。本讲稿第十六页，共二十二页176、集合运算的性质(续2)(3)绝对补运算的性质n（A）=A n E=n=E n A=E nA A=n（AB）=A B例10 证明证明 (AB)=(AB)=AA B B证证:（ABAB）=x|x=x|x (AB)(AB)=x|x=x|x AB=x|AB=x|xAB xAB=x|=x|(xAxB)=x|(xAxB

12、)=x|xAxA xB xB=x|x=x|x AxAx B=x|xB=x|x AxAx B =B =AA B B本讲稿第十七页，共二十二页186、集合运算的性质(续3)(4)差运算的性质nA-B=A BnA-B=A-(AB)nA(B-C)=(AB)-(AC)例11 证明证明 A-B=A-(AB)A-B=A-(AB)证证:因为因为 xA-B xA-B xA xA x x B B xA xA x x(AB)(AB)xA-(AB)xA-(AB)所以，所以，A-BA-B A-(AB)A-(AB)。反之，反之，xA-(AB)xA-(AB)xA xA x x(AB)(AB)xA xA x x(AB)(AB

13、)xA xA x x A AB B xA xA(x(x A A xx B)B)(xA(xA xx A)A)(xA(xA xx B)B)）F F(xA(xA xx B)B)xAxA xx B B xAxA x x B B xA-B xA-B所以，所以，A-(AB)A-(AB)A-B A-B。纵上所述，原式成立。纵上所述，原式成立。本讲稿第十八页，共二十二页196、集合运算的性质(续4)(5)对称差运算的性质nA B=B AnA =AnA A=nA B=（A B）（AB）n(A B)C=A (B C)对结合律，用文氏图说明如下：本讲稿第十九页，共二十二页207、课堂练习练习1 证明证明A(B-C)

14、=(AB)-(AC)证法1：(AB)-(AC)=(AB)(AC)=(AB)(A C)=(AB A)(AB C)=(AB C)（从左往右的关键步骤）（从左往右的关键步骤）=AB C=A(B-C)证法2:按集合相等的定义证明。任取按集合相等的定义证明。任取xxA(B-C),有有 x xA(B-C)xxA xx(B-C)(xxA xxB x x C)(xxA xxB x x A)(xxA xxB x x C)(xxA xxB)(x x A x x C)xx(AB)(xxA xxC)xx(AB)(xxA xxC)xx(AB)(xxAC)xx(AB)x x AC xx(AB)-(AC)所以，所以，A(B

15、-C)=(AB)-(AC)。本讲稿第二十页，共二十二页217、课堂练习练习2 若若A B=A C，是否必有，是否必有B=C？解：(下下面面证证明明，如如果果A B=A C，则则xB xB xCxC，所所以以B B C C；反之有；反之有xC xC xBxB，所以，所以C C B B。从而有。从而有B=C。)任取任取xBxB，则对，则对A A而言，只有而言，只有xAxA或或x x A A两种可能。两种可能。（1 1）若若xAxA xAxAB x x A B x x A C 进而有进而有 xAxA x x A C xAxAC xCxC （2）若若x x A A x x A AB，又，又 xB xB xAxA B B，由由 x x A AB xAxA B B xxA B xxA C 进而有进而有 x x A A xxA C xCxC 所以所以B B C C。反之，反之，任取任取xCxC，同样可证，同样可证xBxB，所以，所以C C B B。综合上述综合上述，若若A B=A C，必有，必有B=C。本讲稿第二十一页，共二十二页22第3-1讲 作业nP85 1ace，4bf，6cdnP94 3cd，5ac，8本讲稿第二十二页，共二十二页