离散数学集合证明.ppt

《离散数学集合证明.ppt》由会员分享，可在线阅读，更多相关《离散数学集合证明.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2020/10/30,集合论与图论第4讲,1,第4讲 集合恒等式,内容提要 1. 集合恒等式与对偶原理 2. 集合恒等式的证明 3. 集合列的极限 4. 集合论悖论与集合论公理,2020/10/30,集合论与图论第4讲,2,集合恒等式(关于与),等幂律(idempotent laws) AA=A AA=A 交换律(commutative laws) AB=BA AB=BA,2020/10/30,集合论与图论第4讲,3,集合恒等式(关于与、续),结合律(associative laws) (AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws) A(BC)=(

2、AB)(AC) A(BC)=(AB)(AC),2020/10/30,集合论与图论第4讲,4,集合恒等式(关于与 、续),吸收律(absorption laws) A(AB)=A A(AB)=A,2020/10/30,集合论与图论第4讲,5,集合恒等式(关于),双重否定律(double complement law) A=A 德摩根律(DeMorgans laws) (AB)=AB (AB)=AB,2020/10/30,集合论与图论第4讲,6,集合恒等式(关于与E),零律(dominance laws) AE=E A= 同一律(identity laws) A=A AE=A,2020/10/30

3、,集合论与图论第4讲,7,集合恒等式(关于,E),排中律(excluded middle) AA = E 矛盾律(contradiction) AA = 全补律 = E E = ,2020/10/30,集合论与图论第4讲,8,集合恒等式(关于-),补交转换律(difference as intersection) A-B=AB,2020/10/30,集合论与图论第4讲,9,集合恒等式(推广到集族),分配律 德摩根律,2020/10/30,集合论与图论第4讲,10,对偶(dual)原理,对偶式(dual): 一个集合关系式, 如果只含有, , E,=, , 那么, 同时把与互换, 把与E互换,

4、把与互换, 得到的式子称为原式的对偶式. 对偶原理: 对偶式同真假. 或者说, 集合恒等式的对偶式还是恒等式.,2020/10/30,集合论与图论第4讲,11,对偶原理(举例),分配律 A (B C) = (A B ) (A C ) A (B C) = (A B ) (A C ) 排中律 A A=E 矛盾律 A A= ,2020/10/30,集合论与图论第4讲,12,对偶原理(举例、续),零律 A E =E A = 同一律 A =A A E=A,2020/10/30,集合论与图论第4讲,13,对偶原理(举例、续),A B A A B A A E A,2020/10/30,集合论与图论第4讲,1

5、4,集合恒等式证明(方法),逻辑演算法: 利用逻辑等值式和推理规则 集合演算法: 利用集合恒等式和已知结论,2020/10/30,集合论与图论第4讲,15,逻辑演算法(格式),题目: A=B. 证明: x, xA (?) xB A=B. #,题目: AB. 证明: x, xA (?) xB AB. #,2020/10/30,集合论与图论第4讲,16,分配律(证明),A(BC)=(AB)(AC) 证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(xAC) (定义) x(AB)(AC) (定义) A(B

6、C)=(AB)(AC),2020/10/30,集合论与图论第4讲,17,零律(证明),A = 证明: x, xA xA x (定义) xA 0 (定义) 0 (命题逻辑零律) A = ,2020/10/30,集合论与图论第4讲,18,排中律(证明),AA = E 证明: x, xAA xA xA (定义) xA xA (定义) xA xA (定义) 1 (命题逻辑排中律) AA = E,2020/10/30,集合论与图论第4讲,19,集合演算法(格式),题目: A=B. 证明: A =(?) =B A=B. #,题目: AB. 证明: A (?) B AB. #,2020/10/30,集合论与

7、图论第4讲,20,吸收律(证明),A(AB)=A 证明: A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = AE (零律) = A (同一律) A(AB)=A,A,B,2020/10/30,集合论与图论第4讲,21,吸收律(证明、续),A(AB) = A 证明: A(AB) = (AA)(AB) (分配律) = A(AB) (等幂律) = A (吸收律第一式) A(AB) = A,A,B,2020/10/30,集合论与图论第4讲,22,集合演算法(格式,续),题目: A=B. 证明: () AB () A B A = B. # 说明: 分=成与,题目: AB. 证明

8、: AB (或AB) =(?) = A (或B) AB. # 说明: 化成= AB=AAB AB=BAB,2020/10/30,集合论与图论第4讲,23,集合恒等式证明(举例),基本集合恒等式 对称差()的性质 集族(AS)的性质 幂集(P( )的性质,2020/10/30,集合论与图论第4讲,24,补交转换律,A-B = AB 证明: x, xA-B xA xB xA xB x AB A-B = AB. #,2020/10/30,集合论与图论第4讲,25,德摩根律的相对形式,A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C) 证明: A-(BC) = A(BC) (补交转

9、换律) = A(BC) (德摩根律) = (AA)(BC) (等幂律) = (AB)(AC) (交换律,结合律) = (A-B)(B-A) (补交转换律). #,2020/10/30,集合论与图论第4讲,26,对称差的性质,交换律: AB=BA 结合律: A(BC)=(AB)C 分配律: A(BC)=(AB)(AC) A=A, AE=A AA=, AA=E,2020/10/30,集合论与图论第4讲,27,对称差的性质(证明2),结合律: A(BC)=(AB)C 证明思路： 分解成 “基本单位”, 例如: 1. ABC 2. A BC 3. A B C 4. ABC,A,B,C,ABC,1,2,

10、3,4,2020/10/30,集合论与图论第4讲,28,对称差的性质(证明2、续1),结合律: A(BC)=(AB)C 证明: 首先, AB = (A-B)(B-A) (定义) = (AB)(BA) (补交转换律) = (AB)(AB) (交换律) (*),AB,A,B,2020/10/30,集合论与图论第4讲,29,对称差的性质(证明2、续2),其次, A(BC) = (A(BC)(A(BC) (*) = (A(BC)(BC) (A(BC)(BC) (*) = (A(BC)(BC) (A(BC)(BC) (德摩根律),2020/10/30,集合论与图论第4讲,30,对称差的性质(证明2、续3

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

12、 (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) A(BC)=(AB)C. #,2020/10/30,集合论与图论第4讲,33,对称差的性质(讨论),有些作者用表示对称差: AB=AB 消去律: AB=AC B=C (习题一,23) A=BC B=AC C=AB 对称差与补: (AB) = AB = AB AB = AB 问题: ABC=ABC ?,2020/10/30,集合论与图论第4讲,34,对称差的性质(讨论、续),如何把对称差推广到n个集合: A1A2A3An = ? x, xA1A2A3An x恰好属于A1,A2,A3,An中的奇数个 特征函数表达: A1A

13、2An(x) = A1(x)+A2(x)+An(x) (mod 2) = A1(x)A2(x)An(x) (mod 2),都表示模2加法,即相加除以2取余数),2020/10/30,集合论与图论第4讲,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) (mod 2) = A(x)B(x),A,B,2020/10/30,集合论与图论第4讲,36,对称差的性质(讨论、续),问题: ABC =

14、ABC ? 答案: ABC = (ABC) = (ABC) = ABC ABCD = ABCD = ABCD = (ABCD) = A = (A),2020/10/30,集合论与图论第4讲,37,对称差的性质(证明3),分配律: A(BC)=(AB)(AC) 证明 A(BC) = A(BC)(BC) = (ABC) (ABC),A,B,C,A(BC),2020/10/30,集合论与图论第4讲,38,对称差分配律(证明3、续),(续) (AB)(AC) = (AB)(AC)(AB)(AC) =(AB)(AC)(AB)(AC) =(ABC)(ABC) A(BC)=(AB)(AC). #,2020/

15、10/30,集合论与图论第4讲,39,对称差分配律(讨论),A(BC)=(AB)(AC) A(BC)=(AB)(AC) ? A(BC)=(AB)(AC) ? A(BC)=(AB)(AC) ?,2020/10/30,集合论与图论第4讲,40,集族的性质,设A,B为集族, 则 1. AB A B 2. AB A B 3. A AB B A 4. AB B A 5. A A A,2020/10/30,集合论与图论第4讲,41,集族的性质(证明1),AB A B 证明: x, xA A(AA xA) (A定义) A(AB xA) (AB) xB (B定义) A B. #,2020/10/30,集合论与

16、图论第4讲,42,集族的性质(证明2),AB A B 证明: x, xA AB xA (AB, 合取) A(AB xA) (EG) xB A B. #,2020/10/30,集合论与图论第4讲,43,集族的性质(证明3),A AB B A 说明: 若约定=E, 则A的条件可去掉. 证明: x, xB y( yB xy ) y( yA xy ) (AB) xA B A . #,2020/10/30,集合论与图论第4讲,44,集族的性质(证明4),AB B A 证明: x, xB y( yB xy ) AB x A (UI) xA (AB) B A . #,2020/10/30,集合论与图论第4讲

17、,45,集族的性质(证明5),A A A 说明: A的条件不可去掉! 证明: A y(yA), 设 AA. x, xA y( yA xy ) AA xA xA (AA) AA xA y( yA xy) x A A A . #,2020/10/30,集合论与图论第4讲,46,幂集的性质,AB P(A)P(B) P(A)P(B) P(AB) P(A)P(B) = P(AB) P(A-B) (P(A)-P(B),2020/10/30,集合论与图论第4讲,47,幂集的性质(证明1),AB P(A)P(B) 证明: () x, xP(A) xA xB (AB) xP(B) P(A)P(B),2020/1

18、0/30,集合论与图论第4讲,48,幂集的性质(证明1、续),AB P(A)P(B) 证明(续): () x, xA xP(A) xP(B) (P(A)P(B) xB AB. #,2020/10/30,集合论与图论第4讲,49,幂集的性质(证明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),2020/10/30,集合论与图论第4讲,50,幂集的性质(证明2、续),P(A)P(B) P(AB) 讨论: 给出反例, 说明等号不成立: A=1, B=2, AB=1,2, P(A)=,1, P(B

19、)=,2, P(AB)= ,1,2,1,2 P(A)P(B) ,1,2 此时, P(A)P(B) P(AB). #,2020/10/30,集合论与图论第4讲,51,幂集的性质(证明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). #,2020/10/30,集合论与图论第4讲,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) x A-

20、B xAxB xP(A)xP(B) xP(A)-P(B) P(A-B) (P(A)-P(B). #,A,B,2020/10/30,集合论与图论第4讲,53,集合运算的优先级,分三级: 第一级最高, 依次降低 第一级: 补, 幂P() 第二级: 广义并, 广义交 第三级: 并, 交, 相对补-, 对称差 同一级: 用括号表示先后顺序,2020/10/30,集合论与图论第4讲,54,集合列的极限,2020/10/30,集合论与图论第4讲,55,集合列的极限,Infinite often( i.o.): Almost everywhere(a.e.),2020/10/30,集合论与图论第4讲,56,

21、集合列的极限,上极限: 下极限:,2020/10/30,集合论与图论第4讲,57,集合列的极限,性质:,2020/10/30,集合论与图论第4讲,58,集合论悖论,罗素悖论(Russells paradox)： S = x | xx SS ? SS SS SS SS,2020/10/30,集合论与图论第4讲,59,集合论公理,外延公理: 所含元素相同的两个集合是相等的 空集存在公理: 空集合存在 无序对公理: 对任意的a,b, a,b存在 并集公理: 对任意的A, A存在 幂集公理: 对任意的A, P(A)存在 联集公理:,2020/10/30,集合论与图论第4讲,60,集合论公理(续),子集公理: xA | P(x) 存在 正则公理: 若S,则 x(xSy(ySxy) 无穷公理: 无穷集存在 替换公理: f(a) | aA 存在 ( f是定义域为A的函数),2020/10/30,集合论与图论第4讲,61,集合论公理(续),选择公理(Zorn引理, 良序原理): A是元素互不相交的集合,则可以从A的每个元素中恰好选择一个元素, 构成一个集合,2020/10/30,集合论与图论第4讲,62,总结,集合恒等式 集合恒等式的证明 集合论悖论,2020/10/30,集合论与图论第4讲,63,作业(#2),p27, 习题一, 11, 13, 14, 20 今天1班交作业(#1),