集合的运算-集合与关系-离散数学

集合的运算第1页一、定义设A、B是两个集合，={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈B={x|xA∧xB}x∈A∩Bx∈A∧x∈B={x|x∈A∧xB}x∈A-Bx∈A∧xB={x|x∈E∧xA}={x|xA}x∈~AxA(x∈A)={x|((xA)∧(xB))∨((xB)∧(xA))}AB=(A-B)∪(B-A)AB=(A∪B)-(A∩B)EAB差集EAB交集补集EA并集EAB(1)并集A∪B(2)交集A∩B(3)差集A-B(4)补集~A(5)对称差集AB第2页例：A={4,{1,2},{3}},B={{3},{1,2,3},4,{1,2},{1}}则：A∩B={4,{1,2},{3}}=AA∪B={4,{1,2},{3},{1,2,3},{1}}=BA-B=ΦB-A={{1,2,3},{1}}第3页二、集合的运算律等幂律:A∪A=A；A∩A=A；交换律:A∪B=B∪A;A∩B=B∩A结合律:A∪(B∪C)=(A∪B)∪C；A∩(B∩C)=(A∩B)∩C；恒等律:A∪Φ=A；A∩E=A；零律:A∪E=E；A∩Φ=Φ；分配律:A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)吸收律:A∩(A∪B)=A;A∪(A∩B)=A；集合的运算律是指集合的交、并、补、差等运算的主要性质，也称为集合的基本定律。第4页定理否定律：~~A=A；德摩根定律：~(A∩B)=~A∪~B~(A∪B)=~A∩~B矛盾律：A∩~A＝Φ；排中律：A∪~A＝E。其他：A-A=Φ；A-B=A-(A∩B)；A-B=A∩~B;(A-B)-C=A-(B∪C)；A∪(B-A)=A∪B；EAB第5页三、证明集合相等的四种方法方法一：命题演算法（逻辑等价式和推理规则）方法二：等式代入法(假设交换律、分配律、同一律、零律已经成立)方法三：证明出：AB且BA，则A=B。方法四：反证法第6页三、证明集合相等的四种方法方法一：命题演算法（逻辑等价式和推理规则）例：证明A∪(A∩B)=A（吸收律）证任取x,x(A∪(A∩B))xA∨x(A∩B)xA∨(xA∧xB)xA因此得A∪(AB)=A。方法二：等式代入法(假设交换律、分配律、同一律、零律已经成立)例证明吸收律A∪(A∩B)=(A∩E)∪(A∩B)=A∩(E∪B)=A∩E=A第7页集合等式的证明方法三：证明出：AB且BA，则A=B依据：定理3-1.1A=B，当且仅当AB且BA。例如：（P91定理3-2.5的证明方法）方法四：反证法假设不等，推出矛盾。第8页分析：(x)(x∈A∩Bx∈A)(x)(x∈Ax∈B)证明：A∩B=A，(x)(x∈A∩Bx∈A)(x)((x∈A∩Bx∈A)∧(x∈Ax∈A∩B))(x)((xA∩B∨x∈A)∧(xA∨x∈A∩B))(x)(((x∈A∧x∈B)∨x∈A)∧(xA∨(x∈A∧x∈B))(x)(((xA∨xB)∨x∈A)∧(xA∨(x∈A∧x∈B)))(x)(T∧(T∧(xA∨x∈B)))(x)(xA∨x∈B)(x)(x∈Ax∈B)AB证明P90定理3-2.3：A∩B=AAB第9页四、证明AB的四种方法：方法一：A和B是用枚举方式定义的：依次检查A的每个元素是否在B中出现。方法二：通过集合运算判断AB：即A∪B=B,A∩B=A,AB=三个等式中有一个为真，则AB。方法三：通过文氏图判断集合的包含（注意这里是判断，而不是证明）方法四：A和B是谓词定义的，且A和B中元素的性质分别为P和Q：（即：A={x|P(x)}B={x|Q(x)}利用的定义证明（按定义证明法）。第10页按定义证明的方法若定义中有“若…则…”来描述的，则在证明时应采用离散数学中特有的按定义证明方法即证明时，首先叙述定义的前半部分“若…”，将这部分的内容称为“附加的已知条件”，此时利用该“附加的已知条件”和题目本身所给的已知条件证明出定义的后半部分“则…”，这部分的内容称为定义中的结论。这种证明问题的方法在于：证明时不能单纯利用题目所给的已知条件，而应同时利用定义中的“已知”，推出的并非整个定义，而是定义中的结论。这与一般的证明思路：已知→中间结果→结论是完全不同的。本章的证明大部分都采用按定义证明方法。利用的定义证明：AB定义：AB(x)(x∈Ax∈B)证明：假设(x)(x∈A)，利用题目中的已知条件和已有的定理和公理去推出即(x)(x∈B)，从而证明AB。注意：若已知AB，则可以设(x)(x∈A)(x)(x∈B)第11页六、证明集合不等的方法证AB：方法一：举例或画文氏图示意。方法二：转化为证明逻辑判断式不等价。A≠B(x)(xA且xB)∨(x)(xB且xA)方法三：反证法，假设A=B，推出矛盾。五、判断客体a是否是集合A元素的基本方法：把a作为一个整体，检查它在A中是否出现。第12页七、证明集合A是空集的方法方法一：其逻辑判断条件是永假。Φ={x|P(x)∧P(x)}方法二：用反证法：设aA，引出矛盾的结果。第13页自学求证(A-B)-C=(A-C)-(B-C)证明：任取x，x∈(A-C)-(B-C)x∈(A-C)∧x(B-C)(x∈A∧xC)∧(x∈B∧xC)(x∈A∧xC)∧(xB∨x∈C)(x∈A∧xC∧xB)∨(x∈A∧xC∧x∈C)x∈A∧xC∧xBx∈A∧xB∧xC(x∈A∧xB)∧xCx∈A-B∧xCx∈(A-B)-C所以(A-B)-C=(A-C)-(B-C)第14页自学A-(B∩C)=(A-B)∪(A-C)A-(B∪C)=(A-B)∩(A-C)证明：任取x∈A-(B∪C)x∈A∧x(B∪C)x∈A∧(x∈B∨x∈C)x∈A∧(xB∧xC)(x∈A∧xB)∧(x∈A∧xC)x∈A-B∧x∈A-Cx∈(A-B)∩(A-C)所以A-(B∪C)=(A-B)∩(A-C))A∩(B-C)=(A∩B)-(A∩C)但∪对-是不可分配的，如A∪(A-B)=A，而(A∪A)-(A∪B)=Φ注意:这不是分配律第15页自学证明：AB~B~A证明：AB(x)(x∈Ax∈B)(x)(xBxA)x(x∈~Bx∈~A)~B~A∴AB~B~A证明：德摩根定律(1)~(A∩B)=~A∪~B(2)~(A∪B)=~A∩~B证明:(1)：任取x∈~(A∩B)x∈~(A∩B)xA∩B(x∈A∧x∈B)(xA)∨(xB)(x∈~A)∨(x∈~B)x∈(~A∪~B)∴~(A∩B)=~A∪~B第16页自学~A=B当且仅当A∪B=E且A∩B=Φ证明：(A∪B=E)∧(A∩B=Φ)(x)(x∈A∪Bx∈E)∧(PT=P)(x)(x∈A∩Bx∈Φ)(PF=P)(x)(x∈A∪BT)∧x(x∈A∩BF)(x)(x∈A∪B∧(x∈A∩B))(x)((x∈A∨x∈B)∧(x∈A∧x∈B))(x)((x∈A∨x∈B)∧(xA∨xB))(x)((xAx∈B)∧(x∈BxA))(x)((x∈~Ax∈B)∧(x∈Bx∈~A))(x)((x∈~Ax∈B)~A=B第17页