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

離散數(shù)學(xué)離散數(shù)學(xué) 集合證明集合證明集合恒等式(關(guān)于與)等冪律(idempotent laws)AA=AAA=A交換律(commutative laws)AB=BAAB=BA2024/5/22集合論與圖論第4講集合恒等式(關(guān)于與、續(xù))結(jié)合律(associative laws)(AB)C=A(BC)(AB)C=A(BC)分配律(distributive laws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)2024/5/23集合論與圖論第4講集合恒等式(關(guān)于與、續(xù))吸收律(absorption laws)A(AB)=AA(AB)=A2024/5/24集合論與圖論第4講集合恒等式(關(guān)于)雙重否定律(double complement law)A=A德摩根律(DeMorgans laws)(AB)=AB(AB)=AB2024/5/25集合論與圖論第4講集合恒等式(關(guān)于與E)零律(dominance laws)AE=EA=同一律(identity laws)A=AAE=A2024/5/26集合論與圖論第4講集合恒等式(關(guān)于,E)排中律(excluded middle)AA=E矛盾律(contradiction)AA=全補(bǔ)律=EE=2024/5/27集合論與圖論第4講集合恒等式(關(guān)于-)補(bǔ)交轉(zhuǎn)換律(difference as intersection)A-B=AB2024/5/28集合論與圖論第4講集合恒等式(推廣到集族)分配律德摩根律2024/5/29集合論與圖論第4講對(duì)偶(dual)原理對(duì)偶式(dual):一個(gè)集合關(guān)系式,如果只含有,E,=,那么,同時(shí)把與互換,把與E互換,把與互換,得到的式子稱為原式的對(duì)偶式.對(duì)偶原理:對(duì)偶式同真假.或者說,集合恒等式的對(duì)偶式還是恒等式.2024/5/210集合論與圖論第4講對(duì)偶原理(舉例)分配律A (B C)=(A B)(A C)A (B C)=(A B)(A C)排中律A A=E矛盾律A A=2024/5/211集合論與圖論第4講對(duì)偶原理(舉例、續(xù))零律A E=EA =同一律A =AA E=A2024/5/212集合論與圖論第4講對(duì)偶原理(舉例、續(xù))A B AA B A AE A2024/5/213集合論與圖論第4講集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結(jié)論2024/5/214集合論與圖論第4講邏輯演算法(格式)題目:A=B.證明:x,xA (?)xB A=B.#題目:AB.證明:x,xA (?)xB AB.#2024/5/215集合論與圖論第4講分配律(證明)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/5/216集合論與圖論第4講零律(證明)A=證明:x,xA xA x (定義)xA 0 (定義)0 (命題邏輯零律)A=2024/5/217集合論與圖論第4講排中律(證明)AA=E證明:x,xAA xA xA (定義)xA xA (定義)xA xA (定義)1 (命題邏輯排中律)AA=E2024/5/218集合論與圖論第4講集合演算法(格式)題目:A=B.證明:A =(?)=B A=B.#題目:AB.證明:A (?)B AB.#2024/5/219集合論與圖論第4講吸收律(證明)A(AB)=A證明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE (零律)=A (同一律)A(AB)=AAB2024/5/220集合論與圖論第4講吸收律(證明、續(xù))A(AB)=A證明:A(AB)=(AA)(AB)(分配律)=A(AB)(等冪律)=A (吸收律第一式)A(AB)=AAB2024/5/221集合論與圖論第4講集合演算法(格式,續(xù))題目:A=B.證明:()AB ()A B A=B.#說明:分=成與題目:AB.證明:AB(或AB)=(?)=A(或B)AB.#說明:化成=AB=AABAB=BAB 2024/5/222集合論與圖論第4講集合恒等式證明(舉例)基本集合恒等式對(duì)稱差()的性質(zhì)集族(AS)的性質(zhì)冪集(P()的性質(zhì)2024/5/223集合論與圖論第4講補(bǔ)交轉(zhuǎn)換律A-B=AB證明:x,xA-B xA xB xA xB x ABA-B=AB.#2024/5/224集合論與圖論第4講德摩根律的相對(duì)形式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)換律).#2024/5/225集合論與圖論第4講對(duì)稱差的性質(zhì)1.交換律:AB=BA2.結(jié)合律:A(BC)=(AB)C3.分配律:A(BC)=(AB)(AC)4.A=A,AE=A5.AA=,AA=E2024/5/226集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2)結(jié)合律:A(BC)=(AB)C證明思路：分解成 “基本單位”,例如:1.ABC 2.A BC 3.A B C 4.ABCABCABC12342024/5/227集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律:A(BC)=(AB)C證明:首先,AB=(A-B)(B-A)(定義)=(AB)(BA)(補(bǔ)交轉(zhuǎn)換律)=(AB)(AB)(交換律)(*)A BAB2024/5/228集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2、續(xù)2)其次,A(BC)=(A(BC)(A(BC)(*)=(A(BC)(BC)(A(BC)(BC)(*)=(A(BC)(BC)(A(BC)(BC)(德摩根律)2024/5/229集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2、續(xù)3)=(A(BC)(BC)(A(BC)(BC)=(A(BC)(BC)(A(BC)(BC)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配律)2024/5/230集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2、續(xù)4)同理,(AB)C =(AB)C)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(*)=(AB)(AB)C)(AB)(AB)C)(德摩根律)2024/5/231集合論與圖論第4講對(duì)稱差的性質(zhì)(證明2、續(xù)5)=(AB)(AB)C)(AB)(AB)C)=(AB)(AB)C)(AB)(AB)C)(德摩根律)=(ABC)(ABC)(ABC)(ABC)(分配律)A(BC)=(AB)C.#2024/5/232集合論與圖論第4講對(duì)稱差的性質(zhì)(討論)有些作者用表示對(duì)稱差:AB=AB 消去律:AB=AC B=C(習(xí)題一,23)A=BC B=AC C=AB對(duì)稱差與補(bǔ):(AB)=AB=AB AB=AB問題:ABC=ABC?2024/5/233集合論與圖論第4講對(duì)稱差的性質(zhì)(討論、續(xù))如何把對(duì)稱差推廣到n個(gè)集合:A1A2A3An=?x,xA1A2A3An x恰好屬于A1,A2,A3,An中的奇數(shù)個(gè)特征函數(shù)表達(dá):A1A2An(x)=A1(x)+A2(x)+An(x)(mod 2)=A1(x)A2(x)An(x)(mod 2),都表示模2加法,即相加除以2取余數(shù))2024/5/234集合論與圖論第4講特征函數(shù)與集合運(yùn)算: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/5/235集合論與圖論第4講對(duì)稱差的性質(zhì)(討論、續(xù))問題:ABC=ABC?答案:ABC=(ABC)=(ABC)=ABC ABCD=ABCD =ABCD=(ABCD)=A=(A)2024/5/236集合論與圖論第4講對(duì)稱差的性質(zhì)(證明3)分配律:A(BC)=(AB)(AC)證明 A(BC)=A(BC)(BC)=(ABC)(ABC)ABCA(BC)2024/5/237集合論與圖論第4講對(duì)稱差分配律(證明3、續(xù))(續(xù))(AB)(AC)=(AB)(AC)(AB)(AC)=(AB)(AC)(AB)(AC)=(ABC)(ABC)A(BC)=(AB)(AC).#2024/5/238集合論與圖論第4講對(duì)稱差分配律(討論)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?2024/5/239集合論與圖論第4講集族的性質(zhì)設(shè)A,B為集族集族,則1.AB A B2.AB A B 3.A AB B A4.AB B A5.A A A2024/5/240集合論與圖論第4講集族的性質(zhì)(證明1)AB A B證明:x,x A A(AA xA)(A定義)A(AB xA)(AB)x B (B定義)A B.#2024/5/241集合論與圖論第4講集族的性質(zhì)(證明2)AB A B 證明:x,xA AB xA (AB,合取)A(AB xA)(EG)x B A B.#2024/5/242集合論與圖論第4講集族的性質(zhì)(證明3)A AB B A說明:若約定=E,則A的條件可去掉.證明:x,x B y(yB xy)y(yA xy)(AB)x A B A.#2024/5/243集合論與圖論第4講集族的性質(zhì)(證明4)AB B A證明:x,x B y(yB xy)AB x A (UI)xA (AB)B A.#2024/5/244集合論與圖論第4講集族的性質(zhì)(證明5)A A A說明:A的條件不可去掉!證明:A y(yA),設(shè) AA.x,x A y(yA xy)AA xA xA (AA)AA xA y(yA xy)x A A A.#2024/5/245集合論與圖論第4講冪集的性質(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)2024/5/246集合論與圖論第4講冪集的性質(zhì)(證明1)AB P(A)P(B)證明:()x,xP(A)xA xB (AB)xP(B)P(A)P(B)2024/5/247集合論與圖論第4講冪集的性質(zhì)(證明1、續(xù))AB P(A)P(B)證明(續(xù)):()x,xA xP(A)xP(B)(P(A)P(B)xB AB.#2024/5/248集合論與圖論第4講冪集的性質(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)2024/5/249集合論與圖論第4講冪集的性質(zhì)(證明2、續(xù))P(A)P(B)P(AB)討論:給出反例,說明等號(hào)不成立: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 此時(shí),P(A)P(B)P(AB).#2024/5/250集合論與圖論第4講冪集的性質(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).#2024/5/251集合論與圖論第4講冪集的性質(zhì)(證明4)P(A-B)(P(A)-P(B)證明:x,分兩種情況,(1)x=,這時(shí) xP(A-B)并且 x(P(A)-P(B)(2)x,這時(shí) xP(A-B)x A-B xAxB xP(A)xP(B)xP(A)-P(B)P(A-B)(P(A)-P(B).#AB2024/5/252集合論與圖論第4講集合運(yùn)算的優(yōu)先級(jí)分三級(jí):第一級(jí)最高,依次降低第一級(jí):補(bǔ),冪P()第二級(jí):廣義并,廣義交 第三級(jí):并,交,相對(duì)補(bǔ)-,對(duì)稱差同一級(jí):用括號(hào)表示先后順序2024/5/253集合論與圖論第4講集合列的極限2024/5/254集合論與圖論第4講集合列的極限Infinite often(i.o.):Almost everywhere(a.e.)2024/5/255集合論與圖論第4講集合列的極限上極限:下極限:2024/5/256集合論與圖論第4講集合列的極限性質(zhì):2024/5/257集合論與圖論第4講集合論悖論羅素悖論(Russells paradox)：S=x|xx SS?SS SSSS SS2024/5/258集合論與圖論第4講集合論公理外延公理:所含元素相同的兩個(gè)集合是相等的空集存在公理:空集合存在無序?qū)?對(duì)任意的a,b,a,b存在并集公理:對(duì)任意的A A,A A存在存在冪集公理:對(duì)任意的A,P(A)存在聯(lián)集公理:2024/5/259集合論與圖論第4講集合論公理(續(xù))子集公理:xA|P(x)存在正則公理:若S,則x(xSy(ySxy)無窮公理:無窮集存在替換公理:f(a)|aA 存在 (f是定義域?yàn)锳的函數(shù))2024/5/260集合論與圖論第4講集合論公理(續(xù))選擇公理(Zorn引理,良序原理):A是元素互不相交的集合,則可以從A的每個(gè)元素中恰好選擇一個(gè)元素,構(gòu)成一個(gè)集合2024/5/261集合論與圖論第4講總結(jié) 集合恒等式 集合恒等式的證明 集合論悖論2024/5/262集合論與圖論第4講作業(yè)(#2)p27,習(xí)題一,11,13,14,20 今天1班交作業(yè)(#1)2024/5/263集合論與圖論第4講結(jié)束語結(jié)束語謝謝大家聆聽！謝謝大家聆聽！64