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

第4講集合恒等式內(nèi)容提要1.集合恒等式與對偶原理2.集合恒等式的證明3.集合列的極限4.集合論悖論與集合論公理2024/4/281《集合論與圖論》第4講集合恒等式(關(guān)于

與

)等冪律(idempotentlaws)A

A=AA

A=A交換律(commutativelaws)A

B=B

AA

B=B

A2024/4/282《集合論與圖論》第4講集合恒等式(關(guān)于

與

、續(xù))結(jié)合律(associativelaws)(A

B)

C=A

(B

C)

(A

B)

C=A

(B

C)

分配律(distributivelaws)A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)2024/4/283《集合論與圖論》第4講集合恒等式(關(guān)于

與

、續(xù))吸收律(absorptionlaws)A

(A

B)=AA

(A

B)=A2024/4/284《集合論與圖論》第4講集合恒等式(關(guān)于~)雙重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(A

B)=~A~B~(A

B)=~A

~B2024/4/285《集合論與圖論》第4講集合恒等式(關(guān)于

與E)零律(dominancelaws)AE=EA

=

同一律(identitylaws)A

=AA

E=A2024/4/286《集合論與圖論》第4講集合恒等式(關(guān)于

,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=

全補律~

=E~E=

2024/4/287《集合論與圖論》第4講集合恒等式(關(guān)于-)補交轉(zhuǎn)換律(differenceasintersection)A-B=A~B2024/4/288《集合論與圖論》第4講集合恒等式(推廣到集族)分配律德●摩根律2024/4/289《集合論與圖論》第4講對偶(dual)原理對偶式(dual):一個集合關(guān)系式,如果只含有,

,~,,E,=,,

那么,同時把

與

互換,把

與E互換,把

與

互換,得到的式子稱為原式的對偶式.對偶原理:對偶式同真假.或者說,集合恒等式的對偶式還是恒等式.2024/4/2810《集合論與圖論》第4講對偶原理(舉例)分配律A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)排中律A

~A=E矛盾律A

~A=

2024/4/2811《集合論與圖論》第4講對偶原理(舉例、續(xù))零律A

E=EA

=

同一律A

=AA

E=A2024/4/2812《集合論與圖論》第4講對偶原理(舉例、續(xù))A

B

AA

B

A

AE

A2024/4/2813《集合論與圖論》第4講集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結(jié)論2024/4/2814《集合論與圖論》第4講邏輯演算法(格式)題目:A=B.證明:

x,

xA

…(????)

xB

A=B.#題目:A

B.證明:

x,

xA

…(????)

xB

A

B.#2024/4/2815《集合論與圖論》第4講分配律(證明)A

(B

C)=(A

B)

(A

C)證明:

x,

xA

(B

C)

xAx(B

C)(

定義)xA(xB

xC)(

定義)(xAxB)(xAxC)(命題邏輯分配律)(xA

B)(xA

C)(

定義)x(A

B)(A

C)(

定義)

A

(B

C)=(A

B)

(A

C)2024/4/2816《集合論與圖論》第4講零律(證明)A

=

證明:

x,xA

xAx

(

定義)xA0

(

定義)0

(命題邏輯零律)

A

=

2024/4/2817《集合論與圖論》第4講排中律(證明)A~A=E證明:

x,xA~A

xAx~A(

定義)xAxA(~定義)xAxA(定義)

1(命題邏輯排中律)

A~A=E2024/4/2818《集合論與圖論》第4講集合演算法(格式)題目:A=B.證明:A

=…(????)

=B

A=B.#題目:A

B.證明:A

…(????)

B

A

B.#2024/4/2819《集合論與圖論》第4講吸收律(證明)A

(A

B)=A證明:A

(A

B)=(AE)(A

B)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)

A

(A

B)=AAB2024/4/2820《集合論與圖論》第4講吸收律(證明、續(xù))A

(A

B)=A證明:A

(A

B)=(AA)(A

B)(分配律)=A(AB)(等冪律)=A(吸收律第一式)

A

(A

B)=AAB2024/4/2821《集合論與圖論》第4講集合演算法(格式,續(xù))題目:A=B.證明:(

)…

A

B(

)…

A

B

A=B.#說明:分=成與題目:A

B.證明:

A

B(或A

B)

=…(????)

=

A(或B)

A

B.#說明:化成=A

B=AA

BA

B=BA

B2024/4/2822《集合論與圖論》第4講集合恒等式證明(舉例)基本集合恒等式對稱差(

)的性質(zhì)集族({A

}S)的性質(zhì)冪集(P())的性質(zhì)2024/4/2823《集合論與圖論》第4講補交轉(zhuǎn)換律A-B=A~B證明:

x,x

A-B

x

A

xB

x

Ax~B

x

A~BA-B=A~B.#2024/4/2824《集合論與圖論》第4講德●摩根律的相對形式A-(B

C)=(A-B)

(A-C)A-(B

C)=(A-B)

(A-C)證明:A-(B

C)=A~(B

C)(補交轉(zhuǎn)換律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等冪律)=(A~B)(A~C)(交換律,結(jié)合律)=(A-B)(B-A)(補交轉(zhuǎn)換律).#2024/4/2825《集合論與圖論》第4講對稱差的性質(zhì)交換律:AB=BA結(jié)合律:A(BC)=(AB)C分配律:A

(BC)=(AB)

(AC)A

=A,AE=~AAA=

,A~A=E2024/4/2826《集合論與圖論》第4講對稱差的性質(zhì)(證明2)結(jié)合律:

A(BC)=(AB)C證明思路：

分解成“基本單位”,例如:1.A~B~C2.A

B~C3.A

B

C4.~A~B~CABCABC12342024/4/2827《集合論與圖論》第4講對稱差的性質(zhì)(證明2、續(xù)1)結(jié)合律:A(BC)=(AB)C證明:

首先,AB=(A-B)(B-A)(定義)=(A~B)(B~A)(補交轉(zhuǎn)換律)=(A~B)(~A

B)(交換律)(*)ABAB2024/4/2828《集合論與圖論》第4講對稱差的性質(zhì)(證明2、續(xù)2)其次,A

(BC)=(A~(B

C))(~A

(B

C))(*)=(A

~((B~C)(~B

C)))

(~A

((B~C)(~B

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

C)))

(~A

((B~C)(~B

C)))(德?摩根律)2024/4/2829《集合論與圖論》第4講對稱差的性質(zhì)(證明2、續(xù)3)=(A(~(B~C)

~(~B

C)))

(~A

((B~C)(~B

C)))=(A(~B

C)(B~C)))

(~A

((B~C)(~B

C)))(德?摩根律)=(A

B

C)

(A~B~C)

(~A

B~C)(~A~B

C)(分配律…)2024/4/2830《集合論與圖論》第4講對稱差的性質(zhì)(證明2、續(xù)4)

同理,(AB)

C=(A

B)~C)(~(A

B)

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

B))~C)

(~((A~B)(~A

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

B))~C)

((~(A~B)~(~A

B))C)(德?摩根律)2024/4/2831《集合論與圖論》第4講對稱差的性質(zhì)(證明2、續(xù)5)=(((A~B)(~A

B))~C)

((~(A~B)

~(~A

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

B))~C)

((~A

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

(~A

B~C)

(~A~B

C)(A

B

C)(分配律…)

A(BC)=(AB)C.#2024/4/2832《集合論與圖論》第4講對稱差的性質(zhì)(討論)有些作者用△表示對稱差:

AB=A△B消去律:AB=AC

B=C(習(xí)題一,23)A=BC

B=AC

C=AB對稱差與補:~(AB)=~AB=A~BAB=~A~B問題:ABC=~A

~B~C?2024/4/2833《集合論與圖論》第4講對稱差的性質(zhì)(討論、續(xù))如何把對稱差推廣到n個集合:

A1A2A3…An=?x,x

A1A2A3…An

x恰好屬于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ù))2024/4/2834《集合論與圖論》第4講特征函數(shù)與集合運算:

A

B(x)=

A(x)

B(x)

~A(x)=1-

A(x)

A-B(x)=

A~B(x)=

A(x)(1-

B(x))

A

B(x)=

(A-B)

B(x)=

A(x)+

B(x)-

A(x)

B(x)

A

B(x)=

A(x)+

B(x)(mod2)=

A(x)

B(x)AB2024/4/2835《集合論與圖論》第4講對稱差的性質(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)2024/4/2836《集合論與圖論》第4講對稱差的性質(zhì)(證明3)分配律:A

(BC)=(A

B)(A

C)證明

A

(B

C)=A

((B~C)(~B

C))=(A

B~C)(A~B

C)ABCA(BC)2024/4/2837《集合論與圖論》第4講對稱差分配律(證明3、續(xù))(續(xù))(A

B)

(A

C)=((A

B)

~(A

C))(~(A

B)(A

C))=((A

B)(~A~C))((~A~B)(A

C))

=(A

B~C)

(A~B

C)

A

(BC)=(A

B)(A

C).#2024/4/2838《集合論與圖論》第4講對稱差分配律(討論)A

(BC)=(A

B)(A

C)

A

(BC)=(A

B)(A

C)?A(B

C)=(AB)

(AC)?A(B

C)=(AB)

(AC)?2024/4/2839《集合論與圖論》第4講集族的性質(zhì)設(shè)A,B為集族,則1.A

B

∪A

∪B2.A

B

A

∪B

3.A

A

B

∩B

∩A4.A

B

∩B

A5.A

∩A

∪A2024/4/2840《集合論與圖論》第4講集族的性質(zhì)(證明1)A

B

∪A

∪B證明:

x,x

∪A

A(A

A

x

A)(∪A定義)

A(A

B

x

A)(A

B)

x

∪B

(∪B定義)

∪A

∪B.#2024/4/2841《集合論與圖論》第4講集族的性質(zhì)(證明2)A

B

A

∪B

證明:

x,x

A

A

B

x

A(A

B,合取)

A(A

B

x

A)(EG)

x

∪B

A

∪B.#2024/4/2842《集合論與圖論》第4講集族的性質(zhì)(證明3)A

A

B

∩B

∩A說明:若約定∩=E,則A

的條件可去掉.證明:

x,x

∩B

y(y

B

x

y)

y(y

A

x

y)(A

B)

x

∩A

∩B

∩A

.#2024/4/2843《集合論與圖論》第4講集族的性質(zhì)(證明4)A

B

∩B

A證明:

x,x

∩B

y(y

B

x

y)

A

B

x

A(UI)

x

A

(A

B)

∩B

A

.#2024/4/2844《集合論與圖論》第4講集族的性質(zhì)(證明5)A

∩A

∪A說明:A

的條件不可去掉!證明:

A

y(y

A),設(shè)A

A.

x,x

∩A

y(y

A

x

y)

A

A

x

A

x

A(A

A)

A

Ax

A

y(y

A

x

y)

x

∪A

∩A

∪A

.#2024/4/2845《集合論與圖論》第4講冪集的性質(zhì)A

BP(A)

P(B)P(A)

P(B)

P(A

B)P(A)

P(B)

=

P(A

B)P(A-B)

(P(A)-P(B)){}2024/4/2846《集合論與圖論》第4講冪集的性質(zhì)(證明1)A

B

P(A)

P(B)證明:(

)x,x

P(A)

x

A

x

B(A

B)

x

P(B)P(A)

P(B)2024/4/2847《集合論與圖論》第4講冪集的性質(zhì)(證明1、續(xù))A

B

P(A)

P(B)證明(續(xù)):(

)

x,x

A{x}

P(A){x}

P(B)(P(A)

P(B))

x

B

A

B.#2024/4/2848《集合論與圖論》第4講冪集的性質(zhì)(證明2)P(A)

P(B)

P(A

B)證明:

x,x

P(A)

P(B)

x

P(A)x

P(B)

x

Ax

B

x

A

B

x

P(A

B)

P(A)

P(B)

P(A

B)2024/4/2849《集合論與圖論》第4講冪集的性質(zhì)(證明2、續(xù))P(A)

P(B)

P(A

B)討論:給出反例,說明等號不成立:

A={1},B={2},A

B={1,2},P(A)={,{1}},P(B)={,{2}},P(A

B)={,{1},{2},{1,2}}P(A)

P(B)

{,{1},{2}}

此時,P(A)

P(B)

P(A

B).#2024/4/2850《集合論與圖論》第4講冪集的性質(zhì)(證明3)P(A)

P(B)=P(A

B)證明:

x,x

P(A)

P(B)

x

P(A)

x

P(B)

x

Ax

B

x

A

B

x

P(A

B)

P(A)

P(B)=P(A

B).#2024/4/2851《集合論與圖論》第4講冪集的性質(zhì)(證明4)P(A-B)

(P(A)-P(B)){}證明:

x,

分兩種情況,(1)x=

,這時

x

P(A-B)并且

x(P(A)-P(B)){}(2)x

,這時

x

P(A-B)