1、第六章 集合代数,第一节: 集合的基本概念 第二节:集合的运算与集合恒等式,第六章 集合代数,主要内容集合的基本概念 属于、包含 幂集、空集 文氏图等集合的基本运算 并、交、补、差等集合恒等式 集合运算的算律、恒等式的证明方法,第六章 集合代数,德国著名数学家康脱(GEORGE CANTOR,18451918)在总结前人的基础上,创立了(古典、朴素)集合论。集合论为整个经典数学的各分支提供了共同的理论基础。朴素集合论由于在定义集合的方法上缺乏限制,会导致悖论。另一个德国数学家蔡梅罗(ERNST ZERMELO)于1908年建立了集合论的公理系统,由这个公理系统,他推出了所有数学上的重要结果。他
2、的公理使数学哲学中产生的一些矛盾基本上得到统一,在此基础上形成了公理化集合论和抽象集合论。,6.1 集合的基本概念,集合是能作为整体论述的事物的集体。又称为类、族、搜集。组成集合的每个事物叫做这个集合的元素或成员。用符号表示某个元素属于某个集合,表示不属于。任意元素,对于某一集合而言 ,或属于该集合,或者不属于,二者必居其一,不可兼得。这也符合命题演算中,命题要么是真,要么是假的二值逻辑。,通常有三种方法表示集合:1) 列举法2) 描述法用谓词描述出集合元素的公共特征来表示这个集合。例如:A=a|aR0a a4S=a|P(a) 表示a属于S当且仅当 P(a)为真。3) 归纳定义法,6.1 集合
3、的基本概念,有限集合的元素的个数称为该集合的基数或势。记为|A|。例:A=0,1 |A|=2;|A|=1。外延公理:两个集合A和B相等,即A=B,当且仅当他们有相同的成员(也就是,A的每一元素是B的一个元素而B的每一个元素也是A的一个元素)。用逻辑符号表达是:A=B x(xA xB),6.1 集合的基本概念,讨论集合:集合中元素的次序是无关紧要的集合中的元素的重复出现无足轻重集合的表示不是唯一的。一个集合可以用多种方法表示例如: a,b,c=c,b,a=a,c,b=a,a,b,c,c 讨论P=a,b,c 与 Q=a,b,c, PQ 设A=x | x*(x-1)=0与 B=0, 1, 有A=B,
4、6.1 集合的基本概念,集合间的包含关系定义:设A和B是集合,如果A的每一个元素是B的一个元素,那么A是B的子集合,记为A B,读做“ B包含A”或“A包含于B中”。A B x(xA xB)注意:可能AB或BA,也可能两者均不成立,不是两者必居其一。 定义:设A和B是集合, 如果AB和BA则称A和B相等,记做A=B。定义:如果A B,且AB,那么称A是B的真子集,记作A B,读作“B真包含A”A B (A B) (AB),6.1 集合的基本概念,本章中讨论的集合和元素都是限于某一论述域的。我们记该论述域为E,又称为全集合。定义:没有任何元素的集合称为空集,记为 前者是空集,是没有元素的集合;后
5、者是以作为元素的集合定理:对任意集合A有: A 提示: A x(x xA)推论:空集是唯一的 提示: 1 2 2 1 定理:对任意集合A有A E,6.1 集合的基本概念,例:确定下列命题是否为真(1) (2) (3) (4) 含有n个元素的集合简称n元集,它的含有m个(mn)元素的子集称为它的m元子集。,6.1 集合的基本概念,例:A=a,b,c,求A的全部子集解:将A的子集从小到大分类:0元子集:只有一个空集。1元子集:有3个a,b,c。2元子集:有3个a,b,a,c,b,c。3元子集:有1个A本身。A共有8个子集,分别为,a,b,c, a,b,a,c, b,c,a,b,c 。所以一般n个元
6、素的集合有2n个不同的子集合,6.1 集合的基本概念,幂集合定义:由集合A的所有子集(包括空集及A本身)所组成的集合叫做A的幂集,记以 ,即 =B|BA。一个给定集合的幂集是唯一的。例:(a)如果A=,那么 =。 (b)如果A=a,b,那么 =,a,b,a,b。,6.1 集合的基本概念,设A为一个有限集,A的基数为|A|,则 的基数| |=2|A|。例:A=, =, ,6.1 集合的基本概念,定义:设A和B是集合A和B的并记为AB,是集合 AB=x|xA xBA和B的交记为AB,是集合 AB=x|xAxB A和B的差,或B关于A的相对补,记为AB,是集合 AB =x|xAx B命题演算中的各种
7、运算性质,和集合论中的各种运算性质极为相似,6.1 集合的基本概念,6.2 集合的运算,例:设A= a,b,c, B =b,c,d,求AB, AB , AB 。解 AB=a,b,cb,c,d = a,b,c,d AB=a,b,cb,c,d = b,c AB =a,b,cb,c,d = a定义 设 A 与 B 是两个集合。若有AB =,那么称 A 和 B 是不相交的。如果C是一个集合的族,使C的任意两个不同元素(集合)都不相交,那么C是(两两)不相交集合的族。,定义:设A,B是两集合,集合(A-B)(B-A)称为集合A,B的对称差(对称差),记作AB。即 AB=xxAxBxBxA文氏图表示如下:
8、 A B 将AB中同时属于A,B的元素去掉定理 AB=(AB)-(AB),6.2 集合的运算,定义. 设E是论述域而A是E的子集。A的(绝对)补,记为A,是集合AEAx|xEx A=x A。例:若 E= 1,2,3,4 和 A= 1,2 ,則A = 3,4。 若 E = N 且 A= x | x 0, 則A= 0,6.2 集合的运算,例:A=xx-2,xR,E=xx2,xR求A,AA。解:A=xx2x-2 =x-2x2,xR AA=AA=(A-A)(A-A)= =,6.2 集合的运算,文氏图(Venn Diagrams)利用图来图解全集的各子集的关系的图称为文氏图。文氏图约定: (1)全集合用
9、一个大矩形表示(2)设A是E的一个子集,A用圆形表示(3)通常在图中画有阴影的区域表示新组成的集合。,6.2 集合的运算,文氏图,集合运算的表示,A,B,A,B,A,B,A,B,A,B,AB,AB,AB,AB,A,一般说来证明两个集合相等有以下几种方法。(一)利用集合相等的定义证明 A=B x(xA xB)(二)利用已知集合等式证明(三)利用文氏图即只需通过画出文氏图证明即可证明(AB) (AC)= (AC)(AB),6.2 集合的运算,通过画出文氏图即可证明,如下所示: AB AC ( AB) ( AC) A C A B (AC)(AB),6.2 集合的运算,在165个学生中,8个人既学习微
10、积分和心理学又学习计算机科学;33个人既学习微积分又学习计算机;20个人既学习微积分又学习心理学;24个人既学习心理学又学习计算机;79个人学习微积分;83个人学习心理学;63个人学习计算机。问有多少人三门课程中一门都没有学?,6.2 集合的运算,6.2 集合的运算,有限集合的计数: 定理(1)max(A,B)ABA+B(2)ABmin(A,B)(3)ABABA(4)AB=A+B-2AB,6.2 集合的运算,定理 (包含排斥定理)AB=A+B-AB证明:A=A(BB)=(AB)(AB)而(AB)(AB)=A=AB+ABAB=A-AB (1) 而(AB)B=AB;(AB)B=AB=AB+B将(1
11、)式代入AB=A+B-AB,6.2 集合的运算,例:在20名青年有10名是公司职员,12名是学生,其中5名既是职员又是学生,问有几名既不是职员,又不是学生。解:设职员和学生的集合分别是A和B。由已知条件A=10, B =12, AB=5AB=A+B-AB=10+12-5=17则(AB)=E-AB=20-17=3有3名既不是职员又不是学生,从图中可以理解包含排斥定理。,6.2 集合的运算,三个集合的包含排斥定理 |ABC=A+B+C-AB-AC-BC+ABC,6.2 集合的运算,并和交运算的扩展定义6.10-11:设C是某论述域子集的集合。(a)C的成员的并,记为C,是由下式指定的集合 C=x
12、| S(S C x S)(b)如果C,C的成员的交,记为C,是下式指定的集合 C=x | S(S C x S)定义说明如果x C ,那么x至少是一个子集SC 的元素。如果x C ,那么x是每一个子集SC 的元素,6.2 集合的运算,注意:对C的定义来说,C必须非空,否则,由于C=,那么蕴含式 对于每一S将是无意义的真。 对每一x是真。因此所定义的集合就是E,是不正确的。,6.2 集合的运算,例:设论述域是实数R(a)如果C=1,2,4,3,4,5,4,6,那么 C=1,2,3,4,5,6, C=4,(b)我们用0, a)表示集合x|0xa如果Sa=0,a),aR+,C=Sa | aR+,那么
13、C=0,), C=0,6.2 集合的运算,6.3 集合恒等式,设 A,B,C,D是论述域E的任何子集,于是有:幂等律 AA = A AA = A 结合律 (A B) CA ( B C) (A B) CA (B C)交换律 ABBA ABBA分配律 A(BC)= (AB) (AC) A(BC)= (AB) (AC),同一律 A = A AE= A 零律 AE = E A= 排中律 AAE矛盾律 AA吸收律 A(AB)= A A(AB)= A摩根定律 A- (BC)=(A-B) (A-C) A- (BC)=(A-B) (A-C) (BC)= BC (BC)=BC E E双重否定律 (A)=A,6.
14、3 集合恒等式,A B A A B B A AB B AB A-B A A-B=ABAB=B A B A B =A A-B= AB = BA(AB)C=A(BC)A=A AA=AB=ACB=C,6.3 集合恒等式,例: 证明ABA B证:对任意的x,x(AB) xA x B xA x B x A B 所以ABA B,6.3 集合恒等式,例: 如果A B和C D,那么(AC) (BD)证明:设x是属于(AC)的任意元素, 那么xA xC,现分情况证明:如果xA,因为A B,所以xB 所以x BD;如果xC,因为C D,所以xD 所以x BD因此,如果x AC,那么x BD所以有 (AC) (BD
15、),6.3 集合恒等式,证明: AB=B A B A B =A A-B= 证明:先证AB=B A B。假设任意x,xA xA x B xABxB所以A B 再证A B A B =A ,显然A B A ,对任意x,xA xA x A xA x B xA B 所以A B =A,6.3 集合恒等式,再证:A B =A A-B= AB A B (A B ) B A (BB)= 再证: A-B= AB=B因为(A-B)B=AB,而A-B= AB=B,6.3 集合恒等式,第六章 习题课,主要内容集合的两种表示法集合与元素之间的隶属关系、集合之间的包含关系的区别与联系特殊集合:空集、全集、幂集文氏图及有穷集
16、合的计数集合的, , , , 等运算以及广义, 运算集合运算的算律及其应用,基本要求,熟练掌握集合的两种表示法能够判别元素是否属于给定的集合能够判别两个集合之间是否存在包含、相等、真包含等关系熟练掌握集合的基本运算(普通运算和广义运算)掌握证明集合等式或者包含关系的基本方法,练习1,1判断下列命题是否为真 (1) (2) (3) (4) (5) a, b a, b, c, a, b, c (6) a, b a, b, c, a, b (7) a, b a, b, a, b (8) a, b a, b, a,b,解 (1)、(3)、(4)、(5)、(6)、(7)为真,其余为假.,方法分析,(1)
17、 判断元素a与集合A的隶属关系是否成立基本方法: 把 a 作为整体检查它在A中是否出现,注意这里的 a 可 能是集合表达式. (2) 判断AB的四种方法若A,B是用枚举方式定义的,依次检查A的每个元素是否在B中出现. 若A,B是谓词法定义的,且A, B中元素性质分别为P和Q, 那么“若P则Q”意味 AB,“P当且仅当Q”意味=通过集合运算判断AB,即AB = B, AB = A, AB = 三个等式中有一个为真.通过文氏图判断集合的包含(注意这里是判断,而不是证明,练习2,2设 S1=1, 2, , 8, 9, S2=2, 4, 6, 8 S3=1, 3, 5, 7, 9 S4=3, 4, 5
18、 S5=3, 5 确定在以下条件下X是否与S1,S5中某个集合相等?如果是,又与哪个集合相等? (1)若 XS5= (2)若 XS4但 XS2= (3)若 XS1且 X S3 (4)若 XS3= (5)若 XS3 且 X S1,解答,解(1) 和S5不交的子集不含有3和5,因此 X=S2. (2) S4的子集只能是S4和S5. 由于与S2不交,不能含有偶数, 因此 X=S5.(3) S1, S2, S3, S4和S5都是S1的子集,不包含在S3的子集含有 偶数,因此 X=S1, S2或S4. (4) XS3=意味着 X是S3的子集,因此 X=S3或 S5.(5) 由于S3是S1的子集,因此这样
19、的X不存在.,练习3,3. 判断以下命题的真假,并说明理由. (1)AB = A B= (2)A(BC) = (AB)(AC) (3)AA = A (4)如果AB = B,则A = E. (5)A = xx,则 xA且x A.,解题思路,先将等式化简或恒等变形.查找集合运算的相关的算律,如果与算律相符,结果为真.注意以下两个重要的充要条件 AB = A AB = AB = AB AB = B AB = A 如果与条件相符,则命题为真.如果不符合算律,也不符合上述条件,可以用文氏图表示集合,看看命题是否成立.如果成立,再给出证明.试着举出反例,证明命题为假.,解答,解(1) B=是AB=A的充分
20、条件,但不是必要条件. 当B不空但 是与A不交时也有AB=A. (2) 这是DM律,命题为真.(3) 不符合算律,反例如下: A=1,AA=,但是A.(4) 命题不为真. AB=B的充分必要条件是 BA,不是A=E. (5) 命题为真,因为 x 既是 A 的元素,也是 A 的子集,练习4,4证明 AB = AC AB = AC B = C,解题思路分析命题:含有3个命题: AB = AC , AB = AC, B = C 证明要求 前提:命题和 结论:命题 证明方法: 恒等式代入 反证法 利用已知等式通过运算得到新的等式,解答,方法一:恒等变形法 B = B(BA) = B(AB) = B(A
21、C) = (BA)(BC) = (AC)(BC) = (AB)C = (AC)C = C,方法二:反证法.假设 B C,则存在 x (xB且xC), 或存在 x (xC且xB). 不妨设为前者. 若x属于A,则x属于AB 但x不属于AC,与已知矛盾;若x不属于A,则x属于AB但x不属于AC,也与已知矛盾.,解答,方法三:利用已知等式通过运算得到新的等式.由已知等式和可以得到 (AB) (AB) = (AC) (AC)即 AB = AC 从而有 A(AB) =A(AC) 根据结合律得 (AA)B = (AA) C 由于AA = , 化简上式得B = C.,练习5,5设A,B为集合,试确定下列各式
22、成立的充分必要条件:(1) AB=B(2) AB=BA(3) AB=AB(4) AB=A,分析,解题思路: 求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等. 具体求解过程说明如下: (1) 化简给定的集合等式 (2) 求解方法如下:利用已知的算律或者充分必要条件进行判断先求必要条件,然后验证充分性利用文氏图的直观性找出相关的条件,再利用集合论的证明方法加以验证,解答,解(1) AB=B A=B=. 求解过程如下: 由AB=B得 (AB)B = BB 化简得B=. 再将这个结果代入原来的等式得A= . 从而得到必要条件A=B=.再验证充分性. 如果A=B=成立,则AB=B也成立.,(2) AB=BA A=B. 求解过程如下:充分性是显然的,下面验证必要性. 由AB=BA得 (AB)A=(BA)A从而有A=AB, 即AB. 同理可证BA.,解答,(3) AB=AB A=B. 求解过程如下:充分性是显然的,下面验证必要性. 由AB=AB得 A(AB) = A(AB)化简得A =AB,从而有AB. 类似可以证明BA.,(4) AB=A B=. 求解过程如下:充分性是显然的,下面验证必要性. 由AB = A得 A(AB) = AA根据结合律有 (AA)B = AA即 B = , 就是B = .,