离散数学---集合的基本运算

3.2集合的基本运算集合的交、并、差、补、对称差集合相等的证明并集union定义：设A，B是两个集合，所有属于A或属于B的元素组成的集合，称为集合A与B的并集，记作AB;AB={xxAxB}。ABE交集intersection定义：A，B是两个集合，即属于A，又属于B，称为集合A与B的交集，记为AB。即AB={xxAxB}EAB广义的并集集合的并(union)：集合A和B的并AB定义为：AB={x|xA或者xB}，集合的并可推广到多个集合，设A1,A2,…,An都是集合，它们的并定义为：A1A2∪…An={x|存在某个i，使得xAi}广义的交集集合的交(intersection)：集合A和B的并AB定义为：AB={x|xA而且xB}，集合的交也可推广到多个集合，设A1,A2,…,An都是集合，它们的交定义为：A1∩A2∩…∩An={x|对所有的i，都有xAi}集合的交并例题1例如：集合A={x-2＜x＜2，xR}，B={x0≤x≤4,xR}求A∪B，A∩B。解：A∪B={x-2＜x＜2或0≤x≤4,xR}={x-2＜x≤4,xR}A∩B={x-2＜x＜2且0≤x≤4,xR}={x0≤x＜2,xR}01234-1-2-3集合的交并例题2设A为奇数集合，B为偶数集合，求A∪B和A∩B。解：A∪B={xx是偶数或x是奇数}=ZA∩B={xx既是偶数又是奇数}=集合的交并例题3设A1={1，{2，3}}，A2={2，{1，3}}，A3={3，{1，2}}，求A1∩A2，A1∩A3，A2∩A3。解：三个集合均有两个元素，其中一个元素是数。另一元素是两个数组成的集合，三个集合没有相同元素，∴A1∩A2=A2∩A3=A3∩A1=不相交如A∩B=称A，B不相交。集合的差设A，B是两集合，属于A而不属于B的元素全体称为A与B的差集，记作A-B，即A-B={xxA∧xB}。EAB补集(complementset)集合A的补集，记为∼A，是那些不属于集合A的元素所构成的集合，即∼A={x|xA}。通常来说，是在存在一个全集U的情况下讨论集合的补集。全集U是所讨论的问题域中所有元素所构成的集合。显然，A=E-A。AE可知：x∈∼AxAx∈A求证A-B=AB证明A-B={x|xA-B}={xxA∧xB}={xxA∧xB}=AB当A，B不相交时，A-B=A，B-A=BEAB对称差定义：设A，B是两集合，集合（A-B）（B-A）称为集合A，B的对称差，记作AB。即AB={xxA且xBxB且xA}={x(xA∧xB)(xB∧xA)}AB=(AB)-(AB)EAB对称差举例例1、A={a,b,e}B={a,c,d}解：B-A={c,d}A-B={b,e}，AB={c,d,b,e}例2、A={xx-2,xR},E={xx≤2}求A，AA。解：A={xx-2}={x-2≤x≤2，xR}A-A=∴AA=(A-A)(A-A)==集合运算性质（运算律）1、交换律A∪B=B∪A，A∩B=B∩A2、结合律（A∪B）∪C=A∪（B∪C）（A∩B）∩C=A∩（B∩C）3、分配律A∪（B∩C）=（A∪B）∩（A∪C）A∩（B∪C）=（A∩B）∪（A∩C)4、幂等律A∪A=A，A∩A=A5、同一律A∪=A,A∩E=A9、德摩根律（A∪B）=A∩B6、零一律A∩=，A∪E=E（A∩B）=A∪B7、补余律A∩A=，A∪A=E10、双重否定律（A）=A8、吸收律A∪（A∩B）=A注：A-B=A∩BA∩（A∪B）=A集合相等的证明的方法一、利用集合的定义证明；二、利用集合等式证明；（常用）三、利用谓词公式证明；四、用集合成员表。（略）证明：A∪（B∩C）=（A∪B）∩（A∪C）(1)xA(BC),分两种情况(a)如xAxAB且xACx(AB)(AC)(b)如xA,则xBCxB且xCxAB且xACx(AB)(AC)任何情况下均有x(AB)(AC)A(BC)(AB)(AC)证明：A∪（B∩C）=（A∪B）∩（A∪C）(续)(2)x(AB)(AC)xAB且xAC分两种情况(a)若xA,则xA(BC)(b)若xA，由xA,xABxB,由xA,xACxCxBCxA(BC)任何情况均有xA(BC)(AB)(AC)A(BC)(1)(2)合并为A（BC）=（AB）（AC）求证：A-(B∪C)=(A-B)∩(A-C)证明：x(A-B)∩(A-C)，则x(A-B)∧x(A-C)（xA)∧(xB)∧(xA)∧(xC)（xA)∧(xB)∧(xC)（xA)∧(xB)∧(xC)（xA)∧(xB∨xC)(xA)∧(xB∪C)xA-(B∪C)从而，A-(B∪C)=(A-B)∩(A-C)利用谓词公式证明求证：A-(B∪C)=(A-B)∩(A-C)证明：(A-B)∩(A-C)＝{x|x(A-B)∩(A-C)}={x|x(A-B)∧x(A-C)}={x|xA∧(xB)∧(xA)∧(xC)}={x|(xA)∧(xB)∧(xC)}={x|(xA)∧(xB)∧(xC)}={x|（xA)∧(xB∨xC)}={x|(xA)∧(xB∪C)}={x|xA-(B∪C)}=(A-B)∩(A-C)利用集合等式证明求证：A-(B∪C)=(A-B)∩(A-C)(A-B)∩(A-C)＝A∩~B∩A∩~C=A∩~B∩~C=A∩~(B∪C)=A-(B∪C)证明吸收律A（AB）=A证明：A（AB）=（A）（AB）=A（B）=A=A已知AB=AC,AB=AC,求证B=C证明:B=B(AB)(吸收律)=B(AC)(等量代入)=(BA)(BC)(分配律)=(AC)(BC)(等量代入)=(AB)C(分配律)=(AC)C(等量代入)=C(吸收律)说明:AB=ACB=CAB=ACB=C两种推理均是不成立的。课堂练习用三种方法求证：(B-A)∪A=B∪A集合的化简化简((ABC)(AB))-((A(B-C))A)证明:原集合=(AB)-A(吸收律)=(AB)A=(AA)(BA)(分配律)=(BA)(互补律)=BA(同一律)集合包含的性质•AE•如果ABC，则AC•ABAA∪B•ABA∪B=BAB=A~B~A集合包含的证明方法：一、包含的定义；xA，最后xB；二、利用已知等式和包含性质ABA∪B=BA∩B=AA-B=∼B∼A例题：证明：A，B是集合，ABP（A）P(B）uP(A)∴uA,∵AB∴uB,∴uP（B）从而P(A)P(B)xA∴{x}A∴{x}P(A),∵P(A)P(B)∴{x}P(B)∴xB∴AB。另外∵AP(A),P(A)P(B)∴AP(B)∴AB。例题：证明：如果AB，那么∼B∼A证明：∼B∪∼A=∼(B∩A)=∼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L∪P④3）数学系一年级的学生都没有选修离散数学。Ｍ∩Ｆ～Ｔ③4）只有一、二年级的学生才爱好体育运动。ＰＦ∪Ｓ⑤5）除去数学系和计算机系二年级的学生外都不选离散数学。只有数学系和计算机系二年级的学生才选离散数学。T(M∪R)∩S①