北京大学：《离散数学》系列课程之一《集合论与图论》第4讲 集合恒等式

第4讲集合恒等式 内容提要 1.集合恒等式与对偶原理 2.集合恒等式的证明 秦3.集合列的极限 4.集合论悖论与集合论公理 《集合论与图论》第4讲

《集合论与图论》第4讲 1 第4讲 集合恒等式 内容提要 1. 集合恒等式与对偶原理 2. 集合恒等式的证明 3. 集合列的极限 4. 集合论悖论与集合论公理

集合恒等式(关于∪与⌒) 等幂律( idempotent laws A∪A=A AOA=A 秦交换律( commutative laws) A∪B=BA AoB=BOA 《集合论与图论》第4讲

《集合论与图论》第4讲 2 集合恒等式(关于∪与∩) 等幂律(idempotent laws) A∪A=A A∩A=A 交换律(commutative laws) A∪B=B∪A A∩B=B∩A

集合恒等式(关于∪与∩、续) 合律( associative laws) (AB八C=A∪(B∪C) (ABC=A(B∩C) 秦分配律( distributive laws A∪(BC)=(A∪B)(AC A⌒(BUC)=(AB)(A⌒C) 《集合论与图论》第4讲

《集合论与图论》第4讲 3 集合恒等式(关于∪与∩、续) 结合律(associative laws) (A∪B)∪C=A∪(B∪C) (A∩B)∩C=A∩(B∩C) 分配律(distributive laws) A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C)

集合恒等式(关于∪与∩、续) 秦吸收律( absorption laws) AU(AnB=A A⌒(AB)=A 《集合论与图论》第4讲

《集合论与图论》第4讲 4 集合恒等式(关于∪与∩ 、续) 吸收律(absorption laws) A∪(A∩B)=A A∩(A∪B)=A

集合恒等式(关于-) 双重否定律( double complement law AA 德●摩根律( DeMorgan|aws) (A∪B)=~A~B (A⌒B=~A~B 《集合论与图论》第4讲

《集合论与图论》第4讲 5 集合恒等式(关于~) 双重否定律(double complement law) ~~A=A 德●摩根律(DeMorgan’s laws) ~(A∪B)=~A∩~B ~(A∩B)=~A∪~B

集合恒等式(关于与E) 零律( dominance laws) AUE=E AO=o 同一律( dentity laws) AUO=A AOE=A 《集合论与图论》第4讲

《集合论与图论》第4讲 6 集合恒等式(关于∅与E) 零律(dominance laws) A∪E=E A∩∅=∅ 同一律(identity laws) A∪∅=A A∩E=A

集合恒等式(关于②E) 排中律( excluded middle) A∪~A=E 矛盾律( contradiction) AOA=o 全补律 E=O 《集合论与图论》第4讲

《集合论与图论》第4讲 7 集合恒等式(关于∅,E) 排中律(excluded middle) A∪~A = E 矛盾律(contradiction) A∩~A = ∅ 全补律 ~∅ = E ~E = ∅

集合恒等式(关于-) 交转换律( fference as intersection) A-B=AoB 《集合论与图论》第4讲

《集合论与图论》第4讲 8 集合恒等式(关于-) 补交转换律(difference as intersection) A-B=A∩~B

集合恒等式(推广到集族) 婚分配律 B∪(4{An}as)=4(B∪An) a∈ B∩(;{A} aNaes/ (B∩An) a∈S 德●摩根律 (iAajaes =4( aa) a∈S afa∈S ∈S B-(Aaes )=4(b-A a∈ B-(4(Aaes )=i(B-A) a∈ 《集合论与图论》第4讲

《集合论与图论》第4讲 9 集合恒等式(推广到集族) 分配律 德●摩根律 ( { } ) ( ) α α B Aα α B A S ∪ S = ∪ ∈ I ∈ I ( { } ) ( ) α α B Aα α B A S ∩ S = ∩ ∈ U ∈ U ( { } ) ( ) α α B Aα α B A S − S = − ∈ I ∈ U ( { } ) ( ) α α B Aα α B A S − S = − ∈ U ∈ I ~ ( { } ) (~ ) α α Aα α A S S ∈ U ∈ = I ~ ( { } ) (~ ) α α Aα α A S S ∈ I ∈ = U

对偶(ua)原理 对偶式(dua):一个集合关系式,如果只 含有⌒,∪,~,O,E,=,c,那么,同时把∪与 ∩互换,把⑦与E互换,把c与互换,得到 的式子称为原式的对偶式 对偶原理:对偶式同真假.或者说,集合 恒等式的对偶式还是恒等式 《集合论与图论》第4讲

《集合论与图论》第4讲 10 对偶(dual)原理 对偶式(dual): 一个集合关系式, 如果只 含有∩, ∪,~,∅, E,=, ⊆, 那么, 同时把∪与 ∩互换, 把∅与E互换, 把⊆与⊇互换, 得到 的式子称为原式的对偶式. 对偶原理: 对偶式同真假. 或者说, 集合 恒等式的对偶式还是恒等式.