集合论与图论优秀PPT.ppt-淘文阁

资源描述

《集合论与图论优秀PPT.ppt》由会员分享，可在线阅读，更多相关《集合论与图论优秀PPT.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、例如，习惯上用表示非负整数的集合，用表示有理数集合，表示实数集合等等。如果是集合的元素,记作,读作“属于”。如不是的元素，记作 b，读作“不属于”，它它等价于等价于（bsbs）。若一个集合的元素个数是有限的，则称为有限集，否则称为无限集。第四页，本课件共有22页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。第五页，本课件共有22页62、集合的表示（续）n空集定义1 不含任何元素的集合叫空集，记作。x|P(x)P(x)，P(x)是任意谓词。例如，A=xRx210是空集，式中表示实数集合。n全集定义2 在研究某一问题时，如果所有涉及的集合都是某一集合的部分元素组成的，则称该集合为全集，记作。即 x|P(x)P(x)。（P(x)是任意谓词）显然，全集的概念相当于论域，它是一个相对概念。第六页，本课件共有

4、22页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)(传递性传递性)第七页，本课件共有22页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为真。第八页，本课件共有22页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 确定下列命题的真值确定下列命题的真值；。解：解：、为真；为真；（因为空集是任何集合的子集，所以（因为空集是任何集合的子集，所以、为真。）为真。）为假。（因为空集不含任何元素。）为假。（因为空集不含任何元素。）第九页，本课件共有22页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。第十页，本课件共有22页114、幂集n定义集合的所有子集构成的集合叫的幂集，记作(A)。根据定义，根据定义，(A)=X|X A。例如。例如,设设a,b,c,a,b,c,则则 (

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

9、的相相对对补补集集）和和对对称称差差A B分别定义如下：分别定义如下：ABxxAxB ABxxAxB ABxxAx B A B（AB）（BA）xxA xB用文氏图可将集合表示如下：用文氏图可将集合表示如下：第十三页，本课件共有22页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,

11、AB，B AB例9 设设A B，C D，则，则AC BD。证证:对任意对任意xAC，则，则xA或或xC。若。若xA，因，因A B，xB，故，故xBD；若；若xC，因，因C D，所以，所以xD 亦有亦有xBD。按子集的定义可知原式成立。按子集的定义可知原式成立。第十六页，本课件共有22页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|(xAx

12、B)=x|xAxA xB xB=x|x=x|x AxAx B=x|xB=x|x AxAx B =B =AA B B第十七页，本课件共有22页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)(A

13、B)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。纵上所述，原式成立。纵上所述，原式成立。第十八页，本课件共有22页196、集合运算的性质(续4)(5)对称差运算的性质nA B=B AnA =AnA A=nA B=（A B）（AB）n(A B)C=A (B C)对结合律，用文氏图说明如下：第十九页，本课件共有22页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(

15、B-C)=(AB)-(AC)。第二十页，本课件共有22页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页22第3-1讲作业nP85 1ace，4bf，6cdnP94 3cd，5ac，8第二十二页，本课件共有22页

展开阅读全文