离散数学-集合证明

第4讲集合恒等式内容提要1.集合恒等式与对偶原理2.集合恒等式证实3.集合列极限4.集合论悖论与集合论公理2025/5/91《集合论与图论》第4讲第1页集合恒等式(关于

与

)等幂律(idempotentlaws)A

A=AA

A=A交换律(commutativelaws)A

B=B

AA

B=B

A2025/5/92《集合论与图论》第4讲第2页集合恒等式(关于

与

、续)结合律(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)2025/5/93《集合论与图论》第4讲第3页集合恒等式(关于

与

、续)吸收律(absorptionlaws)A

(A

B)=AA

(A

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

B)=~A~B~(A

B)=~A

~B2025/5/95《集合论与图论》第4讲第5页集合恒等式(关于

与E)零律(dominancelaws)AE=EA

=

同一律(identitylaws)A

=AA

E=A2025/5/96《集合论与图论》第4讲第6页集合恒等式(关于

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

全补律~

=E~E=

2025/5/97《集合论与图论》第4讲第7页集合恒等式(关于-)补交转换律(differenceasintersection)A-B=A~B2025/5/98《集合论与图论》第4讲第8页集合恒等式(推广到集族)分配律德●摩根律2025/5/99《集合论与图论》第4讲第9页对偶(dual)原理对偶式(dual):一个集合关系式,假如只含有,

,~,,E,=,,

那么,同时把

与

交换,把

与E交换,把

与

交换,得到式子称为原式对偶式.对偶原理:对偶式同真假.或者说,集合恒等式对偶式还是恒等式.2025/5/910《集合论与图论》第4讲第10页对偶原理(举例)分配律A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)排中律A

~A=E矛盾律A

~A=

2025/5/911《集合论与图论》第4讲第11页对偶原理(举例、续)零律A

E=EA

=

同一律A

=AA

E=A2025/5/912《集合论与图论》第4讲第12页对偶原理(举例、续)A

B

AA

B

A

AE

A2025/5/913《集合论与图论》第4讲第13页集合恒等式证实(方法)逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集合恒等式和已知结论2025/5/914《集合论与图论》第4讲第14页逻辑演算法(格式)题目:A=B.证实:

x,

xA

…(????)

xB

A=B.#题目:A

B.证实:

x,

xA

…(????)

xB

A

B.#2025/5/915《集合论与图论》第4讲第15页分配律(证实)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)2025/5/916《集合论与图论》第4讲第16页零律(证实)A

=

证实:

x,xA

xAx

(

定义)xA0

(

定义)0(命题逻辑零律)

A

=

2025/5/917《集合论与图论》第4讲第17页排中律(证实)A~A=E证实:

x,xA~A

xAx~A(

定义)xAxA(~定义)xAxA(定义)

1(命题逻辑排中律)

A~A=E2025/5/918《集合论与图论》第4讲第18页集合演算法(格式)题目:A=B.证实:A

=…(????)

=B

A=B.#题目:A

B.证实:A

…(????)

B

A

B.#2025/5/919《集合论与图论》第4讲第19页吸收律(证实)A

(A

B)=A证实:A

(A

B)=(AE)(A

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

A

(A

B)=AAB2025/5/920《集合论与图论》第4讲第20页吸收律(证实、续)A

(A

B)=A证实:A

(A

B)=(AA)(A

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

A

(A

B)=AAB2025/5/921《集合论与图论》第4讲第21页集合演算法(格式,续)题目:A=B.证实:(

)…

A

B(

)…

A

B

A=B.#说明:分=成与题目:A

B.证实:A

B(或A

B)

=…(????)

=

A(或B)

A

B.#说明:化成=A

B=AA

BA

B=BA

B2025/5/922《集合论与图论》第4讲第22页集合恒等式证实(举例)基本集合恒等式对称差(

)性质集族({A

}S)性质幂集(P())性质2025/5/923《集合论与图论》第4讲第23页补交转换律A-B=A~B证实:

x,x

A-B

x

A

xB

x

Ax~B

x

A~BA-B=A~B.#2025/5/924《集合论与图论》第4讲第24页德●摩根律相对形式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)(补交转换律).#2025/5/925《集合论与图论》第4讲第25页对称差性质交换律:AB=BA结合律:A(BC)=(AB)C分配律:A

(BC)=(AB)

(AC)A

=A,AE=~AAA=

,A~A=E2025/5/926《集合论与图论》第4讲第26页对称差性质(证实2)结合律:A(BC)=(AB)C证实思绪：

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

B~C3.A

B

C4.~A~B~CABCABC12342025/5/927《集合论与图论》第4讲第27页对称差性质(证实2、续1)结合律:A(BC)=(AB)C证实:

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

B)(交换律)(*)ABAB2025/5/928《集合论与图论》第4讲第28页对称差性质(证实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)))(德•摩根律)2025/5/929《集合论与图论》第4讲第29页对称差性质(证实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)(分配律…)2025/5/930《集合论与图论》第4讲第30页对称差性质(证实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)(德•摩根律)2025/5/931《集合论与图论》第4讲第31页对称差性质(证实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.#2025/5/932《集合论与图论》第4讲第32页对称差性质(讨论)有些作者用△表示对称差:

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

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

B=AC

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

~B~C?2025/5/933《集合论与图论》第4讲第33页对称差性质(讨论、续)怎样把对称差推广到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取余数)2025/5/934《集合论与图论》第4讲第34页特征函数与集合运算:

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)AB2025/5/935《集合论与图论》第4讲第35页对称差性质(讨论、续)问题: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)2025/5/936《集合论与图论》第4讲第36页对称差性质(证实3)分配律:A

(BC)=(A

B)(A

C)证实

A

(B

C)=A

((B~C)(~B

C))=(A

B~C)(A~B

C)ABCA(BC)2025/5/937《集合论与图论》第4讲第37页对称差分配律(证实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).#2025/5/938《集合论与图论》第4讲第38页对称差分配律(讨论)A

(BC)=(A

B)(A

C)

A

(BC)=(A

B)(A

C)?A(B

C)=(AB)

(AC)?A(B

C)=(AB)

(AC)?2025/5/939《集合论与图论》第4讲第39页集族性质设A,B为集族,则1.A

B

∪A

∪B2.A

B

A

∪B

3.A

A

B

∩B

∩A4.A

B

∩B

A5.A

∩A

∪A2025/5/940《集合论与图论》第4讲第40页集族性质(证实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.#2025/5/941《集合论与图论》第4讲第41页集族性质(证实2)A

B

A

∪B

证实:

x,x

A

A

B

x

A(A

B,合取)

A(A

B

x

A)(EG)

x

∪B

A

∪B.#2025/5/942《集合论与图论》第4讲第42页集族性质(证实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

.#2025/5/943《集合论与图论》第4讲第43页集族性质(证实4)A

B

∩B

A证实:

x,x

∩B

y(y

B

x

y)

A

B

x

A(UI)

x

A

(A

B)

∩B

A

.#2025/5/944《集合论与图论》第4讲第44页集族性质(证实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

.#2025/5/945《集合论与图论》第4讲第45页幂集性质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)){}2025/5/946《集合论与图论》第4讲第46页幂集性质(证实1)A

B

P(A)

P(B)证实:(

)x,x

P(A)

x

A

x

B(A

B)

x

P(B)P(A)

P(B)2025/5/947《集合论与图论》第4讲第47页幂集性质(证实1、续)A

B

P(A)

P(B)证实(续):(

)

x,x

A{x}

P(A){x}

P(B)(P(A)

P(B))

x

B

A

B.#2025/5/948《集合论与图论》第4讲第48页幂集性质(证实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)2025/5/949《集合论与图论》第4讲第49页幂集性质(证实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).#2025/5/950《集合论与图论》第4讲第50页幂集性质(证实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).#2025/5/951《集合论与图论》第4讲第51页幂集性质(证实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

A