《离散数学第4讲集合恒等式》由会员分享，可在线阅读，更多相关《离散数学第4讲集合恒等式（63页珍藏版）》请在金锄头文库上搜索。
1、第4讲 集合恒等式内容提要 1. 集合恒等式与对偶原理 2. 集合恒等式的证明 3. 集合列的极限 4. 集合论悖论与集合论公理2024/8/121离散数学 集合证明集合恒等式(关于与)等幂律(idempotent laws)AA=AAA=A交换律(commutative laws)AB=BAAB=BA2024/8/122离散数学 集合证明集合恒等式(关于与、续)结合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)2024/8/123离散数学 集合证明集合恒
2、等式(关于与 、续)吸收律(absorption laws)A(AB)=AA(AB)=A2024/8/124离散数学 集合证明集合恒等式(关于)双重否定律(double complement law)A=A德摩根律(DeMorgans laws)(AB)=AB(AB)=AB2024/8/125离散数学 集合证明集合恒等式(关于与E)零律(dominance laws)AE=EA=同一律(identity laws)A=AAE=A2024/8/126离散数学 集合证明集合恒等式(关于,E)排中律(excluded middle)AA = E矛盾律(contradiction)AA = 全补律 =
3、 EE = 2024/8/127离散数学 集合证明集合恒等式(关于-)补交转换律(difference as intersection)A-B=AB2024/8/128离散数学 集合证明集合恒等式(推广到集族)分配律德摩根律2024/8/129离散数学 集合证明对偶(dual)原理对偶式(dual): 一个集合关系式, 如果只含有, , E,=, , 那么, 同时把与互换, 把与E互换, 把与互换, 得到的式子称为原式的对偶式. 对偶原理: 对偶式同真假. 或者说, 集合恒等式的对偶式还是恒等式.2024/8/1210离散数学 集合证明对偶原理(举例)分配律A (B C) = (A B ) (
4、A C )A (B C) = (A B ) (A C )排中律A A=E矛盾律A A= 2024/8/1211离散数学 集合证明对偶原理(举例、续)零律A E =EA = 同一律A =AA E=A2024/8/1212离散数学 集合证明对偶原理(举例、续) A B AA B A AE A2024/8/1213离散数学 集合证明集合恒等式证明(方法)逻辑演算法: 利用逻辑等值式和推理规则集合演算法: 利用集合恒等式和已知结论2024/8/1214离散数学 集合证明逻辑演算法(格式)题目: A=B. 证明: x, xA (?) xB A=B. #题目: AB. 证明: x, xA (?) xB A
5、B. #2024/8/1215离散数学 集合证明分配律(证明)A(BC)=(AB)(AC)证明: x, xA(BC) xA x(BC) (定义) xA (xB xC) (定义) (xAxB)(xAxC) (命题逻辑分配律) (xAB)(xAC) (定义) x(AB)(AC) (定义) A(BC)=(AB)(AC)2024/8/1216离散数学 集合证明零律(证明)A = 证明: x, xA xA x (定义) xA 0 (定义) 0 (命题逻辑零律) A = 2024/8/1217离散数学 集合证明排中律(证明)AA = E证明: x, xAA xA xA (定义) xA xA (定义) xA
6、 xA (定义) 1 (命题逻辑排中律) AA = E2024/8/1218离散数学 集合证明集合演算法(格式)题目: A=B. 证明: A =(?) =B A=B. #题目: AB. 证明: A (?) B AB. #2024/8/1219离散数学 集合证明吸收律(证明)A(AB)=A证明: A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = AE (零律) = A (同一律) A(AB)=AAB2024/8/1220离散数学 集合证明吸收律(证明、续)A(AB) = A证明: A(AB) = (AA)(AB) (分配律) = A(AB) (等幂律) = A (吸收
7、律第一式) A(AB) = AAB2024/8/1221离散数学 集合证明集合演算法(格式,续)题目: A=B. 证明: () AB () A B A = B. #说明: 分=成与题目: AB. 证明: AB (或AB) =(?) = A (或B) AB. #说明: 化成=AB=AABAB=BAB 2024/8/1222离散数学 集合证明集合恒等式证明(举例)基本集合恒等式对称差()的性质集族(AS)的性质幂集(P( )的性质2024/8/1223离散数学 集合证明补交转换律A-B = AB证明: x, xA-B xA xB xA xB x ABA-B = AB. #2024/8/1224离散
8、数学 集合证明德摩根律的相对形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明: A-(BC) = A(BC) (补交转换律) = A(BC) (德摩根律) = (AA)(BC) (等幂律) = (AB)(AC) (交换律,结合律)= (A-B)(B-A) (补交转换律). #2024/8/1225离散数学 集合证明对称差的性质1.交换律: AB=BA2.结合律: A(BC)=(AB)C3.分配律: A(BC)=(AB)(AC)4.A=A, AE=A5.AA=, AA=E2024/8/1226离散数学 集合证明对称差的性质(证明2)结合律: A(BC)=(AB)C证明
9、思路： 分解成 “基本单位”, 例如: 1. ABC 2. A BC 3. A B C 4. ABCABCABC12342024/8/1227离散数学 集合证明对称差的性质(证明2、续1)结合律: A(BC)=(AB)C证明: 首先, AB = (A-B)(B-A) (定义) = (AB)(BA) (补交转换律) = (AB)(AB) (交换律) (*)A BAB2024/8/1228离散数学 集合证明对称差的性质(证明2、续2) 其次, A(BC) = (A(BC)(A(BC) (*) = (A(BC)(BC) (A(BC)(BC) (*) = (A(BC)(BC) (A(BC)(BC) (
10、德摩根律)2024/8/1229离散数学 集合证明对称差的性质(证明2、续3) = (A(BC)(BC) (A(BC)(BC) = (A(BC)(BC) (A(BC)(BC) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律)2024/8/1230离散数学 集合证明对称差的性质(证明2、续4) 同理, (AB)C = (AB)C)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (德摩根律)2024/8/1231离散数学 集合证明对称差的性质(证明2、续5) = (AB)(AB)C) (AB)(A
11、B)C) = (AB)(AB)C) (AB)(AB)C) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) A(BC)=(AB)C. #2024/8/1232离散数学 集合证明对称差的性质(讨论)有些作者用表示对称差: AB=AB 消去律: AB=AC B=C (习题一,23) A=BC B=AC C=AB对称差与补: (AB) = AB = AB AB = AB问题: ABC=ABC ?2024/8/1233离散数学 集合证明对称差的性质(讨论、续)如何把对称差推广到n个集合: A1A2A3An = ? x, xA1A2A3An x恰好属于A1,A2,A3,An中的奇
12、数个特征函数表达: A1A2An(x) = A1(x)+A2(x)+An(x) (mod 2) = A1(x)A2(x)An(x) (mod 2),都表示模2加法,即相加除以2取余数)2024/8/1234离散数学 集合证明特征函数与集合运算: 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)AB2024/8/1235离散数学 集合证明对称差的性质(讨论、续)问题: ABC = ABC
13、? 答案: ABC = (ABC) = (ABC) = ABC ABCD = ABCD = ABCD = (ABCD) =A = (A)2024/8/1236离散数学 集合证明对称差的性质(证明3)分配律: A(BC)=(AB)(AC)证明 A(BC) = A(BC)(BC) = (ABC) (ABC)ABCA(BC)2024/8/1237离散数学 集合证明对称差分配律(证明3、续)(续) (AB)(AC) = (AB)(AC)(AB)(AC) =(AB)(AC)(AB)(AC) =(ABC)(ABC) A(BC)=(AB)(AC). #2024/8/1238离散数学 集合证明对称差分配律(讨
14、论)A(BC)=(AB)(AC) A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ?2024/8/1239离散数学 集合证明集族的性质设A,B为集族集族, 则1. AB A B2. AB A B 3. A AB B A4. AB B A5. A A A2024/8/1240离散数学 集合证明集族的性质(证明1)AB A B证明: x, x A A(AA xA) ( A定义) A(AB xA) (AB) x B ( B定义) A B. #2024/8/1241离散数学 集合证明集族的性质(证明2)AB A B 证明: x, xA AB xA (AB,
15、 合取) A(AB xA) (EG) x B A B. #2024/8/1242离散数学 集合证明集族的性质(证明3)A AB B A说明: 若约定 =E, 则A的条件可去掉.证明: x, x B y( yB xy ) y( yA xy ) (AB) x A B A . #2024/8/1243离散数学 集合证明集族的性质(证明4)AB B A证明: x, x B y( yB xy ) AB x A (UI) xA (AB) B A . #2024/8/1244离散数学 集合证明集族的性质(证明5)A A A说明: A的条件不可去掉!证明: A y(yA), 设 AA. x, x A y( y
16、A xy ) AA xA xA (AA) AA xA y( yA xy) x A A A . #2024/8/1245离散数学 集合证明幂集的性质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)2024/8/1246离散数学 集合证明幂集的性质(证明1)AB P(A)P(B)证明: () x, xP(A) xA xB (AB) xP(B) P(A)P(B)2024/8/1247离散数学 集合证明幂集的性质(证明1、续)AB P(A)P(B)证明(续): () x, xA xP(A) xP(B) (P(A)P(B
17、) xB AB. #2024/8/1248离散数学 集合证明幂集的性质(证明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)2024/8/1249离散数学 集合证明幂集的性质(证明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). #2024/8/1250离散数学 集合证明幂集的性质(证明3)P(A)P(
18、B) = P(AB)证明: x, xP(A)P(B) xP(A) xP(B) xA xB x AB xP(AB) P(A)P(B) = P(AB). #2024/8/1251离散数学 集合证明幂集的性质(证明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). #AB2024/8/1252离散数学 集合证明集合运算的优先级分三级: 第一级最高, 依次降低第一级: 补, 幂P()
19、第二级: 广义并 , 广义交 第三级: 并, 交, 相对补-, 对称差同一级: 用括号表示先后顺序2024/8/1253离散数学 集合证明集合列的极限2024/8/1254离散数学 集合证明集合列的极限Infinite often( i.o.):Almost everywhere(a.e.)2024/8/1255离散数学 集合证明集合列的极限上极限:下极限:2024/8/1256离散数学 集合证明集合列的极限性质:2024/8/1257离散数学 集合证明集合论悖论罗素悖论(Russells paradox)：S = x | xx SS ?SS SSSS SS2024/8/1258离散数学 集合
20、证明集合论公理外延公理: 所含元素相同的两个集合是相等的空集存在公理: 空集合存在无序对公理: 对任意的a,b, a,b存在并集公理: 对任意的A A, A A存在存在幂集公理: 对任意的A, P(A)存在联集公理: 2024/8/1259离散数学 集合证明集合论公理(续)子集公理: xA | P(x) 存在正则公理: 若S,则x(xSy(ySxy)无穷公理: 无穷集存在替换公理: f(a) | aA 存在 ( f是定义域为A的函数) 2024/8/1260离散数学 集合证明集合论公理(续)选择公理(Zorn引理, 良序原理): A是元素互不相交的集合,则可以从A的每个元素中恰好选择一个元素, 构成一个集合2024/8/1261离散数学 集合证明总结 集合恒等式 集合恒等式的证明 集合论悖论2024/8/1262离散数学 集合证明作业(#2) p27, 习题一, 11, 13, 14, 20 今天1班交作业(#1)2024/8/1263离散数学 集合证明
