离散数学课件3.1集合的概念和表示法-3.2集合的运算

2020/4/30,1,离散数学(DiscreteMathematics),2020/4/30,1,2020/4/30,2,2020/4/30,2,第二篇集合论,集合论是从集合出发，来定义数及其运算，进而发展到整个数学。按现代数学的观点，数学各分支的研究对象或者本身都是带有某种特定结构的集合，如群、环、拓扑空间等，或者是可以通过集合来定义的。从这个意义上说，集合论可以看做是整个现代数学的基础。它的基本概念已经渗透到数学的所有领域，如古典分析、泛函、概率、函数论等。,2020/4/30,3,2020/4/30,3,1集合的概念和表示法2集合的运算34序偶与笛卡尔集5关系及其表示6关系的性质7复合关系和逆关系8关系的闭包运算910等价关系与划分11相容关系与覆盖12偏序关系,第三章集合与关系,2020/4/30,4,2020/4/30,4,一、基本概念二、集合的表示方式三、集合间的关系四、几类特殊的集合,3.1集合概念及其表示法,2020/4/30,5,2020/4/30,5,一、基本概念,集合由某些特殊对象汇集在一起构成的整体。研究对象的全体用大写字母表示。如N:自然数集，I：整数集，Q：有理数集，R：实数集。元素：组成集合的单个体称为集合的元素通常用小写字母表示。例如，集合A中的某个元素a二者关系若个体a是集合A的元素，称a属于A,记作“aA”否则称a不属于集合A，记作有限集：集合中的元素个数是有限的。无限集：集合中的元素个数是无限的。,3.1集合概念及其表示法,2020/4/30,6,2020/4/30,6,二、集合的表示方法,列举法将构成集合的元素列出来，元素之间用逗号隔开，并用花括号括起来。例如：A=a,b,c,d,B=4,5,6,7,8叙述法：P(x)表示谓词，描述元素的共同特征。A=xP(x)表示集合当且仅当个体a使P(a)成立时，aA，否则。B=xxN且4x8C=2xiZ+,即C=20,21,22,23,D=2xxZ+且x50,即D=0,2,4,6,98,100,3.1集合概念及其表示法,集合中的元素彼此不同，且无顺序要求集合中的元素也可以是集合,本法可能会出现悖论。著名的“理发师悖论”：“我要给所有不给自己刮脸的人刮脸，而不给给自己刮脸的人刮脸”,2020/4/30,7,2020/4/30,7,练习,2,3,5,7,11,13,17,19-3,-1,1,3,2x|xZ+且x1002n|nN且n10,2020/4/30,8,2020/4/30,8,例如设A=a,b,c,d,B=a,e,x,y,z,C=a,x则,集合的包含设A、B是任意两个集合，如果A的每一个元素都是B的成员，则称A是B的子集，记作或，读作“A包含在B内”或“B包含A”。如果A不是B的子集，则记作。（判断子集的方法）性质对任意集合A，；对任意集合A，；对任意集合A、B、C，若则,3.1集合概念及其表示法,三、集合间的关系：集合的包含和相等是集合间的两个基本关系,2020/4/30,9,2020/4/30,9,例如设A=x|xN且x能整除24，B=1,2,3,4,6,8,12,24则A=B又例如（1）a,b,c=b,c,a（2）a,b,c,c=a,b,c（3）a,b,ca,b,c（4）,两集合相等设A、B是任何两个集合，若且，即A、B有相同的成员，则称集合A与B相等，记作A=B。（外延性原理）,3.1集合概念及其表示法,三、集合间的关系：集合的包含和相等是集合间的两个基本关系,2020/4/30,10,真子集设集合A、B，若,且AB，则称A是B的真子集，记作，若A不是B的真子集，则记作若，则对，如果则必有,且使得且,3.1集合概念及其表示法,三、集合间的关系：集合的包含和相等是集合间的两个基本关系,例如设A=0，1，B=0，1，2，C=0则但,2020/4/30,11,空集：不含任何元素的集合，称为空集，记作。例如A=x|xR且x2+8=0=定理1：空集是任何集合的子集即推论：空集是唯一的。对于每一个非空集合A，至少有两个不同的子集，A和，称为A的平凡子集。,3.1集合概念及其表示法,四、几类特殊的集合,2020/4/30,12,全集：在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E或U对于任一xA,因,则xE,即恒真。全集相当于论域，即，为任何谓词幂集：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集，记为P(A)P(A)=x|xA注意:xP(A)xA例如:A=a,b的0元子集：，1元子集：a,b，2元子集：为a,b所以：P(A)=,a,b,a,b，共22=4个子集。如果有限集合A有n个元素，则幂集P(A)有2n个元素。,3.1集合概念及其表示法,四、几类特殊的集合,判断：任何集合的幂集一定不是空集。（空集呢？）,2020/4/30,13,2020/4/30,13,例1.设,求A和B的幂集,解对于集合A，它只有一个子集，,即,对于集合B，有,1个元素的子集：，a，a,2个元素的子集：,3个元素的子集：,0个元素的子集：,因此,2020/4/30,14,2020/4/30,14,(1)(2)(3)(4),()()()(),()()()(),Y,Y,Y,Y,Y,Y,N,N,令则,例2.设,B是A的幂集的幂集，判断下列论断是否正确，并将“Y”或“N”填入相应论断后面的括号中。,2020/4/30,15,2020/4/30,15,答案：(),A,B,D,答案：(),A,B,C,练习,B.C.D.,1试判断下列各式是否正确，并将正确的题号填入括号内。,2设,试判断下列各式是否正确，并将正确的题号填入括号内。,B.C.D.,2020/4/30,16,2020/4/30,16,3.2集合的运算,文氏图,例如,U,A,A,B,2020/4/30,17,2020/4/30,17,一、交运算,例如设A=a,b,c,d,B=d,f,a,C=e,f,g,则,交运算性质:,定义1：设有集合A、B，属于A同时又属于B的所有元素组成的集合称为A与B的交集，记作。即,a)AA=A（幂等律）b)A=（零律）c)AE=A（同一律）d)AB=BA（交换律）e)(AB)C=A(BC)（结合律）f),3.2集合的运算,2020/4/30,18,2020/4/30,18,3.2集合的运算,二、并运算,例如设A=a,b,c,B=c,d,f,C=b,e,则,A,B,定义2设有集合A、B，属于A或属于B的所有元素组成的集合称为A与B的并集，记作。即,2020/4/30,19,2020/4/30,19,3.2集合的运算,二、并运算,a)AA=A（幂等律）b)A=A（同一律）c)AE=E（零律）d)AB=BA（交换律）e)(AB)C=A(BC)（结合律）f),并运算的性质,2020/4/30,20,2020/4/30,20,3.2集合的运算,二、并运算,1)设AB,CD,则ACBD2)AB,则ACBC3)分配律4)吸收律5)当且仅当AB=BAB=AAB,并运算的其他性质,2020/4/30,21,2020/4/30,21,定义3设有集合A、B，所有属于B而不属于A的元素组成的集合，称为A相对于B的补集，记作B-A。即,例如设A=a,b,c,d,B=d,f,a,C=e,f,g,B,A,3.2集合的运算,三、相对补运算(差),2020/4/30,22,2020/4/30,22,定义4集合A相对于全集合U的补集称为A的绝对补集，简称为A的补集，记作。即,3.2集合的运算,四、绝对补运算,2020/4/30,23,2020/4/30,23,例如设U=1，2，3，4，10，A=2，4，6，8，10,则,又例如设U=I（I是整数集），,则,2020/4/30,24,2020/4/30,24,定义5：设有集合A、B，所有属于A而不属于B或属于B而不属于A的元素组成的集合，称为A与B的对称差，记作。即,3.2集合的运算,五、对称差运算,2020/4/30,25,2020/4/30,25,六、集合运算的十条定律,对于全集合U的任意子集A、B、C，有：,交换律,结合律,分配律,同一律,3.2集合的运算,2020/4/30,26,2020/4/30,26,互补律,对合律,幂等律,零一律,吸收律,德摩根律,六、集合运算的十条定律,3.2集合的运算,2020/4/30,27,2020/4/30,27,六、集合运算的十条定律,3.2集合的运算,2020/4/30,28,2020/4/30,28,D若，则A=B,练习,1设A、B、C是任意集合，判断下述论断是否正确，并将正确的题号填入括号内。,A若，则B=C,B若，则B=C,C若A-B=A-C，则B=C,(),D,反例设A=a,b,c,B=b,d,C=c,d则但,2020/4/30,29,2020/4/30,29,2设U=1，2，3，4，5，A=2，4，B=4，3，5，C=2，5，3，确定下列集合的元素，将其填入相应的花括号内。,(1),(2),(3),(4),(5),2,1,4,2,3,4,5,4,2020/4/30,30,2020/4/30,30,3设U表示刘平拥有的所有书的集合，其中A是离散数学参考书的集合，B是操作系统参考书的集合，C是今年出版的新书的集合，D是从图书馆借来的书的集合。现知道如下情形：（1）所有离散数学参考书都是今年出版的新书。（）（2）所有操作系统参考书都是从图书馆借来的。（）（3）今年出版的新书不是从图书馆借来的。（）（4）没有一本操作系统的参考书是今年出版的。（）,3,1,5,7,试用集合的方法分别表示上述四种情形，可供选择的答案如下，请从下述答案中挑选出相应表达式的编号填入每一种情形后面的括号中。,2.3.4.5.6.7.,2020/4/30,31,2020/4/30,31,逻辑演算法:根据定义，利用逻辑等价式和逻辑推理规则集合演算法:利用集合恒等式和已知的集合结论,七、集合恒等式的几种证明方法,3.2集合的运算,逻辑演算法(根据定义),题型:A=B.证明：x,xA(?)xBA=B证毕.或证明：x,xA(?)xB.则，AB另，x,xB(?)xA.则，BAA=B证毕.,题型:AB.证明:x,xA(?)xBAB证毕.,3.2集合的运算,例1：分配律(证明)A(BC)=(AB)(AC)证明:x,xA(BC)xAx(BC)(定义)xA(xBxC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)A(BC)=(AB)(AC)成立,逻辑演算法(根据定义),3.2集合的运算,例2：零律(证明)A=证明:x,xAxAx(定义)xAF(定义)F(命题逻辑零律)A=成立,逻辑演算法(根据定义),3.2集合的运算,例3.排中律(证明)AA=E证明:x,xAAxAxA(定义)xAxA(定义)xA(xA)(定义)T(命题逻辑排中律)AA=E成立,逻辑演算法(根据定义),3.2集合的运算,2020/4/30,37,2020/4/30,37,即且，,因此，,故。,反之若，,则且，,即且，,因此。,由上证得，,例4证明,证明若则且，,故。,逻辑演算法(根据定义),集合演算法（格式）,题型:A=B.题型:AB.证明:A证明:A=(?)(?)=BBA=B.#AB.#,3.2集合的运算,例1：吸收律(一式证明)A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB)(逆用分配律)=AE(零律)=A(同一律)A(AB)=A,集合演算法,3.2集合的运算,例2：吸收律(二式证明)A(AB)=A证明:A(AB)