離散數(shù)學(xué)集合證明

《離散數(shù)學(xué)集合證明》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)集合證明（63頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2021-6-6集合論與圖論第4講1 第4講 集合恒等式內(nèi)容提要 1. 集合恒等式與對偶原理 2. 集合恒等式的證明 3. 集合列的極限 4. 集合論悖論與集合論公理 2021-6-6集合論與圖論第4講2 集合恒等式(關(guān)于與)等冪律(idempotent laws)AA=AAA=A交換律(commutative laws)AB=BAAB=BA 2021-6-6集合論與圖論第4講3 集合恒等式(關(guān)于與、續(xù))結(jié)合律(associative laws)(AB)C=A(BC) (AB)C=A(BC) 分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)

2、2021-6-6集合論與圖論第4講4 集合恒等式(關(guān)于與 、續(xù))吸收律(absorption laws)A(AB)=AA(AB)=A 2021-6-6集合論與圖論第4講5 集合恒等式(關(guān)于)雙重否定律(double complement law)A=A德摩根律(DeMorgans laws)(AB)=AB(AB)=AB 2021-6-6集合論與圖論第4講6 集合恒等式(關(guān)于與E)零律(dominance laws)AE=EA=同一律(identity laws)A=AAE=A 2021-6-6集合論與圖論第4講7 集合恒等式(關(guān)于,E)排中律(excluded middle)AA = E矛盾律

3、(contradiction)AA = 全補(bǔ)律 = EE = 2021-6-6集合論與圖論第4講8 集合恒等式(關(guān)于-)補(bǔ)交轉(zhuǎn)換律(difference as intersection)A-B=AB 2021-6-6集合論與圖論第4講9 集合恒等式(推廣到集族)分配律德摩根律)()( ABAB SS )()( ABAB SS )()( ABAB SS )()( ABAB SS )()( AA SS )()( AA SS 2021-6-6集合論與圖論第4講10 對偶(dual)原理對偶式(dual): 一個集合關(guān)系式, 如果只含有, , E,=, , 那么, 同時把與互換, 把與E互換, 把與互

4、換, 得到的式子稱為原式的對偶式. 對偶原理: 對偶式同真假. 或者說, 集合恒等式的對偶式還是恒等式. 2021-6-6集合論與圖論第4講11 對偶原理(舉例)分配律A (B C) = (A B ) (A C )A (B C) = (A B ) (A C )排中律A A=E矛盾律A A= 2021-6-6集合論與圖論第4講12 對偶原理(舉例、續(xù))零律A E =EA = 同一律A =AA E=A 2021-6-6集合論與圖論第4講13 對偶原理(舉例、續(xù)) A B AA B A AE A 2021-6-6集合論與圖論第4講14 集合恒等式證明(方法)邏輯演算法: 利用邏輯等值式和推理規(guī)則集合

5、演算法: 利用集合恒等式和已知結(jié)論 2021-6-6集合論與圖論第4講15 邏輯演算法(格式)題目: A=B. 證明: x, xA (?) xB A=B. #題目: AB. 證明: x, xA (?) xB AB. # 2021-6-6集合論與圖論第4講16 分配律(證明)A(BC)=(AB)(AC)證明: x, xA(BC) xA x(BC) (定義) xA (xB xC) (定義) (xAxB)(xAxC) (命題邏輯分配律) (xAB)(xAC) (定義) x(AB)(AC) (定義) A(BC)=(AB)(AC) 2021-6-6集合論與圖論第4講17 零律(證明)A = 證明: x,

6、 xA xA x (定義) xA 0 (定義) 0 (命題邏輯零律) A = 2021-6-6集合論與圖論第4講18 排中律(證明)AA = E證明: x, xAA xA xA (定義) xA xA (定義) xA xA (定義) 1 (命題邏輯排中律) AA = E 2021-6-6集合論與圖論第4講19 集合演算法(格式)題目: A=B. 證明: A =(?) =B A=B. #題目: AB. 證明: A (?) B AB. # 2021-6-6集合論與圖論第4講20 吸收律(證明)A(AB)=A證明: A(AB) = (AE)(AB) (同一律) = A(EB) (分配律) = AE (

7、零律) = A (同一律) A(AB)=A A B 2021-6-6集合論與圖論第4講21 吸收律(證明、續(xù))A(AB) = A證明: A(AB) = (AA)(AB) (分配律) = A(AB) (等冪律) = A (吸收律第一式) A(AB) = A A B 2021-6-6集合論與圖論第4講22 集合演算法(格式,續(xù))題目: A=B. 證明: () AB () A B A = B. #說明: 分=成與題目: AB. 證明: AB (或AB) =(?) = A (或B) AB. #說明: 化成=AB=AABAB=BAB 2021-6-6集合論與圖論第4講23 集合恒等式證明(舉例)基本集合

8、恒等式對稱差()的性質(zhì)集族(AS)的性質(zhì)冪集(P( )的性質(zhì) 2021-6-6集合論與圖論第4講24 補(bǔ)交轉(zhuǎn)換律A-B = AB證明: x, xA-B xA xB xA xB x ABA-B = AB. # 2021-6-6集合論與圖論第4講25 德摩根律的相對形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)證明: A-(BC) = A(BC) (補(bǔ)交轉(zhuǎn)換律) = A(BC) (德摩根律) = (AA)(BC) (等冪律) = (AB)(AC) (交換律,結(jié)合律)= (A-B)(B-A) (補(bǔ)交轉(zhuǎn)換律). # 2021-6-6集合論與圖論第4講26 對稱差的性質(zhì)1.交換

9、律: AB=BA2.結(jié)合律: A(BC)=(AB)C3.分配律: A(BC)=(AB)(AC)4. A=A, AE=A5. AA=, AA=E 2021-6-6集合論與圖論第4講27 對稱差的性質(zhì)(證明2)結(jié)合律: A(BC)=(AB)C證明思路： 分解成 “基本單位”, 例如: 1. ABC 2. A BC 3. A B C 4. ABC AB CABC12 34 2021-6-6集合論與圖論第4講28 對稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律: A(BC)=(AB)C證明: 首先, AB = (A-B)(B-A) (定義) = (AB)(BA) (補(bǔ)交轉(zhuǎn)換律) = (AB)(AB) (交換律)

10、(*)ABA B 2021-6-6集合論與圖論第4講29 對稱差的性質(zhì)(證明2、續(xù)2) 其次, A(BC) = (A(BC)(A(BC) (*) = (A(BC)(BC) (A(BC)(BC) (*) = (A(BC)(BC) (A(BC)(BC) (德摩根律) 2021-6-6集合論與圖論第4講30 對稱差的性質(zhì)(證明2、續(xù)3) = (A(BC)(BC) (A(BC)(BC) = (A(BC)(BC) (A(BC)(BC) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) 2021-6-6集合論與圖論第4講31 對稱差的性質(zhì)(證明2、續(xù)4) 同理, (AB)C = (

11、AB)C)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (*) = (AB)(AB)C) (AB)(AB)C) (德摩根律) 2021-6-6集合論與圖論第4講32 對稱差的性質(zhì)(證明2、續(xù)5) = (AB)(AB)C) (AB)(AB)C) = (AB)(AB)C) (AB)(AB)C) (德摩根律) = (ABC)(ABC) (ABC)(ABC) (分配律) A(BC)=(AB)C. # 2021-6-6集合論與圖論第4講33 對稱差的性質(zhì)(討論)有些作者用表示對稱差: AB=AB 消去律: AB=AC B=C (習(xí)題一,23) A=BC B=AC C=AB對稱差與

12、補(bǔ): (AB) = AB = AB AB = AB問題: ABC=ABC ? 2021-6-6集合論與圖論第4講34 對稱差的性質(zhì)(討論、續(xù))如何把對稱差推廣到n個集合: A1A2A3An = ? x, xA1A2A3An x恰好屬于A1,A2,A3,An中的奇數(shù)個特征函數(shù)表達(dá): A1A2An(x) = A 1(x)+A2(x)+An(x) (mod 2) = A1(x)A2(x)An(x) (mod 2),都表示模2加法,即相加除以2取余數(shù)) 2021-6-6集合論與圖論第4講35 特征函數(shù)與集合運(yùn)算: AB(x) = A(x)B(x)A(x) = 1-A(x)A-B(x) = AB(x)=

13、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 2021-6-6集合論與圖論第4講36 對稱差的性質(zhì)(討論、續(xù))問題: ABC = ABC ? 答案: ABC = (ABC) = (ABC) = ABC ABCD = ABCD = ABCD = (ABCD) =A = (A) 2021-6-6集合論與圖論第4講37 對稱差的性質(zhì)(證明3)分配律: A(BC)=(AB)(AC)證明 A(BC) = A(BC)(BC) = (ABC) (ABC)AB CA(BC) 2

14、021-6-6集合論與圖論第4講38 對稱差分配律(證明3、續(xù))(續(xù)) (AB)(AC) = (AB)(AC)(AB)(AC) =(AB)(AC)(AB)(AC) =(ABC)(ABC) A(BC)=(AB)(AC). # 2021-6-6集合論與圖論第4講39 對稱差分配律(討論)A(BC)=(AB)(AC) A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ?A(BC)=(AB)(AC) ? 2021-6-6集合論與圖論第4講40 集族的性質(zhì)設(shè)A,B為集族, 則1. AB A B2. AB A B 3. A AB B A4. AB B A5. A A A 2021-6-6集合論

15、與圖論第4講41 集族的性質(zhì)(證明1) AB A B證明: x, x A A(AA xA) ( A定義) A(AB xA) (AB) x B ( B定義) A B. # 2021-6-6集合論與圖論第4講42 集族的性質(zhì)(證明2) AB A B 證明: x, xA AB xA (AB, 合取) A(AB xA) (EG) x B A B. # 2021-6-6集合論與圖論第4講43 集族的性質(zhì)(證明3) A AB B A說明: 若約定=E, 則A的條件可去掉.證明: x, xB y( yB xy ) y( yA xy ) (AB) xA B A . # 2021-6-6集合論與圖論第4講44

16、集族的性質(zhì)(證明4) AB B A證明: x, xB y( yB xy ) AB x A (UI) xA (AB) B A . # 2021-6-6集合論與圖論第4講45 集族的性質(zhì)(證明5) A A A說明: A的條件不可去掉!證明: A y(yA), 設(shè) AA. x, xA y( yA xy ) AA xA xA (AA) AA xA y( yA xy) x A A A . # 2021-6-6集合論與圖論第4講46 冪集的性質(zhì)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) 2021-6-6集合論

17、與圖論第4講47 冪集的性質(zhì)(證明1)AB P(A)P(B)證明: () x, xP(A) xA xB (AB) xP(B) P(A)P(B) 2021-6-6集合論與圖論第4講48 冪集的性質(zhì)(證明1、續(xù))AB P(A)P(B)證明(續(xù)): () x, xA xP(A) xP(B) (P(A)P(B) xB AB. # 2021-6-6集合論與圖論第4講49 冪集的性質(zhì)(證明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) 2021-6-6集合論與圖論第4講50 冪集的性質(zhì)(證明2、續(xù))P(A

18、)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). # 2021-6-6集合論與圖論第4講51 冪集的性質(zhì)(證明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). # 2021-6-6集合論與圖論第4講52 冪集的性質(zhì)(證明4)P(A-B) (P(A)-P(B)證明: x, 分兩種情況, (1) x=,

19、這時 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). #A B 2021-6-6集合論與圖論第4講53 集合運(yùn)算的優(yōu)先級分三級: 第一級最高, 依次降低第一級: 補(bǔ), 冪P()第二級: 廣義并 , 廣義交第三級: 并, 交, 相對補(bǔ)-, 對稱差同一級: 用括號表示先后順序 2021-6-6集合論與圖論第4講54 集合列的極限 2021-6-6集合論與圖論第4講55 集合列的極限Infinite often( i.o.):Almost everywhere(a

20、.e.) 2021-6-6集合論與圖論第4講56 集合列的極限上極限:下極限: .|lim oiAxxA kkk .|lim eaAxxA kkk 2021-6-6集合論與圖論第4講57 集合列的極限性質(zhì): 1lim n nk kkk AA 1lim n nk kkk AA 2021-6-6集合論與圖論第4講58 集合論悖論羅素悖論(Russells paradox)：S = x | xx SS ?SS SSSS SS 2021-6-6集合論與圖論第4講59 集合論公理外延公理: 所含元素相同的兩個集合是相等的空集存在公理: 空集合存在無序?qū)? 對任意的a,b, a,b存在并集公理: 對任

21、意的A, A存在冪集公理: 對任意的A, P(A)存在聯(lián)集公理: 2021-6-6集合論與圖論第4講60 集合論公理(續(xù))子集公理: xA | P(x) 存在正則公理: 若S,則x(xSy(ySxy)無窮公理: 無窮集存在替換公理: f(a) | aA 存在 ( f是定義域為A的函數(shù)) 2021-6-6集合論與圖論第4講61 集合論公理(續(xù))選擇公理(Zorn引理, 良序原理): A是元素互不相交的集合,則可以從A的每個元素中恰好選擇一個元素, 構(gòu)成一個集合 2021-6-6集合論與圖論第4講62 總結(jié) 集合恒等式 集合恒等式的證明 集合論悖論 2021-6-6集合論與圖論第4講63 作業(yè)(#2) p27, 習(xí)題一, 11, 13, 14, 20 今天1班交作業(yè)(#1)