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

離散數(shù)學集合證明2023/6/21《集合論與圖論》第4講1第一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講2集合恒等式(關于與)等冪律(idempotentlaws)AA=AAA=A交換律(commutativelaws)AB=BAAB=BA第二頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講3集合恒等式(關于與、續(xù))結(jié)合律(associativelaws)(AB)C=A(BC)

(AB)C=A(BC)

分配律(distributivelaws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)第三頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講4集合恒等式(關于與、續(xù))吸收律(absorptionlaws)A(AB)=AA(AB)=A第四頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講5集合恒等式(關于~)雙重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(AB)=~A~B~(AB)=~A~B第五頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講6集合恒等式(關于與E)零律(dominancelaws)AE=EA=同一律(identitylaws)A=AAE=A第六頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講7集合恒等式(關于,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=全補律~=E~E=第七頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講8集合恒等式(關于-)補交轉(zhuǎn)換律(differenceasintersection)A-B=A~B第八頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講9集合恒等式(推廣到集族)分配律德●摩根律第九頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講10對偶(dual)原理對偶式(dual):一個集合關系式,如果只含有,

,~,,E,=,,

那么,同時把與互換,把與E互換,把與互換,得到的式子稱為原式的對偶式.對偶原理:對偶式同真假.或者說,集合恒等式的對偶式還是恒等式.第十頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講11對偶原理(舉例)分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律A

~A=E矛盾律A~A=第十一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講12對偶原理(舉例、續(xù))零律AE=EA

=同一律A

=AAE=A第十二頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講13對偶原理(舉例、續(xù))ABAAB

A

AE

A第十三頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講14集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結(jié)論第十四頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講15邏輯演算法(格式)題目:A=B.證明:x,

xA

…(????)

xB

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

xA

…(????)

xB

AB.#第十五頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第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)第十六頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講17零律(證明)A=證明:x,xA

xAx(定義)xA0

(定義)0(命題邏輯零律)A=第十七頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講18排中律(證明)A~A=E證明:x,xA~A

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

1(命題邏輯排中律)A~A=E第十八頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講19集合演算法(格式)題目:A=B.證明:A

=…(????)

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

…(????)

BAB.#第十九頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講20吸收律(證明)A(AB)=A證明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=AAB第二十頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講21吸收律(證明、續(xù))A(AB)=A證明:A(AB)=(AA)(AB)(分配律)=A(AB)(等冪律)=A(吸收律第一式)A(AB)=AAB第二十一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講22集合演算法(格式,續(xù))題目:A=B.證明:()…

AB()…

AB

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

=…(????)

=

A(或B)

AB.#說明:化成=AB=AABAB=BAB第二十二頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講23集合恒等式證明(舉例)基本集合恒等式對稱差()的性質(zhì)集族({A}S)的性質(zhì)冪集(P())的性質(zhì)第二十三頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講24補交轉(zhuǎn)換律A-B=A~B證明:x,xA-BxA

xBxAx~B

xA~BA-B=A~B.#第二十四頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講25德●摩根律的相對形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)證明:A-(BC)=A~(BC)(補交轉(zhuǎn)換律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等冪律)=(A~B)(A~C)(交換律,結(jié)合律)=(A-B)(B-A)(補交轉(zhuǎn)換律).#第二十五頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講26對稱差的性質(zhì)交換律:AB=BA結(jié)合律:A(BC)=(AB)C分配律:A(BC)=(AB)(AC)A=A,AE=~AAA=,A~A=E第二十六頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講27對稱差的性質(zhì)(證明2)結(jié)合律:A(BC)=(AB)C證明思路：分解成“基本單位”,例如:1.A~B~C2.AB~C3.ABC4.~A~B~CABCABC1234第二十七頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講28對稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律:A(BC)=(AB)C證明:

首先,AB=(A-B)(B-A)(定義)=(A~B)(B~A)(補交轉(zhuǎn)換律)=(A~B)(~AB)(交換律)(*)ABAB第二十八頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講29對稱差的性質(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)))(德?摩根律)第二十九頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講30對稱差的性質(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)(分配律…)第三十頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講31對稱差的性質(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)(德?摩根律)第三十一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講32對稱差的性質(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.#第三十二頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講33對稱差的性質(zhì)(討論)有些作者用△表示對稱差:

AB=A△B消去律:AB=ACB=C(習題一,23)A=BCB=ACC=AB對稱差與補:~(AB)=~AB=A~BAB=~A~B問題:ABC=~A~B~C?第三十三頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講34對稱差的性質(zhì)(討論、續(xù))如何把對稱差推廣到n個集合:

A1A2A3…An=?x,xA1A2A3…Anx恰好屬于A1,A2,A3,…,An中的奇數(shù)個特征函數(shù)表達:A1A2…An(x)=A1(x)+A2(x)+…+An(x)(mod2)=A1(x)A2(x)…An(x)((mod2),,都表示模2加法,即相加除以2取余數(shù))第三十四頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講35特征函數(shù)與集合運算: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第三十五頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講36對稱差的性質(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)第三十六頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講37對稱差的性質(zhì)(證明3)分配律:A(BC)=(AB)(AC)證明

A(BC)=A((B~C)(~BC))=(AB~C)(A~BC)ABCA(BC)第三十七頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講38對稱差分配律(證明3、續(xù))(續(xù))(AB)(AC)=((AB)~(AC))(~(AB)(AC))=((AB)(~A~C))((~A~B)(AC))=(AB~C)(A~BC)A(BC)=(AB)(AC).#第三十八頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講39對稱差分配律(討論)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?第三十九頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講40集族的性質(zhì)設A,B為集族,則1.AB

∪A∪B2.AB

A∪B

3.A

AB

∩B∩A4.AB

∩BA5.A

∩A∪A第四十頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講41集族的性質(zhì)(證明1)AB

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

A(AA

xA)(∪A定義)

A(AB

xA)(AB)x∪B

(∪B定義)∪A∪B.#第四十一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講42集族的性質(zhì)(證明2)AB

A∪B

證明:x,xA

AB

xA(AB,合取)A(AB

xA)(EG)x∪B

A∪B.#第四十二頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講43集族的性質(zhì)(證明3)A

AB

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

y(yB

xy)y(yA

xy)(AB)x∩A

∩B

∩A

.#第四十三頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講44集族的性質(zhì)(證明4)AB

∩BA證明:x,x∩B

y(yB

xy)AB

xA(UI)

xA

(AB)∩B

A

.#第四十四頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講45集族的性質(zhì)(證明5)A

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

A

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

xy)AA

xAxA(AA)AAxAy(yA

xy)

x∪A∩A

∪A

.#第四十五頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第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)){}第四十六頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講47冪集的性質(zhì)(證明1)ABP(A)P(B)證明:()x,xP(A)xAxB(AB)xP(B)P(A)P(B)第四十七頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講48冪集的性質(zhì)(證明1、續(xù))ABP(A)P(B)證明(續(xù)):()x,xA{x}P(A){x}P(B)(P(A)P(B))

xBAB.#第四十八頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第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)第四十九頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講50冪集的性質(zhì)(證明2、續(xù))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).#第五十頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第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).#第五十一頁，共六十三頁，編輯于2023年，星期一2023/6/21《集合論與圖論》第4講52冪集的性質(zhì)(證明4)P(A-B)

(P(A)-P(B)){}證明:x,分兩種情況,(1)x=,這時

xP(A-B)并且x(P(A)-P(B)){}(2)x,這時

xP(A-B)xA-B

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