北大集合论与图论4.pptx

《北大集合论与图论4.pptx》由会员分享，可在线阅读，更多相关《北大集合论与图论4.pptx（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/2/22集合论与图论第4讲1集合恒等式集合恒等式(关于关于 与与)等幂律(idempotent laws)AA=AAA=A交换律(commutative laws)AB=BAAB=BA第1页/共63页2023/2/22集合论与图论第4讲2集合恒等式集合恒等式(关于关于 与与、续续)结合律(associative laws)(AB)C=A(BC)(AB)C=A(BC)分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)第2页/共63页2023/2/22集合论与图论第4讲3集合恒等式集合恒等式(关于关于 与与 、续续)吸收律(absorpt

2、ion laws)A(AB)=AA(AB)=A第3页/共63页2023/2/22集合论与图论第4讲4集合恒等式集合恒等式(关于关于)双重否定律(double complement law)A=A德摩根律(DeMorgans laws)(AB)=AB(AB)=AB第4页/共63页2023/2/22集合论与图论第4讲5集合恒等式集合恒等式(关于关于与与E)零律(dominance laws)AE=EA=同一律(identity laws)A=AAE=A第5页/共63页2023/2/22集合论与图论第4讲6集合恒等式集合恒等式(关于关于,E)排中律(excluded middle)AA=E矛盾律(c

3、ontradiction)AA=全补律=EE=第6页/共63页2023/2/22集合论与图论第4讲7集合恒等式集合恒等式(关于关于-)补交转换律(difference as intersection)A-B=AB第7页/共63页2023/2/22集合论与图论第4讲8集合恒等式集合恒等式(推广到集族推广到集族)分配律德摩根律第8页/共63页2023/2/22集合论与图论第4讲9对偶对偶(dual)原理原理对偶式(dual):一个集合关系式,如果只含有,E,=,那么,同时把与互换,把与E互换,把与互换,得到的式子称为原式的对偶式.对偶原理:对偶式同真假.或者说,集合恒等式的对偶式还是恒等式.第9页

4、/共63页2023/2/22集合论与图论第4讲10对偶原理对偶原理(举例举例)分配律A (B C)=(A B)(A C)A (B C)=(A B)(A C)排中律A A=E矛盾律A A=第10页/共63页2023/2/22集合论与图论第4讲11对偶原理对偶原理(举例、续举例、续)零律A E=EA =同一律A =AA E=A第11页/共63页2023/2/22集合论与图论第4讲12对偶原理对偶原理(举例、续举例、续)A B AA B A AE A第12页/共63页2023/2/22集合论与图论第4讲13集合恒等式证明集合恒等式证明(方法方法)逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集

5、合恒等式和已知结论第13页/共63页2023/2/22集合论与图论第4讲14逻辑演算法逻辑演算法(格式格式)题目:A=B.证明:x,xA (?)xB A=B.#题目:AB.证明:x,xA (?)xB AB.#第14页/共63页2023/2/22集合论与图论第4讲15分配律分配律(证明证明)A(BC)=(AB)(AC)证明:x,xA(BC)xA x(BC)(定义)xA (xB xC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)A(BC)=(AB)(AC)第15页/共63页2023/2/22集合论与图论第4讲16零律零律(证明证明)A=证

6、明:x,xA xA x (定义)xA 0 (定义)0 (命题逻辑零律)A=第16页/共63页2023/2/22集合论与图论第4讲17排中律排中律(证明证明)AA=E证明:x,xAA xA xA (定义)xA xA (定义)xA xA (定义)1 (命题逻辑排中律)AA=E第17页/共63页2023/2/22集合论与图论第4讲18集合演算法集合演算法(格式格式)题目:A=B.证明:A =(?)=B A=B.#题目:AB.证明:A (?)B AB.#第18页/共63页2023/2/22集合论与图论第4讲19吸收律吸收律(证明证明)A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB

7、)(分配律)=AE (零律)=A (同一律)A(AB)=AAB第19页/共63页2023/2/22集合论与图论第4讲20吸收律吸收律(证明、续证明、续)A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A(AB)(等幂律)=A (吸收律第一式)A(AB)=AAB第20页/共63页2023/2/22集合论与图论第4讲21集合演算法集合演算法(格式格式,续续)题目:A=B.证明:()AB ()A B A=B.#说明:分=成与题目:AB.证明:AB(或AB)=(?)=A(或B)AB.#说明:化成=AB=AABAB=BAB 第21页/共63页2023/2/22集合论与图论第4讲22集合恒等式

8、证明集合恒等式证明(举例举例)基本集合恒等式对称差()的性质集族(AS)的性质幂集(P()的性质第22页/共63页2023/2/22集合论与图论第4讲23补交转换律补交转换律A-B=AB证明:x,xA-B xA xB xA xB xABA-B=AB.#第23页/共63页2023/2/22集合论与图论第4讲24德德 摩根律的相对形式摩根律的相对形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明:A-(BC)=A(BC)(补交转换律)=A(BC)(德摩根律)=(AA)(BC)(等幂律)=(AB)(AC)(交换律,结合律)=(A-B)(A-C)(补交转换律).#第24页/共

9、63页2023/2/22集合论与图论第4讲25对称差的性质对称差的性质1.交换律:AB=BA2.结合律:A(BC)=(AB)C3.分配律:A(BC)=(AB)(AC)4.A=A,AE=A5.AA=,AA=E第25页/共63页2023/2/22集合论与图论第4讲26对称差的性质对称差的性质(证明证明2)结合律:A(BC)=(AB)C证明思路：分解成 “基本单位”,例如:1.ABC 2.A BC 3.A B C 4.ABCABCABC1234第26页/共63页2023/2/22集合论与图论第4讲27对称差的性质对称差的性质(证明证明2、续续1)结合律:A(BC)=(AB)C证明:首先,AB=(A-

10、B)(B-A)(定义)=(AB)(BA)(补交转换律)=(AB)(AB)(交换律)(*)A BAB第27页/共63页2023/2/22集合论与图论第4讲28对称差的性质对称差的性质(证明证明2、续续2)其次,A(BC)=(A(BC)(A(BC)(*)=(A(BC)(BC)(A(BC)(BC)(*)=(A(BC)(BC)(A(BC)(BC)(德摩根律)第28页/共63页2023/2/22集合论与图论第4讲29对称差的性质对称差的性质(证明证明2、续续3)=(A(BC)(BC)(A(BC)(BC)=(A(BC)(BC)(A(BC)(BC)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配

11、律)第29页/共63页2023/2/22集合论与图论第4讲30对称差的性质对称差的性质(证明证明2、续续4)同理,(AB)C =(AB)C)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(德摩根律)第30页/共63页2023/2/22集合论与图论第4讲31对称差的性质对称差的性质(证明证明2、续续5)=(AB)(AB)C)(AB)(AB)C)=(AB)(AB)C)(AB)(AB)C)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配律)A(BC)=(AB)C.#第31页/共63页2023/2/22集合论与图论第4讲32对称

12、差的性质对称差的性质(讨论讨论)有些作者用表示对称差:AB=AB 消去律:AB=AC B=C(习题一,23)A=BC B=AC C=AB对称差与补:(AB)=AB=AB AB=AB问题:ABC=ABC?第32页/共63页2023/2/22集合论与图论第4讲33对称差的性质对称差的性质(讨论、续讨论、续)如何把对称差推广到n个集合:A1A2A3An=?x,xA1A2A3An x恰好属于A1,A2,A3,An中的奇数个特征函数表达:A1A2An(x)=A1(x)+A2(x)+An(x)(mod 2)=A1(x)A2(x)An(x)(mod 2),都表示模2加法,即相加除以2取余数)第33页/共63

13、页2023/2/22集合论与图论第4讲34特征函数与集合运算特征函数与集合运算: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)(mod 2)=A(x)B(x)AB第34页/共63页2023/2/22集合论与图论第4讲35对称差的性质对称差的性质(讨论、续讨论、续)问题:ABC=ABC?答案:ABC=(ABC)=(ABC)=ABC ABCD=ABCD =ABCD=(ABCD)=A=(A)第35页/共63页2023/2/22集合论与图论第4讲36对称

14、差的性质对称差的性质(证明证明3)分配律:A(BC)=(AB)(AC)证明 A(BC)=A(BC)(BC)=(ABC)(ABC)ABCA(BC)第36页/共63页2023/2/22集合论与图论第4讲37对称差分配律对称差分配律(证明证明3、续、续)(续)(AB)(AC)=(AB)(AC)(AB)(AC)=(AB)(AC)(AB)(AC)=(ABC)(ABC)A(BC)=(AB)(AC).#第37页/共63页2023/2/22集合论与图论第4讲38对称差分配律对称差分配律(讨论讨论)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC

15、)?第38页/共63页2023/2/22集合论与图论第4讲39集族的性质集族的性质设A,B为集族集族,则1.AB A B2.AB A B 3.A AB B A4.AB B A5.A A A第39页/共63页2023/2/22集合论与图论第4讲40集族的性质集族的性质(证明证明1)AB A B证明:x,xA A(AA xA)(A定义)A(AB xA)(AB)xB (B定义)A B.#第40页/共63页2023/2/22集合论与图论第4讲41集族的性质集族的性质(证明证明2)AB A B 证明:x,xA AB xA (AB,合取)A(AB xA)(EG)xB A B.#第41页/共63页2023/

16、2/22集合论与图论第4讲42集族的性质集族的性质(证明证明3)A AB B A说明:若约定=E,则A的条件可去掉.证明:x,x B y(yB xy)y(yA xy)(AB)x A B A.#第42页/共63页2023/2/22集合论与图论第4讲43集族的性质集族的性质(证明证明4)AB B A证明:x,x B y(yB xy)AB x A (UI)xA (AB)B A.#第43页/共63页2023/2/22集合论与图论第4讲44集族的性质集族的性质(证明证明5)A A A说明:A的条件不可去掉!证明:A y(yA),设 AA.x,x A y(yA xy)AA xA xA (AA)AA xA

17、y(yA xy)x A A A.#第44页/共63页2023/2/22集合论与图论第4讲45幂集的性质幂集的性质1.AB P(A)P(B)2.P(A)P(B)P(AB)3.P(A)P(B)=P(AB)4.P(A-B)(P(A)-P(B)第45页/共63页2023/2/22集合论与图论第4讲46幂集的性质幂集的性质(证明证明1)AB P(A)P(B)证明:()x,xP(A)xA xB (AB)xP(B)P(A)P(B)第46页/共63页2023/2/22集合论与图论第4讲47幂集的性质幂集的性质(证明证明1、续、续)AB P(A)P(B)证明(续):()x,xA xP(A)xP(B)(P(A)P

18、(B)xB AB.#第47页/共63页2023/2/22集合论与图论第4讲48幂集的性质幂集的性质(证明证明2)P(A)P(B)P(AB)证明:x,xP(A)P(B)xP(A)xP(B)xAxB xAB xP(AB)P(A)P(B)P(AB)第48页/共63页2023/2/22集合论与图论第4讲49幂集的性质幂集的性质(证明证明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,2 P(A)P(B),1,2 此时,P(A)P(B)P(AB).#第49页/共63页2023/2/22集合论与图

19、论第4讲50幂集的性质幂集的性质(证明证明3)P(A)P(B)=P(AB)证明:x,xP(A)P(B)xP(A)xP(B)xA xB x AB xP(AB)P(A)P(B)=P(AB).#第50页/共63页2023/2/22集合论与图论第4讲51幂集的性质幂集的性质(证明证明4)P(A-B)(P(A)-P(B)证明:x,分两种情况,(1)x=,这时 xP(A-B)并且 x(P(A)-P(B)(2)x,这时 xP(A-B)x A-B xAxB xP(A)xP(B)xP(A)-P(B)P(A-B)(P(A)-P(B).#AB第51页/共63页2023/2/22集合论与图论第4讲52集合运算的优先级

20、集合运算的优先级分三级:第一级最高,依次降低第一级:补,幂P()第二级:广义并,广义交 第三级:并,交,相对补-,对称差同一级:用括号表示先后顺序第52页/共63页2023/2/22集合论与图论第4讲53集合列的极限集合列的极限A1A2A3A4A5E第53页/共63页2023/2/22集合论与图论第4讲54集合列的极限集合列的极限Infinite often(i.o.):无穷多次Almost everywhere(a.e.):几乎处处第54页/共63页2023/2/22集合论与图论第4讲55集合列的极限集合列的极限上极限:下极限:第55页/共63页2023/2/22集合论与图论第4讲56集合列

21、的极限集合列的极限性质:第56页/共63页2023/2/22集合论与图论第4讲57集合论悖论集合论悖论罗素悖论(Russells paradox)：S=x|xx SS?SS SSSS SS第57页/共63页2023/2/22集合论与图论第4讲58集合论公理集合论公理外延公理:所含元素相同的两个集合是相等的空集存在公理:空集合存在无序对公理:对任意集合a,b,a,b存在并集公理:对任意集合a,b,ab存在存在幂集公理:对任意集合A,P(A)存在联集公理:对任意集合A,A存在存在第58页/共63页2023/2/22集合论与图论第4讲59集合论公理集合论公理(续续)子集公理模式(分离公理):对任意集

22、合A,B不在P(x)中出现,B=xA|P(x)存在正则公理:若S,则x(xSy(ySxy)无穷公理:无穷集存在替换公理:f是定义域为集合A的函数,f(a)|aA 存在 第59页/共63页2023/2/22集合论与图论第4讲60集合论公理集合论公理(续续)选择公理(Zorn引理,良序原理):A是元素互不相交的集合,则可以从A的每个元素中恰好选择一个元素,构成一个集合第60页/共63页2023/2/22集合论与图论第4讲61总结总结 集合恒等式 集合恒等式的证明 集合论悖论第61页/共63页2023/2/22集合论与图论第4讲62作业作业(#2)p27,习题一,11,13,14,20第62页/共63页2023/2/22集合论与图论第4讲63谢谢您的观看！第63页/共63页