离散数学集合证明.ppt

《离散数学集合证明.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4讲集合恒等式内容提要1.集合恒等式与对偶原理2.集合恒等式的证明3.集合列的极限4.集合论悖论与集合论公理2021/7/271《集合论与图论》第4讲集合恒等式(关于与)等幂律(idempotentlaws)AA=AAA=A交换律(commutativelaws)AB=BAAB=BA2021/7/272《集合论与图论》第4讲集合恒等式(关于与、续)结合律(associativelaws)(AB)C=A(BC)(AB)C=A(BC)分配律(distributivelaws)A(BC)=(AB)(

2、AC)A(BC)=(AB)(AC)2021/7/273《集合论与图论》第4讲集合恒等式(关于与、续)吸收律(absorptionlaws)A(AB)=AA(AB)=A2021/7/274《集合论与图论》第4讲集合恒等式(关于~)双重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(AB)=~A~B~(AB)=~A~B2021/7/275《集合论与图论》第4讲集合恒等式(关于与E)零律(dominancelaws)AE=EA=同一律(identi

3、tylaws)A=AAE=A2021/7/276《集合论与图论》第4讲集合恒等式(关于,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=全补律~=E~E=2021/7/277《集合论与图论》第4讲集合恒等式(关于-)补交转换律(differenceasintersection)A-B=A~B2021/7/278《集合论与图论》第4讲集合恒等式(推广到集族)分配律德●摩根律2021/7/279《集合论与图论》第4讲对偶(dual)原理对偶式(dual):一个集合关系式,如果

4、只含有,,~,,E,=,,那么,同时把与互换,把与E互换,把与互换,得到的式子称为原式的对偶式.对偶原理:对偶式同真假.或者说,集合恒等式的对偶式还是恒等式.2021/7/2710《集合论与图论》第4讲对偶原理(举例)分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律A~A=E矛盾律A~A=2021/7/2711《集合论与图论》第4讲对偶原理(举例、续)零律AE=EA=同一律A=AAE=A2021/7/2712《集合论与图论》第4讲对偶原理(举例、续)ABAA

5、BAAEA2021/7/2713《集合论与图论》第4讲集合恒等式证明(方法)逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集合恒等式和已知结论2021/7/2714《集合论与图论》第4讲逻辑演算法(格式)题目:A=B.证明:x,xA…(????)xBA=B.#题目:AB.证明:x,xA…(????)xBAB.#2021/7/2715《集合论与图论》第4讲分配律(证明)A(BC)=(AB)(AC)证明:x,xA(BC)xAx(BC)(定义)xA(xBxC)

6、(定义)(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)2021/7/2716《集合论与图论》第4讲零律(证明)A=证明:x,xAxAx(定义)xA0(定义)0(命题逻辑零律)A=2021/7/2717《集合论与图论》第4讲排中律(证明)A~A=E证明:x,xA~AxAx~A(定义)xAxA(~定义)xAxA(定义)1(命题逻

7、辑排中律)A~A=E2021/7/2718《集合论与图论》第4讲集合演算法(格式)题目:A=B.证明:A=…(????)=BA=B.#题目:AB.证明:A…(????)BAB.#2021/7/2719《集合论与图论》第4讲吸收律(证明)A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=AAB2021/7/2720《集合论与图论》第4讲吸收律(证明、续)A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A

8、(AB)(等幂律)=A(吸收律第一式)A(AB)=AAB2021/7/2721《集合论与图论》第4讲集合演算法(格式,续)题目:A=B.证明:()…AB()…ABA=B.