离散数学集合的基本运算.ppt

3.2 集合的基本运算,集合的交、并、差、补、对称差集合相等的证明,并集union,定义：设A，B是两个集合，所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作AB;AB=xxA xB。,交集intersection,定义：A，B是两个集合，即属于A，又属于B，称为集合A与B的交集，记为AB。即AB=xxA xB,广义的并集,集合的并(union)：集合A和B的并AB定义为：AB=x|xA或者xB，集合的并可推广到多个集合，设A1,A2,An都是集合，它们的并定义为：A1A2An=x|存在某个i，使得xAi,广义的交集,集合的交(intersection)：集合A和B的并AB定义为：AB=x|xA而且xB，集合的交也可推广到多个集合，设A1,A2,An都是集合，它们的交定义为：A1A2An=x|对所有的i，都有xAi,集合的交并例题1,例如：集合A=x-2x2，xR，B=x0 x4,xR求AB，AB。解：AB=x-2x2或0 x4,xR=x-2x4,xRAB=x-2x2且0 x4,xR=x0 x2,xR,集合的交并例题2,设A为奇数集合，B为偶数集合，求AB和AB。解：AB=xx是偶数或x是奇数=Z AB=xx既是偶数又是奇数=,集合的交并例题3,设A1=1，2，3，A2=2，1，3，A3=3，1，2，求A1A2，A1A3，A2 A3。解：三个集合均有两个元素，其中一个元素是数。另一元素是两个数组成的集合，三个集合没有相同元素，A1A2=A2A3=A3A1=,不相交,如AB=称A，B不相交。,集合的差,设A，B是两集合，属于A而不属于B的元素全体称为A与B的差集，记作A-B，即A-B=xxAxB。,补集(complement set),集合A的补集，记为A，是那些不属于集合A的元素所构成的集合，即A=x|xA。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。显然，A=E-A。,可知：xA xA xA,求证A-B=AB,证明 A-B=x|xA-B=xxAxB=xxAxB=AB,当A，B不相交时，A-B=A，B-A=B,对称差,定义：设A，B是两集合，集合（A-B）（B-A）称为集合A，B的对称差，记作AB。即AB=xxA且x BxB且x A=x(xAx B)(xBx A)AB=(AB)-(AB),对称差举例,例1、A=a,b,e B=a,c,d解：B-A=c,d A-B=b,e，AB=c,d,b,e 例2、A=xx-2,xR,E=xx2求A，AA。解：A=xx-2=x-2x2，xRA-A=AA=(A-A)(A-A)=,集合运算性质（运算律）,1、交换律AB=BA，AB=BA2、结合律（AB）C=A（BC）（AB）C=A（B C）3、分配律 A（BC）=（AB）（AC）A（BC）=（AB）（AC)4、幂等律 AA=A，AA=A5、同一律 A=A,AE=A 9、德摩根律（AB）=AB 6、零一律 A=，AE=E（AB）=AB 7、补余律 AA=，AA=E 10、双重否定律（A）=A 8、吸收律 A（AB）=A 注：A-B=AB A（AB）=A,集合相等的证明的方法,一、利用集合的定义证明；二、利用集合等式证明；（常用）三、利用谓词公式证明；四、用集合成员表。（略）,证明：A（BC）=（AB）（AC）,(1)xA(BC),分两种情况(a)如xAxAB且x AC x(AB)(AC)(b)如x A,则xBCxB且xC xAB且xAC x(AB)(AC)任何情况下均有x(AB)(AC)A(BC)(AB)(AC),证明：A（BC）=（AB）（AC）(续),(2)x(AB)(AC)xAB且xAC 分两种情况(a)若xA,则xA(BC)(b)若x A，由x A,xABxB,由x A,xACxC xBCxA(BC)任何情况均有xA(BC)(AB)(AC)A(BC)(1)(2)合并为 A（BC）=（AB）（AC）,求证：A-(BC)=(A-B)(A-C),证明：x(A-B)(A-C)，则x(A-B)x(A-C)（xA)(xB)(xA)(xC)（xA)(xB)(xC)（xA)(xB)(xC)（xA)(xBxC)(xA)(xBC)x A-(BC)从而，A-(BC)=(A-B)(A-C),利用谓词公式证明求证：A-(BC)=(A-B)(A-C),证明：(A-B)(A-C)x|x(A-B)(A-C)=x|x(A-B)x(A-C)=x|xA(xB)(xA)(xC)=x|(xA)(xB)(xC)=x|(xA)(xB)(xC)=x|（xA)(xBxC)=x|(xA)(xBC)=x|x A-(BC)=(A-B)(A-C),利用集合等式证明求证：A-(BC)=(A-B)(A-C),(A-B)(A-C)ABAC=ABC=A(BC)=A-(BC),证明吸收律A（AB）=A,证明：A（AB）=（A）（AB）=A（B）=A=A,已知AB=AC,AB=AC,求证B=C,证明:B=B(AB)(吸收律)=B(AC)(等量代入)=(BA)(BC)(分配律)=(AC)(BC)(等量代入)=(AB)C(分配律)=(AC)C(等量代入)=C(吸收律)说明:AB=ACB=C AB=ACB=C 两种推理均是不成立的。,课堂练习,用三种方法求证：(B-A)A=BA,集合的化简,化简(ABC)(AB)-(A(B-C)A)证明:原集合=(AB)-A(吸收律)=(AB)A=(AA)(BA)(分配律)=(BA)(互补律)=BA(同一律),集合包含的性质,AE如果ABC，则ACABAABAB AB=B AB=A B A,集合包含的证明,方法：一、包含的定义；xA，最后x B；二、利用已知等式和包含性质 A B AB=B AB=A A-B=B A,例题：证明：A，B是集合，AB P（A）P(B）,uP(A)uA,AB uB,uP（B）从而P(A)P(B),xAxAxP(A),P(A)P(B)xP(B)xBAB。,另外 AP(A),P(A)P(B)AP(B)AB。,例题：证明：如果AB，那么B A,证明：B A=(BA)=A 从而 B A,求证：如果A B，则P(A)P(B),证明：(使用定义：x左，最后x 右)x P(A)，则x A，又由已知A B，所以x B 从而x P(B)。P(A)P(B),例题,设F表示一年级大学生的集合，S表示二年级大学生的集合，R表示计算机系学生的结合，M表示数学系学生的集合，T表示选修离散数学的学生的集合，L表示爱好文学的学生的集合，P表示爱好体育的学生的集合。则下列句子所对应的集合表达式为：,1）所有计算机系二年级的学生都选修离散数学。R S T 2）数学系的学生或者爱好文学或者爱好体育运动。M LP 3）数学系一年级的学生都没有选修离散数学。,4）只有一、二年级的学生才爱好体育运动。5）除去数学系和计算机系二年级的学生外都不选离散数学。只有数学系和计算机系二年级的学生才选离散数学。T(MR)S,