离散 03-集合

1、第三章 集合论,2020年7月26日星期日,第一节 集合论基础,第一节 集合论基础 定义：集合是指某些可以辨别的不同对象的全体 一个集合是能作为整体论述的事物的集体。例如： 华北电力大学软件工程专业09级学生 硬币的正面和反面 某计算机中的全部内存 ,2020年7月26日星期日,集合与元素,定义：元素是指组成集合的对象，也叫作成员。 通常用大写字母A、B、X、Y等表示集合用小写字母a、b、x、y等表示元素 若a是集合A中的一个元素，则记为a A读作“a属于A”或“a在A中” 若a不是集合A中的一个元素，则记为a A或 (a A)读作“a不属于A”或“a不在A中”,2020年7月26日星期日,集

2、合的表示,通常有3中方法表示集合： 枚举法将集合中的所有元素都列举出来 例如：集合A是小于5的正整数。用枚举法表示为： A=1, 2, 3, 4 在能清楚地表示集合成员的情况下可使用省略号。 例如：集合B表示1到50的整数集合。可以表示为： B=1, 2, 3, , 50,2020年7月26日星期日,集合的表示,谓词描述法用谓词描述出集合元素的公共特征 若P(x)是含有一个自由变元的谓词公式，则：S=x|P(x)定义了集合S，S中的所有元素都满足谓词P(x)。 例如：A=x|小于5的正整数： B=x|x I x0,2020年7月26日星期日,集合的表示,归纳定义法（了解） 例如：能被3整除的正

3、整数集合A，可以归纳定义（设论域为全体整数I）： 1) （基础） 3 A 2) （归纳）如果 x A，且 y A，那么 x+y A 3) （极小性）没有一个整数是A中的元素，除非它是应用条款1)和2)得出的。,2020年7月26日星期日,集合与元素,集合的元素还可以是一个集合。例如：A=1, 2, 3, D，而D=0, -1A称为集合族，或集合类 仅含有一个元素的集合称为单元素集合 要把单元素集合与集合中的元素区分开。例如： A=1, 2，B=A B是单元素集合，其中的唯一的一个元素是集合A,2020年7月26日星期日,外延公理,集合的元素一旦给定，这个集合就完全确立 外延公理：两个集合相等，

4、当且仅当它们有相同的元素。若集合A与B相等，记为A=B；否则，记为A B 外延公理可以表示为：A=B ( x)(x A x B) 或 A=B(x)(xA xB)(x)(xB xA),2020年7月26日星期日,外延公理,由外延公理可知：如果两个集合有相同的元素，那么不管集合是如何表示的，它们都相等。 列举法中，元素的次序是无关紧要的。x, y, z 与 z, x, y 是相等的集合 元素的重复出现无足轻重。x, y 和 x, x, y, y 和 x, y, y 都相等 集合的表示不是唯一的。x|x2-3x+2=0 和 1, 2 是相等的。,2020年7月26日星期日,子集,定义：设A和B是任意

5、两个集合，如果集合A的每个元素，都是集合B中的元素，称A是B的子集（或B包含A，或A被包含于B），记为A B即： A B ( x)(x A x B) 例如：A=a, b, B=a, b, c 则A B 若集合B不包含集合A，记为A B,2020年7月26日星期日,子集,定理：设A和B是两个集合，A=B当且仅当 A B且B A 证明： A=B ( x)(x A x B) (x)(xA xB)(x)(xB xA) A B B A 推论：对于任意集合A，有A A,2020年7月26日星期日,子集,定理：设A、B、C是三个集合，若 AB 且 BC ，则 A C 证明： A B ( x)(x A x B

6、)B C ( x)(x B x C) 因此有： ( x)(x A x B)( x)(x B x C) ( x)(x A x B)(x B x C) ( x)(x A x C) A C,2020年7月26日星期日,真子集,定义：设A和B是任意两个集合，若A B，且AB，则称A是B的真子集(或B真包含A，或A被真包含于B)，记为A B即： A B A B AB ( x)(x A x B) ( x)(x B x A) 例如：A=a, B=a, C=a, b，则A B, A C,2020年7月26日星期日,全集,我们所讨论的集合和元素是限于某一论域的。若没有明确指出，便指全总论域。 定义：若一个集合包

7、含了所要讨论的每一个集合， 则该集合称为全集，记为U，即全总论域。U=x|P(x) P(x) 对于任意集合A，都有A U,2020年7月26日星期日,空集,定义：没有任何元素的集合，称为空集或零集，记为 。 =x|P(x) P(x) 对于任意集合A，都有 A 注意：与的不同 是不含任何元素的集合 是以为元素的单元素集合,2020年7月26日星期日,空集,定理：空集是唯一的 证明：设和都是空集。 所以 ，并且 所以 = A为集合= ( x)(x A A = ),2020年7月26日星期日,集合,例3.1.1求集合p, q的子集 解：集合p, q的子集是、p、q、p, q 下面说法是否正确？ p

8、p, q p p, q p p, q p p, q p, q p, q,2020年7月26日星期日,集合,例3.1.1求集合, q的子集 解：集合, q的子集是、q、, q 下面说法是否正确？ , q , q , q , q,2020年7月26日星期日,集合的基数,定义：含有限个元素的集合，称为有限集合或有穷集， 否则称为无限集合或无穷集。 有限集合A的元素个数，称为集合的基数或势，记为|A|。 本书中：Nm=0, 1, 2, , m-1是一个有限集合，基数是m N=0, 1, 2, 3, 即自然数集合，是一个无限集合 Z=, -2, -1, 0, 1, 2, 即整数集合，是一个无限集合 Z+

9、=1, 2, 3, 即正整数集合，是一个无限集合 Q为有理数集合，R为实数集合，C为复数集合,2020年7月26日星期日,幂集,定义：一个集合的幂集，是指该集合所有子集的集合， 即这些子集的集合族。 设A是一个集合，A的幂集表示为P(A)，P(A)=B|B A,2020年7月26日星期日,幂集,一个有限集合A的基数|A|为n，则它有2n个不同的子集。 那么，|P(A)|= 2n 例：A=，则P(A)= A=a, b，则P(A)= , a, b, A 对于任意集合A，都有： P(A)，A P(A),2020年7月26日星期日,文氏图,文氏图是一种利用平面上的点构成图形，用以表示集合的一种方法。

10、全集用几个矩形的内部表示 其他集合用矩形内的圆或封闭的曲线圈来表示,2020年7月26日星期日,文氏图,例如：,表示： B A,表示： A和B没有共同元素,表示： A和B中有部分共同元素通常用该文氏图表示任意两个集合,2020年7月26日星期日,罗素悖论,1903年，一个震惊数学界的消息传出：集合论是有漏洞的！这就是英国数学家罗素提出的著名的罗素悖论。 罗素悖论 理发师悖论 某村只有一人理发，且该村的人都需要理发，理发师规定，给且只给村中不自己理发的人理发。试问：理发师给不给自己理发？ 罗素构造了一个集合S：S由一切不是自身元素的集合所组成。即 S= T |T T ，然后罗素问：S是否属于S呢

11、？,罗素悖论一提出就在当时的数学界与逻辑学界内引起了极大震动。 如G.弗雷格在收到罗素介绍这一悖论的信后伤心地说：“一个科学家所遇到的最不合心意的事莫过于是在他的工作即将结束时，其基础崩溃了。罗素先生的一封信正好把我置于这个境地。”戴德金也因此推迟了他的什么是数的本质和作用一文的再版。可以说，这一悖论就象在平静的数学水面上投下了一块巨石，而它所引起的巨大反响则导致了第三次数学危机。,2020年7月26日星期日,悖论,“鳄鱼两难” 这是古希腊哲学家们喜欢谈论的一个悖论 一条鳄鱼从一位母亲手中抢走了一个小孩，鳄鱼对孩子的母亲说：“请你回答我，我会不会吃掉你的孩子？答对了，我就把孩子不加伤害的还给你

12、；否则，就别怪我不客气了！”试问聪明的母亲该如何回答？ 中国民间流传着这么一个故事：“师徒打官司” 一位讼师收徒弟，协议规定：“学成之后，打赢一场官司交给讼师一两银子，打输一场官司就不交。”后来弟子满师，打赢了官司却一直不交钱，老讼师气极了告到县衙，和弟子打官司。试问这场官司该如何裁决？,你是会吃掉我的孩子的,2020年7月26日星期日,悖论,聪明的囚徒 古希腊有个国王，对处死囚徒的方法作了两种规定：一种是砍头，一种是处绞刑。并且他自恃聪明地作出一种决定：囚徒可以任意说出一句话，而且这句话是马上可以验证其真假。如果囚徒说的是真话，那么处以绞刑；如果说的是假话，那么就砍头。结果，许多囚徒或者因为

13、说了真话而被绞死；或者因为说了假话而被砍头。 有一位及其聪明的囚徒，当轮到他来选择处死方法时，他说出一句巧妙的话，结果使这个国王按照哪种方式处死他，都违背自己的决定，只得将他放了。试问，这位囚徒说的是句什么话？,国王决定将我砍头,2020年7月26日星期日,第二节 集合运算及性质,第二节 集合运算及性质 集合上的运算是指用给定的集合（运算对象）去生成新的集合（运算结果）。在这里，我们假定所有集合都是全集U的子集。 并、交、差 运算 补运算 对称差,2020年7月26日星期日,交并差,定义：设A和B是任意两个集合。 A和B的并是集合，记做 A BA B=x|x Ax B A和B的交是集合，记做

14、A BA B=x|x Ax B A和B的差（相对补）是集合，记做 A - BA - B=x|x Ax B,2020年7月26日星期日,交并差,例3.2.1 设A=a, b, c, d和B=b, c, e，那么 A B = A B = A B = B A =,a, b, c, d, e,b, c,a, d,e,2020年7月26日星期日,交并差,定义：设A和B是任意两个集合，若A B= ， 则称A和B是不相交的。,若C是一个集合族，且C中任意两个不同元素都不相交，则称C是（两两）不相交的集合族,例如：C = 0, 1, 2, = i |i N ,2020年7月26日星期日,交并差的交换律,交换律

15、：设A、B是任意两个集合。 A B = B A 证明：对于U上的任意元素x，有： x A B x A x B 的定义 x B x A的交换性 x B A 的定义 A B = B A,2020年7月26日星期日,交并差的结合律,结合律：设A、B、C是任意三个集合。 (A B) C = A (B C) 证明：对于U上的任意元素x，有： x (A B) C (x A x B) x C x A (x B x C) x A (B C) (A B) C = A (B C),2020年7月26日星期日,交并差的分配律,分配律：设A、B、C是任意三个集合。 A (B C) = (A B) (A C) 证明：对

16、于U上的任意元素x，有： x A (B C) x A (x B x C) (x A x B) (x A x C) x (A B) (A C) A (B C) = (A B) (A C),2020年7月26日星期日,交并差运算,设A是任意一个集合。 等幂律：A A = A 证明：对于U上的任意元素x，有： x A A x A x A x A A A = A,2020年7月26日星期日,交并差运算,设A是任意一个集合。 么律：A = A 证明：对于U上的任意元素x，有： x A x A x x A 零律：A = ,2020年7月26日星期日,交并差运算,设A是任意一个集合。 A - = A 证明：

17、对于U上的任意元素x，有： x A - x A x x A,2020年7月26日星期日,交并差运算,设A、B是任意两个集合。 A A B 证明：对于U上的任意元素x，有： x A x A x B x A B A B A,2020年7月26日星期日,交并差运算,设A、B是U上任意两个集合。 A - B A 证明：对于U上的任意元素x，有： x A - B x A x B x A,2020年7月26日星期日,交并差运算,设A、B、C、D是U上任意四个集合。 若A B， C D，那么，(A C) (B D) 证明：对于A C上的任意元素x，则有x A x C ： 1) 若x A，因为 A B，所以x

18、 B，所以x B D 2) 若x C，因为 C D，所以x D，所以x B D 若A B， C D，那么，(A C) (B D),2020年7月26日星期日,交并差运算,设A、B是U上任意两个集合。 若A B，那么，A B B， A B A 证明：因为 A B，并且B B，所以A B B B 即A B B 推论：A U = U ， A U = A,2020年7月26日星期日,交并差运算,设A、B、C、D是U上任意四个集合。 A - (B C) = (A - B) (A - C) 证明：对于U上的任意元素x，有： x A - (B C) x A (x B x C ) x A x B x C (x

19、 A x B) (x A x C) x (A - B) (A - C) A - (B C) = (A - B) (A - C),2020年7月26日星期日,交并差运算,定义：设A是含有元素为集合的集合，或集合族。 A的并是集合，记为 AA = x|( B)( BA xB ) = B,BA,A的交是集合，记为 A A = x|( B)( BA xB ) = B,BA,2020年7月26日星期日,交并差运算,例3.2.2设A=a, 1, 2, 2, 3, 6，则 A = A =, 1, 2 2, 3 = 1, 2, 3 , 1, 2 2, 3 = 2 ,例3.2.3设B= a, b, c, b,

20、c, d, c, d, e ，则 B = B =,a, b, c b, c, d c, d, e = a,b,c,d,e ,a, b, c b, c, d c, d, e = c ,2020年7月26日星期日,练习,设A、B、C、D是自然数上的集合，定义如下 A=1, 2, 7, 8 B= i | i 2 50 C= i | i 可以整除30 D= i | i=2kkI0 k 6 求： A (B (C D) A (B (C D) B - (A C),=0, 1, 2, 3, 4, 5, 6, 7,=1, 2, 3, 5, 6, 10, 15, 30,=1,2,4,8,16,32,64,=0,

21、1, 2, 3, 4, 5, 6, 7, 8, 10, 15, 16, 30, 32, 64,=1, 2,=0, 4,2020年7月26日星期日,补,定义：集合A的补是集合，记为A。 A = U - A = x| x U x A= x| x A A也叫绝对补，有的书上记为 A,2020年7月26日星期日,补,例3.2.4 若U=p, q, r, s，A=p, q，那么A=r, s 若U=N，A=x|x0，那么A=0 若U=Z，A=2x|x Z，那么A=2x+1 |x Z,2020年7月26日星期日,补,定理：对于任意给定的集合A，都有 A A = U A A = 证明：对于任意 x U，有：

22、x A A x A x A x A x A T x U x A A x A x A x A x A F x ,2020年7月26日星期日,补,定理：对于任意给定的集合A和B B = A ( A B = U ) ( A B= ) 证明：必要性证明略（使用前面的定理）。 充分性：设A B = U且A B= ，那么 B = U B = ( A A ) B = ( A B ) ( A B ) = ( A B ) = ( A A ) ( A B ) = A ( A B ) = A U = A 该定理说明了补的唯一性。若A的补是B，则B的补是A 推论：U = ， = U,2020年7月26日星期日,补,定

23、理：对于任意给定的集合A，则 A = A 。 证明： A A = U，A A = ，所以A是A的补 定理：（德摩根律）任意集合A和B，则 (A B) = A B (A B) = A B 证明：对于任意x x (A B) x (A B) ( x (A B) ) ( x A x B) (x A) (x B) (x A) (x B) x (A B),2020年7月26日星期日,对称差,定义：对于任意集合A和B，A和B的对称差是集合，记为A B。 A B = ( A B ) ( B A ) = x|(x A x B)(x B x A),2020年7月26日星期日,对称差,定理：对于任意集合A和B，都有

24、： A B = ( A B ) ( A B ) = ( A B ) ( A B ) 证明： A B = ( A B ) ( B A ) = ( A B ) ( B A ) = ( A B ) B) ( A B ) A) = ( A B ) ( A B ) = ( A B ) (A B) = ( A B ) ( A B ),2020年7月26日星期日,对称差,推论：对于任意集合A和B，都有： A B = A B A B = B A A A = ,2020年7月26日星期日,集合公式,可以按照下列规则生成集合公式： 单个集合变元是集合合式公式 若A是集合合式公式，则A也是集合合式公式 若A和B是集

25、合合式公式，则(A B)、(A B)、(A - B)和(A B)也是集合合式公式 只有有限次使用上述规则构成的字符串才是集合合式公式,2020年7月26日星期日,对偶原理,定义：用任意集合常元取代两个集合公式中的各个集合变元，若所得的集合是相等的，则称这两个集合公式是相等的。简称等式。 对偶原理：设E为集合等式，将E中的、U和的每一次出现分别代以、 和U后得到另一个等式E*，称E*为E的对偶式。,2020年7月26日星期日,集合的容斥原理,在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所

26、有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。,如果被计数的事物有A、B两类，A类B类元素个数总和= A类元素个数+ B类元素个数既是A类又是B类的元素个数,若被计数的事物有A、B、C三类，则A、B、C三类元素个数总和 = A类元素个数+ B类元素个数+C类元素个数 既是A类又是B类的元素个数既是A类又是C类的元素个数 既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数,2020年7月26日星期日,集合的容斥原理,例.计算机系三年级一班共有30名学生，在学完英语的基础上，本学期又开了俄、法、日三门外语以供

27、选修。班上选修俄、法语各14人，选修日语有15人，同时选修俄、法语和法、日语的各有6人，同时选修俄、日语的有7人，三门全选的只有3人，试求该班中本学期未选修外语的人数。,解：设A、B、C是集合，A代表选修俄语的学生，B代表选修法语的学生，C代表选修日语的学生 |A|=14 |B|=14 |C|=15 |A B | =6 |B C | =6 |A C | =7 | A B C |=3,2020年7月26日星期日,|A|=14 |B|=14 |C|=15 |A B | =6 |B C | =6 |A C | =7 | A B C |=7,三集合容斥原理问题。解容斥原理的方法主要有两种，一种是画文氏

28、图，还有一种是理解并牢记容斥原理的两个核心公式： （1）两个集合的容斥关系公式：|AB|=A+B-AB （2）三个集合的容斥关系公式： |ABC|=A+B+|C|-AB-|AC|-|BC|+|ABC| 由容斥公式可知，选课的人数共有14+14+15-6-6-7+3=27人，所以答案为30-27=3。 此题也可以用文氏图的方法解答,2020年7月26日星期日,第三节 笛卡尔积与无序积,第三节 笛卡尔积与无序积 定义： 两个元素a和b组成二元组，若它们有次序之别，称为有序对（或二元有序组、序偶），记为，a和b分别称为第一分量和第二分量。当ab时， 若它们没有次序区分，称为无序对（或二元无序组），记

29、为(a, b)。当ab时，(a, b) = (b, a),2020年7月26日星期日,有序对,定义： 给定的两个有序对和，有：= (x=u) (y=v) 推广到n元有序组，有：= (x1= y1) (x2= y2) (xn= yn),2020年7月26日星期日,笛卡尔积,定义：给定集合A和B，若有序对的第一分量是A的元素，第二分量是B的元素，所有这些有序对的集合，称为A和B的笛卡尔积，记为AB。 AB = |x A y B 推广：集合A1, A2, , An的笛卡尔积是 Ai = (A1A2An-1)An= | ai Ai 1 i n,2020年7月26日星期日,笛卡尔积,例3.3.1 设A=

30、a, b, B=1, 2, 3，有： AB=, BA=, AA=, 若C= ，则 AC = ,2020年7月26日星期日,笛卡尔积,当A和B是实数集合，AB能代表笛卡儿平面的点的集合 例3.3.2 设A=x|1 x 2, B=y|0 y，有： AB=| 1 x 2 0 y BA=| 1 x 2 0 y,1,2,y,x,1,2,x,y,2020年7月26日星期日,笛卡尔积,定理：对于任意给定集合A、B和C，有： A(B C)=(AB) (AC) A(B C)=(AB) (AC) (A B) C = (AC) (BC) (A B) C = (AC) (BC),2020年7月26日星期日,无序积,定义：给定集合A和B，若无序对是由A中元素和B中元素组成，所有这些无序对的集合，称为A和B的无序积，记为A&B。A&B = (x, y)|x A y B 例3.3.3 设A=a, b, B=1, 2, 3，有： A&B=(a,1),(a,2),