离散数学集合证明.ppt

关于离散数学集合证明 2022-12-27 《集合论与图论》第4讲 1 第一页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 2 集合恒等式(关于与) 等幂律(idempotent laws) AA=A AA=A 交换律(commutative laws) AB=BA AB=BA 第二页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第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) 第三页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 4 集合恒等式(关于与 、续) 吸收律(absorption laws) A(AB)=A A(AB)=A 第四页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 5 集合恒等式(关于~) 双重否定律(double complement law) ~~A=A 德●摩根律(DeMorgan’s laws) ~(AB)=~A~B ~(AB)=~A~B 第五页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 6 集合恒等式(关于与E) 零律(dominance laws) AE=E A= 同一律(identity laws) A=A AE=A 第六页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 7 集合恒等式(关于,E) 排中律(excluded middle) A~A = E 矛盾律(contradiction) A~A =  全补律 ~ = E ~E =  第七页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 8 集合恒等式(关于-) 补交转换律(difference as intersection) A-B=A~B 第八页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 9 集合恒等式(推广到集族) 分配律 德●摩根律 第九页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 10 对偶(dual)原理 对偶式(dual): 一个集合关系式, 如果只含有, ,~,, E,=, , 那么, 同时把与互换, 把与E互换, 把与互换, 得到的式子称为原式的对偶式. 对偶原理: 对偶式同真假. 或者说, 集合恒等式的对偶式还是恒等式. 第十页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 11 对偶原理(举例) 分配律 A  (B  C) = (A  B )  (A  C ) A  (B  C) = (A  B )  (A  C ) 排中律 A  ~A=E 矛盾律 A  ~A=  第十一页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 12 对偶原理(举例、续) 零律 A  E =E A   =  同一律 A   =A A  E=A 第十二页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 13 对偶原理(举例、续) A  B  A A  B  A   A E  A 第十三页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 14 集合恒等式证明(方法) 逻辑演算法: 利用逻辑等值式和推理规则 集合演算法: 利用集合恒等式和已知结论 第十四页，共六十三页，2022年，8月28日 2022-12-27 《集合论与图论》第4讲 15 逻辑演算法(格式) 题目: A=B. 证明: x, xA  … (????)  xB  A=B. # 题目: AB. 证明: x, xA  … (????)  xB  AB. # 第十五页，共六十三页，2022年，8月28日 2022-1