离散数学 集合证明PPT课件

2020/5/28,.,1,第4讲集合恒等式,内容提要1.集合恒等式与对偶原理2.集合恒等式的证明3.集合列的极限4.集合论悖论与集合论公理,2020/5/28,.,2,集合恒等式(关于与),等幂律(idempotentlaws)AA=AAA=A交换律(commutativelaws)AB=BAAB=BA,2020/5/28,.,3,集合恒等式(关于与、续),结合律(associativelaws)(AB)C=A(BC)(AB)C=A(BC)分配律(distributivelaws)A(BC)=(AB)(AC)A(BC)=(AB)(AC),2020/5/28,.,4,集合恒等式(关于与、续),吸收律(absorptionlaws)A(AB)=AA(AB)=A,2020/5/28,.,5,集合恒等式(关于),双重否定律(doublecomplementlaw)A=A德摩根律(DeMorganslaws)(AB)=AB(AB)=AB,2020/5/28,.,6,集合恒等式(关于与E),零律(dominancelaws)AE=EA=同一律(identitylaws)A=AAE=A,2020/5/28,.,7,集合恒等式(关于,E),排中律(excludedmiddle)AA=E矛盾律(contradiction)AA=全补律=EE=,2020/5/28,.,8,集合恒等式(关于-),补交转换律(differenceasintersection)A-B=AB,2020/5/28,.,9,集合恒等式(推广到集族),分配律德摩根律,2020/5/28,.,10,对偶(dual)原理,对偶式(dual):一个集合关系式,如果只含有,E,=,那么,同时把与互换,把与E互换,把与互换,得到的式子称为原式的对偶式.对偶原理:对偶式同真假.或者说,集合恒等式的对偶式还是恒等式.,2020/5/28,.,11,对偶原理(举例),分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律AA=E矛盾律AA=,2020/5/28,.,12,对偶原理(举例、续),零律AE=EA=同一律A=AAE=A,2020/5/28,.,13,对偶原理(举例、续),ABAABAAEA,2020/5/28,.,14,集合恒等式证明(方法),逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集合恒等式和已知结论,2020/5/28,.,15,逻辑演算法(格式),题目:A=B.证明:x,xA(?)xBA=B.#,题目:AB.证明:x,xA(?)xBAB.#,2020/5/28,.,16,分配律(证明),A(BC)=(AB)(AC)证明:x,xA(BC)xAx(BC)(定义)xA(xBxC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)A(BC)=(AB)(AC),2020/5/28,.,17,零律(证明),A=证明:x,xAxAx(定义)xA0(定义)0(命题逻辑零律)A=,2020/5/28,.,18,排中律(证明),AA=E证明:x,xAAxAxA(定义)xAxA(定义)xAxA(定义)1(命题逻辑排中律)AA=E,2020/5/28,.,19,集合演算法(格式),题目:A=B.证明:A=(?)=BA=B.#,题目:AB.证明:A(?)BAB.#,2020/5/28,.,20,吸收律(证明),A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=A,A,B,2020/5/28,.,21,吸收律(证明、续),A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A(AB)(等幂律)=A(吸收律第一式)A(AB)=A,A,B,2020/5/28,.,22,集合演算法(格式,续),题目:A=B.证明:()AB()ABA=B.#说明:分=成与,题目:AB.证明:AB(或AB)=(?)=A(或B)AB.#说明:化成=AB=AABAB=BAB,2020/5/28,.,23,集合恒等式证明(举例),基本集合恒等式对称差()的性质集族(AS)的性质幂集(P()的性质,2020/5/28,.,24,补交转换律,A-B=AB证明:x,xA-BxAxBxAxBxABA-B=AB.#,2020/5/28,.,25,德摩根律的相对形式,A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明:A-(BC)=A(BC)(补交转换律)=A(BC)(德摩根律)=(AA)(BC)(等幂律)=(AB)(AC)(交换律,结合律)=(A-B)(B-A)(补交转换律).#,2020/5/28,.,26,对称差的性质,交换律:AB=BA结合律:A(BC)=(AB)C分配律:A(BC)=(AB)(AC)A=A,AE=AAA=,AA=E,2020/5/28,.,27,对称差的性质(证明2),结合律:A(BC)=(AB)C证明思路：分解成“基本单位”,例如:1.ABC2.ABC3.ABC4.ABC,A,B,C,ABC,1,2,3,4,2020/5/28,.,28,对称差的性质(证明2、续1),结合律:A(BC)=(AB)C证明:首先,AB=(A-B)(B-A)(定义)=(AB)(BA)(补交转换律)=(AB)(AB)(交换律)(*),AB,A,B,2020/5/28,.,29,对称差的性质(证明2、续2),其次,A(BC)=(A(BC)(A(BC)(*)=(A(BC)(BC)(A(BC)(BC)(*)=(A(BC)(BC)(A(BC)(BC)(德摩根律),2020/5/28,.,30,对称差的性质(证明2、续3),=(A(BC)(BC)(A(BC)(BC)=(A(BC)(BC)(A(BC)(BC)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配律),2020/5/28,.,31,对称差的性质(证明2、续4),同理,(AB)C=(AB)C)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(德摩根律),2020/5/28,.,32,对称差的性质(证明2、续5),=(AB)(AB)C)(AB)(AB)C)=(AB)(AB)C)(AB)(AB)C)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配律)A(BC)=(AB)C.#,2020/5/28,.,33,对称差的性质(讨论),有些作者用表示对称差:AB=AB消去律:AB=ACB=C(习题一,23)A=BCB=ACC=AB对称差与补:(AB)=AB=ABAB=AB问题:ABC=ABC?,2020/5/28,.,34,对称差的性质(讨论、续),如何把对称差推广到n个集合:A1A2A3An=?x,xA1A2A3Anx恰好属于A1,A2,A3,An中的奇数个特征函数表达:A1A2An(x)=A1(x)+A2(x)+An(x)(mod2)=A1(x)A2(x)An(x)(mod2),都表示模2加法,即相加除以2取余数),2020/5/28,.,35,特征函数与集合运算:,AB(x)=A(x)B(x)A(x)=1-A(x)A-B(x)=AB(x)=A(x)(1-B(x)AB(x)=(A-B)B(x)=A(x)+B(x)-A(x)B(x)AB(x)=A(x)+B(x)(mod2)=A(x)B(x),A,B,2020/5/28,.,36,对称差的性质(讨论、续),问题:ABC=ABC?答案:ABC=(ABC)=(ABC)=ABCABCD=ABCD=ABCD=(ABCD)=A=(A),2020/5/28,.,37,对称差的性质(证明3),分配律:A(BC)=(AB)(AC)证明A(BC)=A(BC)(BC)=(ABC)(ABC),A,B,C,A(BC),2020/5/28,.,38,对称差分配律(证明3、续),(续)(AB)(AC)=(AB)(AC)(AB)(AC)=(AB)(AC)(AB)(AC)=(ABC)(ABC)A(BC)=(AB)(AC).#,2020/5/28,.,39,对称差分配律(讨论),A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?,2020/5/28,.,40,集族的性质,设A,B为集族,则1.ABAB2.ABAB3.AABBA4.ABBA5.AAA,2020/5/28,.,41,集族的性质(证明1),ABAB证明:x,xAA(AAxA)(A定义)A(ABxA)(AB)xB(B定义)AB.#,2020/5/28,.,42,集族的性质(证明2),ABAB证明:x,xAABxA(AB,合取)A(ABxA)(EG)xBAB.#,2020/5/28,.,43,集族的性质(证明3),AABBA说明:若约定=E,则A的条件可去掉.证明:x,xBy(yBxy)y(yAxy)(AB)xABA.#,2020/5/28,.,44,集族的性质(证明4),ABBA证明:x,xBy(yBxy)ABxA(UI)xA(AB)BA.#,2020/5/28,.,45,集族的性质(证明5),AAA说明:A的条件不可去掉!证明:Ay(yA),设AA.x,xAy(yAxy)AAxAxA(AA)AAxAy(yAxy)xAAA.#,2020/5/28,.,46,幂集的性质,ABP(A)P(B)P(A)P(B)P(AB)P(A)P(B)=P(AB)P(A-B)(P(A)-P(B),2020/5/28,.,47,幂集的性质(证明1),ABP(A)P(B)证明:()x,xP(A)xAxB(AB)xP(B)P(A)P(B),2020/5/28,.,48,幂集的性质(证明1、续),ABP(A)P(B)证明(续):()x,xAxP(A)xP(B)(P(A)P(B)xBAB.#,2020/5/28,.,49,幂集的性质(证明2),P(A)P(B)P(AB)证明:x,xP(A)P(B)xP(A)xP(B)xAxBxABxP(AB)P(A)P(B)P(AB),2020/5/28,.,50,幂集的性质(证明2、续),P(A)P(B)P(AB)讨论:给出反例,说明等号不成立:A=1,B=2,AB=1,2,P(A)=,1,P(B)=,2,P(AB)=,1,2,1,2P(A)P(B),1,2此时,P(A)P(B)P(AB).#,2020/5/28,.,51,幂集的性质(证明3),P(A)P(B)=P(AB)证明:x,xP(A)P(B)xP(A)xP(B)xAxBxABxP(AB)P(A)P(B)=P(AB).#,2020/5/28,.,52,幂集的性质(证明4),P(A-B)(P(A)-P(B)证明:x,分两种情况,(1)x=,这时xP(A-B)并且x(P(A)-P(B)(2)x,这时xP(A-B)xA-BxAxBxP(A)xP(B)xP(A)-P(B)P(A-B)(P(A)-P(B).#,A,B,2020/5/28,.,53,集合运算的优先级,分三级:第一级最高,依次降低第一级:补,幂P()第二级:广义并,广义交第三级:并,交,相对补-,对称差同一级:用括号表示先后顺序,2020/5/28,.,54,集合列的极限,2020/5/28,.,55,集合列的极限,Infiniteoften(i.o.):Almosteverywhere(a.e.),2020/5/28,.,56,集合列的极限,上极限:下极限:,2020/5/28,.,57,集合列的极限,性质:,2020/5/28,.,58,集合论悖论,罗素悖论(Russellsparadox)：S=x|xxSS?SSSSSSSS,2020/5/28,.,59,集合论公理,外延公理:所含元素相同的两个集合是相等的空集存在公理:空集合存在无序对公理:对任意的a,b,a,b存在并集公理:对任意的A,A存在幂集公理:对任意的A,P(A)存在联集公理:,2020