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

第4講集合恒等式內(nèi)容提要1.集合恒等式與對偶原理2.集合恒等式的證明3.集合列的極限4.集合論悖論與集合論公理2023/7/311離散數(shù)學(xué)集合證明集合恒等式(關(guān)于與)等冪律(idempotentlaws)AA=AAA=A交換律(commutativelaws)AB=BAAB=BA2023/7/312離散數(shù)學(xué)集合證明集合恒等式(關(guān)于與、續(xù))結(jié)合律(associativelaws)(AB)C=A(BC)

(AB)C=A(BC)

分配律(distributivelaws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)2023/7/313離散數(shù)學(xué)集合證明集合恒等式(關(guān)于與、續(xù))吸收律(absorptionlaws)A(AB)=AA(AB)=A2023/7/314離散數(shù)學(xué)集合證明集合恒等式(關(guān)于~)雙重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(AB)=~A~B~(AB)=~A~B2023/7/315離散數(shù)學(xué)集合證明集合恒等式(關(guān)于與E)零律(dominancelaws)AE=EA=同一律(identitylaws)A=AAE=A2023/7/316離散數(shù)學(xué)集合證明集合恒等式(關(guān)于,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=全補(bǔ)律~=E~E=2023/7/317離散數(shù)學(xué)集合證明集合恒等式(關(guān)于-)補(bǔ)交轉(zhuǎn)換律(differenceasintersection)A-B=A~B2023/7/318離散數(shù)學(xué)集合證明集合恒等式(推廣到集族)分配律德●摩根律2023/7/319離散數(shù)學(xué)集合證明對偶(dual)原理對偶式(dual):一個集合關(guān)系式,如果只含有,

,~,,E,=,,

那么,同時把與互換,把與E互換,把與互換,得到的式子稱為原式的對偶式.對偶原理:對偶式同真假.或者說,集合恒等式的對偶式還是恒等式.2023/7/3110離散數(shù)學(xué)集合證明對偶原理(舉例)分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律A

~A=E矛盾律A~A=2023/7/3111離散數(shù)學(xué)集合證明對偶原理(舉例、續(xù))零律AE=EA

=同一律A

=AAE=A2023/7/3112離散數(shù)學(xué)集合證明對偶原理(舉例、續(xù))ABAAB

A

AE

A2023/7/3113離散數(shù)學(xué)集合證明集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結(jié)論2023/7/3114離散數(shù)學(xué)集合證明邏輯演算法(格式)題目:A=B.證明:x,

xA

…(????)

xB

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

xA

…(????)

xB

AB.#2023/7/3115離散數(shù)學(xué)集合證明分配律(證明)A(BC)=(AB)(AC)證明:x,

xA(BC)

xAx(BC)(定義)xA(xB

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

A(BC)=(AB)(AC)2023/7/3116離散數(shù)學(xué)集合證明零律(證明)A=證明:x,xA

xAx(定義)xA0

(定義)0(命題邏輯零律)A=2023/7/3117離散數(shù)學(xué)集合證明排中律(證明)A~A=E證明:x,xA~A

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

1(命題邏輯排中律)A~A=E2023/7/3118離散數(shù)學(xué)集合證明集合演算法(格式)題目:A=B.證明:A

=…(????)

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

…(????)

BAB.#2023/7/3119離散數(shù)學(xué)集合證明吸收律(證明)A(AB)=A證明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=AAB2023/7/3120離散數(shù)學(xué)集合證明吸收律(證明、續(xù))A(AB)=A證明:A(AB)=(AA)(AB)(分配律)=A(AB)(等冪律)=A(吸收律第一式)A(AB)=AAB2023/7/3121離散數(shù)學(xué)集合證明集合演算法(格式,續(xù))題目:A=B.證明:()…

AB()…

AB

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

=…(????)

=

A(或B)

AB.#說明:化成=AB=AABAB=BAB2023/7/3122離散數(shù)學(xué)集合證明集合恒等式證明(舉例)基本集合恒等式對稱差()的性質(zhì)集族({A}S)的性質(zhì)冪集(P())的性質(zhì)2023/7/3123離散數(shù)學(xué)集合證明補(bǔ)交轉(zhuǎn)換律A-B=A~B證明:x,xA-BxA

xBxAx~B

xA~BA-B=A~B.#2023/7/3124離散數(shù)學(xué)集合證明德●摩根律的相對形式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)(B-A)(補(bǔ)交轉(zhuǎn)換律).#2023/7/3125離散數(shù)學(xué)集合證明對稱差的性質(zhì)交換律:AB=BA結(jié)合律:A(BC)=(AB)C分配律:A(BC)=(AB)(AC)A=A,AE=~AAA=,A~A=E2023/7/3126離散數(shù)學(xué)集合證明對稱差的性質(zhì)(證明2)結(jié)合律:A(BC)=(AB)C證明思路：

分解成“基本單位”,例如:1.A~B~C2.AB~C3.ABC4.~A~B~CABCABC12342023/7/3127離散數(shù)學(xué)集合證明對稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律:A(BC)=(AB)C證明:

首先,AB=(A-B)(B-A)(定義)=(A~B)(B~A)(補(bǔ)交轉(zhuǎn)換律)=(A~B)(~AB)(交換律)(*)ABAB2023/7/3128離散數(shù)學(xué)集合證明對稱差的性質(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/7/3129離散數(shù)學(xué)集合證明對稱差的性質(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/7/3130離散數(shù)學(xué)集合證明對稱差的性質(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/7/3131離散數(shù)學(xué)集合證明對稱差的性質(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/7/3132離散數(shù)學(xué)集合證明對稱差的性質(zhì)(討論)有些作者用△表示對稱差:

AB=A△B消去律:AB=ACB=C(習(xí)題一,23)A=BCB=ACC=AB對稱差與補(bǔ):~(AB)=~AB=A~BAB=~A~B問題:ABC=~A~B~C?2023/7/3133離散數(shù)學(xué)集合證明對稱差的性質(zhì)(討論、續(xù))如何把對稱差推廣到n個集合:

A1A2A3…An=?x,xA1A2A3…Anx恰好屬于A1,A2,A3,…,An中的奇數(shù)個特征函數(shù)表達(dá):A1A2…An(x)=A1(x)+A2(x)+…+An(x)(mod2)=A1(x)A2(x)…An(x)((mod2),,都表示模2加法,即相加除以2取余數(shù))2023/7/3134離散數(shù)學(xué)集合證明特征函數(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)AB2023/7/3135離散數(shù)學(xué)集合證明對稱差的性質(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/7/3136離散數(shù)學(xué)集合證明對稱差的性質(zhì)(證明3)分配律:A(BC)=(AB)(AC)證明

A(BC)=A((B~C)(~BC))=(AB~C)(A~BC)ABCA(BC)2023/7/3137離散數(shù)學(xué)集合證明對稱差分配律(證明3、續(xù))(續(xù))(AB)(AC)=((AB)~(AC))(~(AB)(AC))=((AB)(~A~C))((~A~B)(AC))=(AB~C)(A~BC)A(BC)=(AB)(AC).#2023/7/3138離散數(shù)學(xué)集合證明對稱差分配律(討論)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?2023/7/3139離散數(shù)學(xué)集合證明集族的性質(zhì)設(shè)A,B為集族,則1.AB

∪A∪B2.AB

A∪B

3.A

AB

∩B∩A4.AB

∩BA5.A

∩A∪A2023/7/3140離散數(shù)學(xué)集合證明集族的性質(zhì)(證明1)AB

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

A(AA

xA)(∪A定義)

A(AB

xA)(AB)x∪B

(∪B定義)∪A∪B.#2023/7/3141離散數(shù)學(xué)集合證明集族的性質(zhì)(證明2)AB

A∪B

證明:x,xA

AB

xA(AB,合取)A(AB

xA)(EG)x∪B

A∪B.#2023/7/3142離散數(shù)學(xué)集合證明集族的性質(zhì)(證明3)A

AB

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

y(yB

xy)y(yA

xy)(AB)x∩A

∩B

∩A

.#2023/7/3143離散數(shù)學(xué)集合證明集族的性質(zhì)(證明4)AB

∩BA證明:x,x∩B

y(yB

xy)AB

xA(UI)

xA

(AB)∩B

A

.#2023/7/3144離散數(shù)學(xué)集合證明集族的性質(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

.#2023/7/3145離散數(shù)學(xué)集合證明冪集的性質(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/7/3146離散數(shù)學(xué)集合證明冪集的性質(zhì)(證明1)ABP(A)P(B)證明:()x,xP(A)xAxB(AB)xP(B)P(A)P(B)2023/7/3147離散數(shù)學(xué)集合證明冪集的性質(zhì)(證明1、續(xù))ABP(A)P(B)證明(續(xù)):()x,xA{x}P(A){x}P(B)(P(A)P(B))

xBAB.#2023/7/3148離散數(shù)學(xué)集合證明冪集的性質(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/7/3149離散數(shù)學(xué)集合證明冪集的性質(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/7/3150離散數(shù)學(xué)集合證明冪集的性質(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/7/3151離散數(shù)學(xué)集合證明冪集的性質(zhì)(證明4)P(A-B)

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

xP(A-B)并且x(P(A)-P(B)){}