北大集合論與圖論4

會(huì)計(jì)學(xué)1北大集合論與圖論42023/1/18《集合論與圖論》第4講2集合恒等式(關(guān)于與)等冪律(idempotentlaws)AA=AAA=A交換律(commutativelaws)AB=BAAB=BA第1頁/共63頁2023/1/18《集合論與圖論》第4講3集合恒等式(關(guān)于與、續(xù))結(jié)合律(associativelaws)(AB)C=A(BC)

(AB)C=A(BC)

分配律(distributivelaws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)第2頁/共63頁2023/1/18《集合論與圖論》第4講4集合恒等式(關(guān)于與、續(xù))吸收律(absorptionlaws)A(AB)=AA(AB)=A第3頁/共63頁2023/1/18《集合論與圖論》第4講5集合恒等式(關(guān)于~)雙重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(AB)=~A~B~(AB)=~A~B第4頁/共63頁2023/1/18《集合論與圖論》第4講6集合恒等式(關(guān)于與E)零律(dominancelaws)AE=EA=同一律(identitylaws)A=AAE=A第5頁/共63頁2023/1/18《集合論與圖論》第4講7集合恒等式(關(guān)于,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=全補(bǔ)律~=E~E=第6頁/共63頁2023/1/18《集合論與圖論》第4講8集合恒等式(關(guān)于-)補(bǔ)交轉(zhuǎn)換律(differenceasintersection)A-B=A~B第7頁/共63頁2023/1/18《集合論與圖論》第4講9集合恒等式(推廣到集族)分配律德●摩根律第8頁/共63頁2023/1/18《集合論與圖論》第4講10對(duì)偶(dual)原理對(duì)偶式(dual):一個(gè)集合關(guān)系式,如果只含有,

,~,,E,=,,

那么,同時(shí)把與互換,把與E互換,把與互換,得到的式子稱為原式的對(duì)偶式.對(duì)偶原理:對(duì)偶式同真假.或者說,集合恒等式的對(duì)偶式還是恒等式.第9頁/共63頁2023/1/18《集合論與圖論》第4講11對(duì)偶原理(舉例)分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律A

~A=E矛盾律A~A=第10頁/共63頁2023/1/18《集合論與圖論》第4講12對(duì)偶原理(舉例、續(xù))零律AE=EA

=同一律A

=AAE=A第11頁/共63頁2023/1/18《集合論與圖論》第4講13對(duì)偶原理(舉例、續(xù))ABAAB

A

AE

A第12頁/共63頁2023/1/18《集合論與圖論》第4講14集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結(jié)論第13頁/共63頁2023/1/18《集合論與圖論》第4講15邏輯演算法(格式)題目:A=B.證明:x,

xA

…(????)

xB

A=B.#題目:AB.證明:x,

xA

…(????)

xB

AB.#第14頁/共63頁2023/1/18《集合論與圖論》第4講16分配律(證明)A(BC)=(AB)(AC)證明:x,

xA(BC)

xAx(BC)(定義)xA(xB

xC)(定義)(xAxB)(xAxC)(命題邏輯分配律)(xAB)(xAC)(定義)x(AB)(AC)(定義)

A(BC)=(AB)(AC)第15頁/共63頁2023/1/18《集合論與圖論》第4講17零律(證明)A=證明:x,xA

xAx(定義)xA0

(定義)0(命題邏輯零律)A=第16頁/共63頁2023/1/18《集合論與圖論》第4講18排中律(證明)A~A=E證明:x,xA~A

xAx~A(定義)xAxA(~定義)xAxA(定義)

1(命題邏輯排中律)A~A=E第17頁/共63頁2023/1/18《集合論與圖論》第4講19集合演算法(格式)題目:A=B.證明:A

=…(????)

=BA=B.#題目:AB.證明:A

…(????)

BAB.#第18頁/共63頁2023/1/18《集合論與圖論》第4講20吸收律(證明)A(AB)=A證明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=AAB第19頁/共63頁2023/1/18《集合論與圖論》第4講21吸收律(證明、續(xù))A(AB)=A證明:A(AB)=(AA)(AB)(分配律)=A(AB)(等冪律)=A(吸收律第一式)A(AB)=AAB第20頁/共63頁2023/1/18《集合論與圖論》第4講22集合演算法(格式,續(xù))題目:A=B.證明:()…

AB()…

AB

A=B.#說明:分=成與題目:AB.證明:AB(或AB)

=…(????)

=

A(或B)

AB.#說明:化成=AB=AABAB=BAB第21頁/共63頁2023/1/18《集合論與圖論》第4講23集合恒等式證明(舉例)基本集合恒等式對(duì)稱差()的性質(zhì)集族({A}S)的性質(zhì)冪集(P())的性質(zhì)第22頁/共63頁2023/1/18《集合論與圖論》第4講24補(bǔ)交轉(zhuǎn)換律A-B=A~B證明:x,xA-BxA

xBxAx~B

xA~BA-B=A~B.#第23頁/共63頁2023/1/18《集合論與圖論》第4講25德摩根律的相對(duì)形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)證明:A-(BC)=A~(BC)(補(bǔ)交轉(zhuǎn)換律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等冪律)=(A~B)(A~C)(交換律,結(jié)合律)=(A-B)(A-C)(補(bǔ)交轉(zhuǎn)換律).#第24頁/共63頁2023/1/18《集合論與圖論》第4講26對(duì)稱差的性質(zhì)交換律:AB=BA結(jié)合律:A(BC)=(AB)C分配律:A(BC)=(AB)(AC)A=A,AE=~AAA=,A~A=E第25頁/共63頁2023/1/18《集合論與圖論》第4講27對(duì)稱差的性質(zhì)(證明2)結(jié)合律:A(BC)=(AB)C證明思路：

分解成“基本單位”,例如:1.A~B~C2.AB~C3.ABC4.~A~B~CABCABC1234第26頁/共63頁2023/1/18《集合論與圖論》第4講28對(duì)稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律:A(BC)=(AB)C證明:

首先,AB=(A-B)(B-A)(定義)=(A~B)(B~A)(補(bǔ)交轉(zhuǎn)換律)=(A~B)(~AB)(交換律)(*)ABAB第27頁/共63頁2023/1/18《集合論與圖論》第4講29對(duì)稱差的性質(zhì)(證明2、續(xù)2)其次,A(BC)=(A~(BC))(~A(BC))(*)=(A~((B~C)(~BC)))

(~A((B~C)(~BC)))(*)=(A(~(B~C)~(~BC)))

(~A((B~C)(~BC)))(德?摩根律)第28頁/共63頁2023/1/18《集合論與圖論》第4講30對(duì)稱差的性質(zhì)(證明2、續(xù)3)=(A(~(B~C)~(~BC)))

(~A((B~C)(~BC)))=(A(~BC)(B~C)))

(~A((B~C)(~BC)))(德?摩根律)=(ABC)(A~B~C)

(~AB~C)(~A~BC)(分配律…)第29頁/共63頁2023/1/18《集合論與圖論》第4講31對(duì)稱差的性質(zhì)(證明2、續(xù)4)

同理,(AB)C=(AB)~C)(~(AB)C)(*)=(((A~B)(~AB))~C)(~((A~B)(~AB))C)(*)=(((A~B)(~AB))~C)((~(A~B)~(~AB))C)(德?摩根律)第30頁/共63頁2023/1/18《集合論與圖論》第4講32對(duì)稱差的性質(zhì)(證明2、續(xù)5)=(((A~B)(~AB))~C)((~(A~B)~(~AB))C)=(((A~B)(~AB))~C)((~AB)(A~B))C)(德?摩根律)=(A~B~C)(~AB~C)

(~A~BC)(ABC)(分配律…)A(BC)=(AB)C.#第31頁/共63頁2023/1/18《集合論與圖論》第4講33對(duì)稱差的性質(zhì)(討論)有些作者用△表示對(duì)稱差:

AB=A△B消去律:AB=ACB=C(習(xí)題一,23)A=BCB=ACC=AB對(duì)稱差與補(bǔ):~(AB)=~AB=A~BAB=~A~B問題:ABC=~A~B~C?第32頁/共63頁2023/1/18《集合論與圖論》第4講34對(duì)稱差的性質(zhì)(討論、續(xù))如何把對(duì)稱差推廣到n個(gè)集合:

A1A2A3…An=?x,xA1A2A3…Anx恰好屬于A1,A2,A3,…,An中的奇數(shù)個(gè)特征函數(shù)表達(dá):A1A2…An(x)=A1(x)+A2(x)+…+An(x)(mod2)=A1(x)A2(x)…An(x)((mod2),,都表示模2加法,即相加除以2取余數(shù))第33頁/共63頁2023/1/18《集合論與圖論》第4講35特征函數(shù)與集合運(yùn)算:AB(x)=A(x)B(x)~A(x)=1-A(x)A-B(x)=A~B(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)(mod2)=A(x)B(x)AB第34頁/共63頁2023/1/18《集合論與圖論》第4講36對(duì)稱差的性質(zhì)(討論、續(xù))問題:ABC=~A~B~C?答案:ABC=~(~A~B~C)=~(AB~C)=A~B~CABCD=~A~B~C~D=A~BC~D=~(~A~BC~D)=…A=~(~A)第35頁/共63頁2023/1/18《集合論與圖論》第4講37對(duì)稱差的性質(zhì)(證明3)分配律:A(BC)=(AB)(AC)證明

A(BC)=A((B~C)(~BC))=(AB~C)(A~BC)ABCA(BC)第36頁/共63頁2023/1/18《集合論與圖論》第4講38對(duì)稱差分配律(證明3、續(xù))(續(xù))(AB)(AC)=((AB)~(AC))(~(AB)(AC))=((AB)(~A~C))((~A~B)(AC))=(AB~C)(A~BC)A(BC)=(AB)(AC).#第37頁/共63頁2023/1/18《集合論與圖論》第4講39對(duì)稱差分配律(討論)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?第38頁/共63頁2023/1/18《集合論與圖論》第4講40集族的性質(zhì)設(shè)A,B為集族,則1.AB

∪A∪B2.AB

A∪B

3.A

AB

∩B∩A4.AB

∩BA5.A

∩A∪A第39頁/共63頁2023/1/18《集合論與圖論》第4講41集族的性質(zhì)(證明1)AB

∪A∪B證明:x,x∪A

A(AA

xA)(∪A定義)

A(AB

xA)(AB)x∪B

(∪B定義)∪A∪B.#第40頁/共63頁2023/1/18《集合論與圖論》第4講42集族的性質(zhì)(證明2)AB

A∪B

證明:x,xA

AB

xA(AB,合取)A(AB

xA)(EG)x∪B

A∪B.#第41頁/共63頁2023/1/18《集合論與圖論》第4講43集族的性質(zhì)(證明3)A

AB

∩B∩A說明:若約定∩=E,則A的條件可去掉.證明:x,x∩B

y(yB

xy)y(yA

xy)(AB)x∩A

∩B

∩A

.#第42頁/共63頁2023/1/18《集合論與圖論》第4講44集族的性質(zhì)(證明4)AB

∩BA證明:x,x∩B

y(yB

xy)AB

xA(UI)

xA

(AB)∩B

A

.#第43頁/共63頁2023/1/18《集合論與圖論》第4講45集族的性質(zhì)(證明5)A

∩A∪A說明:A的條件不可去掉!證明:

A

y(yA),設(shè)AA.x,x∩Ay(yA

xy)AA

xAxA(AA)AAxAy(yA

xy)

x∪A∩A

∪A

.#第44頁/共63頁2023/1/18《集合論與圖論》第4講46冪集的性質(zhì)ABP(A)P(B)P(A)P(B)

P(AB)P(A)P(B)

=

P(AB)P(A-B)

(P(A)-P(B)){}第45頁/共63頁2023/1/18《集合論與圖論》第4講47冪集的性質(zhì)(證明1)ABP(A)P(B)證明:()x,xP(A)xAxB(AB)xP(B)P(A)P(B)第46頁/共63頁2023/1/18《集合論與圖論》第4講48冪集的性質(zhì)(證明1、續(xù))ABP(A)P(B)證明(續(xù)):()x,xA{x}P(A){x}P(B)(P(A)P(B))

xBAB.#第47頁/共63頁2023/1/18《集合論與圖論》第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)第48頁/共63頁2023/1/18《集合論與圖論》第4講50冪集的性質(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).#第49頁/共63頁2023/1/18《集合論與圖論》第4講51冪集的性質(zhì)(證明3)P(A)P(B)=P(AB)證明:x,xP(A)P(B)xP(A)

xP(B)xAxB

xABxP(AB)P(A)P(B)=P(AB).#第50頁/共63頁2023/1/18《集合論與圖論》第4講52冪集的性質(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)xA-B

xAxBxP(A)xP(B)xP(A)-P(B