离散数学32集合的运算.ppt

第三章 集合与关系3-2 集合的运算授课人：李朔Email:chn.nj.1集合的运算以给定的集合为对象,按照确定的规则得到另一些集合集合的另一种表示法是文氏图文氏图（Venn Diagram）人们常用文氏图描述集合运算和它们之间的关系集合的文氏图画法如下： 用矩形表示全集E，在矩形中画一些圆表示其它集合，不同的圆代表不同的集合如果没有特别说明，任何两个圆彼此相交例如，AB的文氏图如图2一、交一、交P87 定义定义3-2.1 设A，B是集合，由A与B的公共元素组成的集合，称为A和B的交集，记为A∩B A∩B=x |xA∧xB 交集的定义如图右图所示 从交集的定义可以得到： A∩BA，A∩BB 例例1 例例2 例例3 及性质及性质P87 *如果A与B无公共元素，即A∩B=Æ，则称A和B是互不相交的 例如，令A=a,b,c，B=d,e，则A∩B=Æ，A和B是互不相交的3一、并一、并P88 定义定义3-2.2 设A，B是任意的集合，由A中的元素或B中的元素组成的集合，称为A和B的并集并集，记为A∪B。

A∪B=x |xA∨xB 并集的定义如右图所示 并集的定义可以得到： AA∪B，BA∪BP88 例题 集合并运算性质 定理3-2.1 3-2.24三、补（差）P90 定义定义3-2.3 设A，B是集合，属于A的而不属于B的元素组成的集合，称为B对于A的补集补集，也叫B对于A的相对补集相对补集记为A-B A-B=x |xA∧xB A-B也称集合集合A和和B的差的差 相对补集定义如右图所示 例如，令A=Æ,Æ，B=Æ，则 A-B=Æ,Æ-Æ=Æ,Æ 又如，令C=a，D= a,b，则 C-D =a-a,b=Æ C-C= ÆP90 例题3、4 5四、绝对补定义定义3-2.4 设A是集合，A对于全集E的相对补集，称为A的绝对补绝对补，记为~A ~A=E-A=x |xE∧xA=x | xA ~A的定义如图所示 例如，令全集E=1,2,3,4，A= 1,2,3，则 ~A=1,2,3,4-1,2,3=4P90 绝对补运算性质6四、绝对补例设A,B是任意的集合，求证: A-B= A∩(~B) 证明： xA-BxA∧xBxA∧x~B xA∩~B即 A-B A∩~B。

xA∩~BxA∧x~BxA∧xBxA-B 故 A∩~BA-B 所以，A-B= A∩(~B) A- -B=A∩(~B)是一个重要的公式，在集合的运算中经常用是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换绝对补和交运算到，它的意义在于将相对补运算转换绝对补和交运算P91 定理定理3-2.5 设设A、、B为任意两个集合，则下列关系式成立：为任意两个集合，则下列关系式成立：a)A-B= A∩~Bb)A-B=A-(A∩B)P91定理定理3-2.6 交运算对差运算的分配交运算对差运算的分配P91 定理定理3-2.7 7五、对称差 P92 定义定义3-2.5 设A，B是集合，由 A中元素或B中元素，但不是A与B的公共元素组成的集合，称为A和B的对称差对称差，记为A B A B=x |xA xB=(A-B)∪(B-A)=(A∪B)-(A∩B) A B的定义如图所示 例如，令A=1,2,3,4， B= 1,2,5,6，则 A B=A∪B-A∩B =1,2,3,4,5,6-1,2 =3,4,5,68五、对称差 例例 设A,B是任意的集合，求证: A B=(A-B)∪(B-A)=(A∩~B)∪(B∩~A)。

证明：先证AB=(A-B)∪(B-A) xA B(xA) (xB) ((xA)∧(xB))∨((xA)∧(xB))  (xA∧xB)∨(xA∧xB)  xA-B∨xB-A  x(A-B)∪(B-A) 所以，A B=(A-B)∪(B-A) 再证(A-B)∪(B-A)=(A∩~B)∪(B∩~A) 很容易得到此结论，这里从略9五、对称差利用例3.7中的公式可以证明对称差A  B下列的性质设A,B是任意的集合 ①A A= Æ 证明：A A=(A-A)∪(A-A) =Æ  Æ=Æ ②A Æ = A 证明：A Æ=(A-Æ)∪(Æ-A)=A∪Æ =A ③AE=~ A 证明：A E=(A-E)∪(E-A)= Æ∪~ A=~ A此外： 满足交换律结合律P94 图3-2.7及结论10六、五种集合运算的性质对以上运算，可知其具性质：1）幂等幂等：AA=A，AA=A2）交换交换：AB=BA，AB=BA3）结合结合：（AB）C=A（BC） （AB）C=A（BC）4）分配分配：A（BC）=（AB）（AC） A（ BC）=（AB）（AC）5）吸收吸收：A（AB）=A A（AB）=A11六、五种集合运算的性质6）互补：A  A=，A  A=E7）德摩根：（AB）=A  B（AB）=A  B8）同一：A  =A，EA=A9）零律：AE=E，A  =10）双重否定：（A）=A11）E=12）  =E*以上共21个性质，都须证明12六、五种集合运算的性质例如：证明分配律A（BC）=（AB）（AC） 证：任取aA(BC) 即aA且aBC 即aA且aB或aC 即aA且aB或aA且aC 即是aAB或aAC 就是a(AB)(AC)  A(BC)(AB)(AC)反之，任取 a (AB)(AC) 即a AB或a AC 就是a A且aB或a A且aC 即a A且aB或aC  a A(BC) A(BC) (AB)(AC)  A(BC)= (AB)(AC)13练习例1：设F表示一年级大学生的集合，S表示二年级大学生的集合，R表示计算机科学系学生的集合，M表示数学系学生的集合，T表示选修离散数学学生的集合，L表示爱好文学学生的集合，P表示爱好体育运动学生的集合。

则下列各句子所对应的集合表达式分别是：（1）所有计算机科学系二年级的学生都选修离散数学A）（2）数学系的学生或者爱好文学或者爱好体育运动B）（3）数学系一年级的学生都没有选修离散数学C）（4）只有一、二年级的学生才爱好体育运动D）（5）除去数学系和计算机科学系二年级的学生外都不选修离散数学E）14练习答案答案：A：RST； B：MLP；C：(MF)T=； D：PFS；E：T(MR)S1）计算机系二年级学生的集合为RS，选修离散数学的学生集合为T，前者为后者子集2）数学系学生集合为M，爱好文学或爱好体育学生集合为LP，前者为后者子集3）数学系一年级学生集合为MF,选修离散数学学生集合为T，这两个集不相交4）只有P才Q，这种句型的逻辑含义是如果Q则P所以这句话可理解为：爱好体育的学生一定是一、二年级的学生爱好体育的学生构成集P，一、二年的学生构成集FS，前者为后者子集5）除去P都不Q，这种句型的逻辑含义可理解为如果Q则P原来句子就变为：选修离散数学的学生都是数学系和计算机系二年级的学生所以T(MR)S15练习例2：设S1＝{1,2,…,8,9}, S2={2,4,6,8}, S3={1,3,5,7,9}, S4={3,4,5}, S5={3,5}确定在以下条件下x可能与S1,…,S5中哪个集合相等。

1）若x S5=  ，则（A）2）若xS4但xS2= ，则（B）3）若xS1且xS3，则（C）（4）若x-S3=，则（D）（5）若xS3且x S1，则（E）16练习答案：A：x = S2 ；B：x = S5 C：x = S1 , S2或S4；D：x = S3或S5：x与其中任何集合都不相等分析：（1）与S5不相交的集合不含3和5，只能是S22）只有S4和S5是S4的子集，但S4S2   ，所以S5满足要求3）xS3意味着x中必含有偶数，S1 , S2和S4中含有偶数并且都是S1的子集4）由x-S3=知xS3因此x可能是S3或S55）由于S3S1，所以有xS3S1与xS1矛盾x与这5个集合中的任一个都不相等17练习例 某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人问两次考试中都为优的有多少人？（用文氏图解） 18练习例 某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人问两次考试中都为优的有多少人？解：设A，B分别表示第一次和第二次考试中成绩为优的学生集合。

画出文氏图，如图3.7所示首先填A∩B中的人数，这正是要求的，设为xA-B中的人数是26-x， B-A中的人数是21-x，分别填入对应的区域并列出如下 方程： (26-x)＋x＋(21-x)＋17=50 解得：x=14 19约定和说明•为了使集合的表达式更加简洁，我们对集集合运算的优先顺序规定合运算的优先顺序规定如下：• 绝对补的运算级别比其它的4个运算高，先进行绝对补运算，再进行其它的4个运算；其它的4个运算的运算顺序由括号决定 •由于并运算满足结合律，故约定以下的符号：• 由于交运算满足结合律，故约定以下的符号：20约定和说明•说明说明：用文氏图不仅可以表示集合的运算和它们之间的关系，而且还可以很方便地解决有限集合的计数问题用文氏图解决有限集合的计数问题的方法是：每一条性质定义一个集合，画一个圆表示这个集合如果没有特别说明，任何两个圆画成相交的将已知集合的元素数填入表示该集合的区域内通常从n个集合的交集填起，根据计算的结果逐步将数字填入其它各空白区域内 如果交集的值是未知的，可以设为x根据题目的条件，列出方程或方程组，求出所需的结果。

21约定和说明还有一些关于集合运算的重要结果例如：还有一些关于集合运算的重要结果例如： A∩BA A∩BB AA∪B BA∪B A-BA A BA∪B(何时相等？ A、B不相交时） A BA∪∪B=BA∩B=AA- -B=ÆÆ A B=A CB=C22本课小结集合的并，交，差，补，对称差 集合运算的性质文氏图的有限集合计数23作业P95 （5）24。