离散数学 集合证明

第4讲集合恒等式内容提要1.集合恒等式与对偶原理2.集合恒等式的证明3.集合列的极限4.集合论悖论与集合论公理2024/4/281《集合论与图论》第4讲集合恒等式(关于

与

)等幂律(idempotentlaws)A

A=AA

A=A交换律(commutativelaws)A

B=B

AA

B=B

A2024/4/282《集合论与图论》第4讲集合恒等式(关于

与

、续)结合律(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讲集合恒等式(关于

与

、续)吸收律(absorptionlaws)A

(A

B)=AA

(A

B)=A2024/4/284《集合论与图论》第4讲集合恒等式(关于~)双重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(A

B)=~A~B~(A

B)=~A

~B2024/4/285《集合论与图论》第4讲集合恒等式(关于

与E)零律(dominancelaws)AE=EA

=

同一律(identitylaws)A

=AA

E=A2024/4/286《集合论与图论》第4讲集合恒等式(关于

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

全补律~

=E~E=

2024/4/287《集合论与图论》第4讲集合恒等式(关于-)补交转换律(differenceasintersection)A-B=A~B2024/4/288《集合论与图论》第4讲集合恒等式(推广到集族)分配律德●摩根律2024/4/289《集合论与图论》第4讲对偶(dual)原理对偶式(dual):一个集合关系式,如果只含有,

,~,,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讲对偶原理(举例、续)零律A

E=EA

=

同一律A

=AA

E=A2024/4/2812《集合论与图论》第4讲对偶原理(举例、续)A

B

AA

B

A

AE

A2024/4/2813《集合论与图论》第4讲集合恒等式证明(方法)逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集合恒等式和已知结论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讲吸收律(证明、续)A

(A

B)=A证明:A

(A

B)=(AA)(A

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

A

(A

B)=AAB2024/4/2821《集合论与图论》第4讲集合演算法(格式,续)题目: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讲集合恒等式证明(举例)基本集合恒等式对称差(

)的性质集族({A

}S)的性质幂集(P())的性质2024/4/2823《集合论与图论》第4讲补交转换律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)(补交转换律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等幂律)=(A~B)(A~C)(交换律,结合律)=(A-B)(B-A)(补交转换律).#2024/4/2825《集合论与图论》第4讲对称差的性质交换律:AB=BA结合律:A(BC)=(AB)C分配律:A

(BC)=(AB)

(AC)A

=A,AE=~AAA=

,A~A=E2024/4/2826《集合论与图论》第4讲对称差的性质(证明2)结合律:

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

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

B~C3.A

B

C4.~A~B~CABCABC12342024/4/2827《集合论与图论》第4讲对称差的性质(证明2、续1)结合律:A(BC)=(AB)C证明:

首先,AB=(A-B)(B-A)(定义)=(A~B)(B~A)(补交转换律)=(A~B)(~A

B)(交换律)(*)ABAB2024/4/2828《集合论与图论》第4讲对称差的性质(证明2、续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讲对称差的性质(证明2、续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讲对称差的性质(证明2、续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讲对称差的性质(证明2、续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讲对称差的性质(讨论)有些作者用△表示对称差:

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

B=C(习题一,23)A=BC

B=AC

C=AB对称差与补:~(AB)=~AB=A~BAB=~A~B问题:ABC=~A

~B~C?2024/4/2833《集合论与图论》第4讲对称差的性质(讨论、续)如何把对称差推广到n个集合:

A1A2A3…An=?x,x

A1A2A3…An

x恰好属于A1,A2,A3,…,An中的奇数个特征函数表达:

A1A2…An(x)=

A1(x)+

A2(x)+…+

An(x)(mod2)=

A1(x)

A2(x)

…

An(x)((mod2),,都表示模2加法,即相加除以2取余数)2024/4/2834《集合论与图论》第4讲特征函数与集合运算:

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讲对称差的性质(讨论、续)问题: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讲对称差的性质(证明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、续)(续)(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讲集族的性质设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讲集族的性质(证明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讲集族的性质(证明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讲集族的性质(证明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讲集族的性质(证明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讲集族的性质(证明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

.#2024/4/2845《集合论与图论》第4讲幂集的性质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讲幂集的性质(证明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讲幂集的性质(证明1、续)A

B

P(A)

P(B)证明(续):(

)

x,x

A{x}

P(A){x}

P(B)(P(A)

P(B))

x

B

A

B.#2024/4/2848《集合论与图论》第4讲幂集的性质(证明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讲幂集的性质(证明2、续)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讲幂集的性质(证明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讲幂集的性质(证明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)