资源预览内容
第1页 / 共50页
第2页 / 共50页
第3页 / 共50页
第4页 / 共50页
第5页 / 共50页
第6页 / 共50页
第7页 / 共50页
第8页 / 共50页
第9页 / 共50页
第10页 / 共50页
亲,该文档总共50页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第三讲 集 合,3.1 集合论基础 3.2 集合运算及其性质 3.3 集合的笛卡儿积与无序积 3.4 集合中元素的计数,退出,3.1 集合论基础,1. 集合与元素 所谓集合,是指某些可辨别的不同对象的全体,将用大写字母A,B,X,Y,表示之。组成集合的对象称为集合的元素或成员,将用小写字母a,b,x,y表示之。a是A的元素或a属于A,记作aA;a不属于A或a不是A的元素,记作aA,或者(aA)。,集合的元素一旦给定,这一集合便完全确立。这一事实被形式地叙述为外延公理。 外延公理:两集合A和B相等,当且仅当它们有相同的元素。 若A与B相等,记为A=B;否则,记为AB。,外延公理可形式表为: A=B(x)(xAxB) 或者A=B(x)(xAxB)(x)(xBxA) 顺便指出,在应用外延公理证明集合A与B相等时,只需考察: 对于任意元素x,应有下式 xAxB 成立即可。这就是说,证明两集合相等时可按此法行事。,表示一个特定集合,基本上有两种方法: 一是枚举法,在可能时列出它的元素,元素之间用逗号分开,再用花括号括起。如 A=a,e,i,o,u (1) 表明集合A是由字母a, e, I ,o和u为元素构成的。,二是谓词法,用谓词公式来确定集合。即个体域中能使谓词公式为真的那些元素,确定了一个集合,因为这些元素都具有某种特殊性质。若P(x)含有一个自由变元的谓词公式,则x|P(x)定义了集合S,并可表为 S=x|P(x) 由此可见,P(c)为真当且仅当cS。从而有 xSP(x)为真,应该指出的是:集合并不决定于它的元素展示方法。集合的元素被重复或重新排列,集合并不改变,即a, a ,e, i, o, u= a, u, e, o, i。但有时对重复出现的元素都认为是集合的元素,这种集合称为多重集。即a, a, e, i, o, u, ua, e, i, o, u。本书中集合在不特别指明时,都指前者,即中的集合。,集合的元素可以是具体事物,可以是抽象概念,也可以是集体,不是集合的元素称为本元。如,一本书,一支笔,集合1,2,3可以组成集合B=一本书,一支笔,1,2,3 。特别地,以集合为元素的集合称为集合族或集合类如A=1,2,3, 8,9,6。 集合中元素之间可以有某种关联,也可以彼此毫无关系。,2. 子集、全集与空集 子集是描述一个集合与另一个集合之间的关系,其定义如下。 定义3.1.1 设A和B是任意两个集合,如果集合A的每个元素,都是集合B中的一个元素,则称A是B的子集,或称A被包含于B中,或者说B包含A,并记为AB。,本定义也可表成 AB(x)(xAxB) 这表明,要证明AB,只需对任意元素x,有下式 xAxB 成立即可。 此外,若集合B不包含集合A,记为AB。,/,定义3.1.2 设A和B是两个集合,若AB且AB,则称A是B的真子集,记为AB,也称B真包含A。该定义也可表为 AB(ABAB),定义3.1.3 如果一个集合包含了所要讨论的每一个集合,则称该集合为全集,记为U或E。它可形式地表为 U=x|P(x)P(x) 其中P(x)为任何谓词公式。,显然,全集U即是第二章中的全总论域。于是,每个元素x都属于全集U,即命题(x)(xU)为真。由定义易知,对任意集合A,都有AU。 在实际应用中,常常把某个适当大的集合看成全集U。,定义3.1.4 没有任何元素的集合,称为空集,记为,它可形式地表为: =x|P(x)P(x) 其中P(x)为任何谓词公式。 由定义可知,对任何集合A,有A。这是因为任意元素x,公式xxA总是为真。,注意,与是不同的。是以为元素的集合,而没有任何元素,能用构成集合的无限序列: (1), 该序列除第一项外,每项均以前一项为元素的集合。,(2), 该序列除第一项外,每项均以前面各项为元素的集合。它即是冯诺依曼在1924年使用空集给出自然数的集合表示: 0:=,1:=,2:= ,, 定理3.1.1 空集是唯一的 定理3.1.2 ()对任一集合A,有AA。 ()若AB且BC,则AC。,3集合的基数 表示集合中元素多少或度量集合大小的数,称作集合的基数或势。一个集合A的基数,记为|A|。 如果一个集合恰有m个不同的元素,且m是某个非负整数,称该集合是有限的或有穷的,否则称这个集合为无限的或无穷的。,常见的无穷集合有: N=0,1,2,3,,即自然数集合。 Z=,-2,-1,0,1,2,3,,即整数集合。 Z+=1,2,3,,即正整数集合。 Q=有理数集合。 R=实数集合。 C=复数集合。,4集合的幂集 一个集合的幂集是指该集合所有子集的集合,即是由这些子集所组成的集合族。 定义3.1.5 设A为一集合,A的幂集是一集合族,记为P(A), P(A)=B|BA 由定义可知,P(A),AP(A)。,5文氏图 文氏(Venn)图是一种利用平面上的点构成的图形来形象展示集合的一种方法。全集U用一个矩形的内部表示,其他集合用矩形内的园面或一封闭曲线圈成的面积来表示。,如果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。,图 3-1,3.2 集合运算及其性质,集合运算是指用已知的集合去生成新的集合。假设所有集合都是全集U的子集,即这些集合是利用子集公理得到的。下面依次介绍常见的集合运算。,1并、交和差运算 定义3.2.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,定义3.2.2 若A和B是集合,且AB=,则称A和B是不相交的。 如果C是个集合族,且C中任意两个不同元素都不相交,则称C中集合是两个不相交的,或称C是两两不相交的集合族。,定理3.2.1 任给集合A,B和C,则: AB=BA AB=BA (AB)C=A(BC) (AB)C=A(BC) 该定理表明,集合并和交运算满足交换律和结合律。,定理3.2.2 任给集合A、B和C,则 A(BC)=(AB)(AC) A(BC)=(AB)(AC) 该定理表明,集合运算并对交、交对并都是可分配的。,定理3.2.3 任给集合A,B,C和D,则 若AB,则AB=B,AB=A 若AB和CD,则ACBD,ACBD,推论3.2.3 AU=U,AU=A 定理3.2.4 任给集合A,B和C,则 A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C),定义3.2.4 集合A的绝对补是集合,记为A, A=U-A=x|xUxA=x|xA 定理3.2.5 任给集合A,则 A A=U, A A=。,定理3.2.6 任给集合A和B,则 B= A iff AB=U 且 AB= 该定理表明了若A的补是B,则B的补是A,即A和B互补。补的唯一性。 推论3.2.5 U=, =U 定理3.2.7 任给集合A,则 A=A。 该定理表明了,A的补的补是A。,定理3.2.8 任给集合A和B,则 (AB)= A B, (AB)= A B。 定义3.2.5 任给集合A和B,A和B的对称差是集合,记为AB, AB =(A-B)(B-A) =x|(xAxB)(xBxA) =x|xAxB,定理3.2.9 任给集合A和B,则 AB=(AB)( A B) =(AB) - (AB) 推论3.2.9 A B=AB AB=BA AA=,2集合代数与对偶原理 本小节将形式地讨论由集合、集合变元、集合运算和圆括号所构成的集合代数以及集合代数中的对偶原理。 与命题逻辑相似,对于给定集合实行集合运算,可以生成新的集合。同用大写英文字母表示确定集合一样,也用大写字母表示不确定的集合,前者称为集合常元,后者称为集合变元。集合变元用以集合常元代替后,才表示确定的集合。下面将给出集合的合式公式定义。,定义3.2.6 可按下列规则生成集合合式公式: 单个集合变元是集合合式公式。 若A是集合合式公式,则A也是集合合式公式。 若A和B是集合合式公式,则(AB),(AB),(A-B)和(AB)也都是集合合式公式。 只有有限次使用、和构成的符号串才是集合合式公式。 为方便计,简称集合合式公式为公式。,定义3.2.7 用任意集合常元取代两个集合公式中的各个集合变元,若所得集合是相等的,则称该二集合公式是相等的,简称等式。 因为集合公式相等,不依赖于取代集合变元的集合,故常称这些等式为集合恒等式,或集合定律。它们刻划了集合运算的某些性质,这些性质描述一个代数,称为集合代数。下面列出常用集合定律:,(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,(6)零律 AU=U A= (7)排中律 AA=U 矛盾律 AA= (8)吸收律 A(AB)=A A(AB)=A (9)德摩根律 (AB)=AB (AB)=AB (10)双重否定律 (A)=A,下面介绍集合代数中的对偶原理,它与命题逻辑中对偶原理也很相似。 对偶原理 设E是集合代数中等式,将E中的,U和的每一个出现分别代以,和U后得到一等式E*,称E*为E的对偶式。,显然,E也是E*的对偶式,即E与E*互为对偶。 如果E是一集合恒等式,则E*也是一集合恒等式。 可见,上述的集合定律中,凡成对的定律都是为对偶的。,3.3 集合的笛卡尔积与无序积,笛卡尔积与无序积在后面讨论关系和图论时,都有重要应用。 首先引入有序对和无序对的概念。 定义3.3.1 两个元素a,b组成二元组,若它们有次序之别,称为二元有序组,或有序对,记为,称a为第一分量,b为第一分量;若它们无次序区分,称为二元无序组,或无序对, 记为(a, b)。 若ab时,。但(a, b)=(b, a)。,定义3.3.2 给定两个有序对和。当且仅当x=u和y=v时,有序对和相等,亦即 = iff (x=u)(y=v),可将有序对推广到n元有序组,它的第一分量是(n-1)元有序组,并记为,xn,或记为。类似地定义两个n元有序组相等: = iff (x1=y1)(x2=y2)(xn-1=yn-1)(xn=yn) 下面将使用有序对和无序对分别定义笛卡儿积和无序积。,定
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号