離散數(shù)學 集合

離散數(shù)學集合第1頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講2集合恒等式(關于

與

)等冪律(idempotentlaws)A

A=AA

A=A交換律(commutativelaws)A

B=B

AA

B=B

A第2頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講3集合恒等式(關于

與、續(xù))結合律(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)第3頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講4集合恒等式(關于

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

(A

B)=AA

(A

B)=A第4頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講5集合恒等式(關于~)雙重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(A

B)=~A~B~(A

B)=~A

~B第5頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講6集合恒等式(關于

與E)零律(dominancelaws)AE=EA

=

同一律(identitylaws)A

=AA

E=A第6頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講7集合恒等式(關于

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

全補律~

=E~E=

第7頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講8集合恒等式(關于-)補交轉換律(differenceasintersection)A-B=A~B第8頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講9集合恒等式(推廣到集族)分配律德●摩根律第9頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講10對偶(dual)原理對偶式(dual):一個集合關系式,如果只含有

,

,~,,E,=,,

那么,同時把

與

互換,把

與E互換,把

與

互換,得到的式子稱為原式的對偶式.對偶原理:對偶式同真假.或者說,集合恒等式的對偶式還是恒等式.第10頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講11對偶原理(舉例)分配律A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)排中律A

~A=E矛盾律A

~A=

第11頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講12對偶原理(舉例、續(xù))零律A

E=EA

=

同一律A

=AA

E=A第12頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講13對偶原理(舉例、續(xù))A

B

AA

B

A

AE

A第13頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講14集合恒等式證明(方法)邏輯演算法:利用邏輯等值式和推理規(guī)則集合演算法:利用集合恒等式和已知結論第14頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講15邏輯演算法(格式)題目:A=B.證明:

x,

xA

…(????)

xB

A=B.#題目:A

B.證明:

x,

xA

…(????)

xB

A

B.#第15頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講16分配律(證明)A

(B

C)=(A

B)

(A

C)證明:

x,

xA

(B

C)

xAx(B

C)(

定義)xA(xB

xC)(

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

定義)x(AB)(AC)(

定義)

A

(B

C)=(A

B)

(A

C)第16頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講17零律(證明)A

=

證明:

x,xA

xAx(

定義)xA0

(

定義)0(命題邏輯零律)

A

=

第17頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講18排中律(證明)A~A=E證明:

x,xA~A

xAx~A(

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

1(命題邏輯排中律)

A~A=E第18頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講19集合演算法(格式)題目:A=B.證明:A

=…(????)

=B

A=B.#題目:A

B.證明:A

…(????)

B

A

B.#第19頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講20吸收律(證明)A

(A

B)=A證明:A

(A

B)=(AE)(A

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

A

(A

B)=AAB第20頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講21吸收律(證明、續(xù))A

(A

B)=A證明:A

(A

B)=(AA)(A

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

A

(A

B)=AAB第21頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講22集合演算法(格式,續(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

B第22頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講23集合恒等式證明(舉例)基本集合恒等式對稱差(

)的性質集族({A

}S)的性質冪集(P())的性質第23頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講24補交轉換律A-B=A~B證明:

x,x

A-B

x

A

xB

x

Ax~B

x

A~BA-B=A~B.#第24頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講25德

摩根律的相對形式A-(B

C)=(A-B)

(A-C)A-(B

C)=(A-B)

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

C)=A~(B

C)(補交轉換律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等冪律)=(A~B)(A~C)(交換律,結合律)=(A-B)(A-C)(補交轉換律).#第25頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講26對稱差的性質交換律:AB=BA結合律:A(BC)=(AB)C分配律:A

(BC)=(A

B)(A

C)A

=A,AE=~AAA=

,A~A=E第26頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講27對稱差的性質(證明2)結合律:A(BC)=(AB)C證明思路：分解成“基本單位”,例如:1.A~B~C2.A

B~C3.A

B

C4.~A~B~CABCABC1234第27頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講28對稱差的性質(證明2、續(xù)1)結合律:A(BC)=(AB)C證明:

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

B)(交換律)(*)ABAB第28頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講29對稱差的性質(證明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)))(德?摩根律)第29頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講30對稱差的性質(證明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)(分配律…)第30頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講31對稱差的性質(證明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)(德?摩根律)第31頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講32對稱差的性質(證明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.#第32頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講33對稱差的性質(作業(yè)）有些作者用△表示對稱差:

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

B=CA=BC

B=AC

C=AB對稱差與補:~(AB)=~AB=A~BAB=~A~B問題:ABC=~A~B~C?第33頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講34對稱差的性質(作業(yè)續(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ù))第34頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講35特征函數(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)AB第35頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講36對稱差的性質(討論、續(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)第36頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講37對稱差的性質(證明3)分配律:A

(BC)=(A

B)(A

C)證明

A

(B

C)=A

((B~C)(~B

C))=(A

B~C)(A~B

C)ABCA(BC)第37頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講38對稱差分配律(證明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).#第38頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講39對稱差分配律(討論)A

(BC)=(A

B)(A

C)

A

(BC)=(A

B)(A

C)?A(B

C)=(AB)

(AC)?A(B

C)=(AB)

(AC)?第39頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講40集族的性質設A,B為集族,則1.A

B

∪A

∪B2.A

B

A

∪B

3.A

A

B

∩B

∩A4.A

B

∩B

A5.A

∩A

∪A第40頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講41集族的性質(證明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.#第41頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講42集族的性質(證明2)A

B

A

∪B

證明:

x,x

A

A

B

x

A(A

B,合取)

A(A

B

x

A)(EG)

x

∪B

A

∪B.#第42頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講43集族的性質(證明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

.#第43頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講44集族的性質(證明4)A

B

∩B

A證明:

x,x

∩B

y(y

B

x

y)

A

B

x

A(UI)

x

A

(A

B)

∩B

A

.#第44頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講45集族的性質(證明5)A

∩A

∪A說明:A

的條件不可去掉!證明:

A

y(y

A),設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

.#第45頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講46冪集的性質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)){}第46頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講47冪集的性質(證明1)A

B

P(A)

P(B)證明:(

)x,x

P(A)

x

A

x

B(A

B)

x

P(B)P(A)

P(B)第47頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講48冪集的性質(證明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.#第48頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講49冪集的性質(證明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)第49頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講50冪集的性質(證明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).#第50頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講51冪集的性質(證明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).#第51頁，課件共62頁，創(chuàng)作于2023年2月2023/9/3《集合論與圖論》第4講52冪集的性質(證明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)

x

A-B

x

Ax

B

x

P(A)xP(B)

x

P(A)-P(B)

P(A-B)

(P(A)-P(B)){}.#AB第52頁，課件共62頁，創(chuàng)作于2023