离散数学集合证明

关于离散数学集合证明2023/7/4《集合论与图论》第4讲1第1页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲2集合恒等式(关于与)等幂律(idempotentlaws)AA=AAA=A交换律(commutativelaws)AB=BAAB=BA第2页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲3集合恒等式(关于与、续)结合律(associativelaws)(AB)C=A(BC)

(AB)C=A(BC)

分配律(distributivelaws)A(BC)=(AB)(AC)A(BC)=(AB)(AC)第3页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲4集合恒等式(关于与、续)吸收律(absorptionlaws)A(AB)=AA(AB)=A第4页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲5集合恒等式(关于~)双重否定律(doublecomplementlaw)~~A=A德●摩根律(DeMorgan’slaws)~(AB)=~A~B~(AB)=~A~B第5页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲6集合恒等式(关于与E)零律(dominancelaws)AE=EA=同一律(identitylaws)A=AAE=A第6页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲7集合恒等式(关于,E)排中律(excludedmiddle)A~A=E矛盾律(contradiction)A~A=全补律~=E~E=第7页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲8集合恒等式(关于-)补交转换律(differenceasintersection)A-B=A~B第8页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲9集合恒等式(推广到集族)分配律德●摩根律第9页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲10对偶(dual)原理对偶式(dual):一个集合关系式,如果只含有,

,~,,E,=,,

那么,同时把与互换,把与E互换,把与互换,得到的式子称为原式的对偶式.对偶原理:对偶式同真假.或者说,集合恒等式的对偶式还是恒等式.第10页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲11对偶原理(举例)分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)排中律A

~A=E矛盾律A~A=第11页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲12对偶原理(举例、续)零律AE=EA

=同一律A

=AAE=A第12页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲13对偶原理(举例、续)ABAAB

A

AE

A第13页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲14集合恒等式证明(方法)逻辑演算法:利用逻辑等值式和推理规则集合演算法:利用集合恒等式和已知结论第14页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲15逻辑演算法(格式)题目:A=B.证明:x,

xA

…(????)

xB

A=B.#题目:AB.证明:x,

xA

…(????)

xB

AB.#第15页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲16分配律(证明)A(BC)=(AB)(AC)证明:x,

xA(BC)

xAx(BC)(定义)xA(xB

xC)(定义)(xAxB)(xAxC)(命题逻辑分配律)(xAB)(xAC)(定义)x(AB)(AC)(定义)

A(BC)=(AB)(AC)第16页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲17零律(证明)A=证明:x,xA

xAx(定义)xA0

(定义)0(命题逻辑零律)A=第17页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲18排中律(证明)A~A=E证明:x,xA~A

xAx~A(定义)xAxA(~定义)xAxA(定义)

1(命题逻辑排中律)A~A=E第18页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲19集合演算法(格式)题目:A=B.证明:A

=…(????)

=BA=B.#题目:AB.证明:A

…(????)

BAB.#第19页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲20吸收律(证明)A(AB)=A证明:A(AB)=(AE)(AB)(同一律)=A(EB)(分配律)=AE(零律)=A(同一律)A(AB)=AAB第20页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲21吸收律(证明、续)A(AB)=A证明:A(AB)=(AA)(AB)(分配律)=A(AB)(等幂律)=A(吸收律第一式)A(AB)=AAB第21页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲22集合演算法(格式,续)题目:A=B.证明:()…

AB()…

AB

A=B.#说明:分=成与题目:AB.证明:AB(或AB)

=…(????)

=

A(或B)

AB.#说明:化成=AB=AABAB=BAB第22页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲23集合恒等式证明(举例)基本集合恒等式对称差()的性质集族({A}S)的性质幂集(P())的性质第23页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲24补交转换律A-B=A~B证明:x,xA-BxA

xBxAx~B

xA~BA-B=A~B.#第24页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲25德●摩根律的相对形式A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明:A-(BC)=A~(BC)(补交转换律)=A(~B~C)(德●摩根律)=(AA)(~B~C)(等幂律)=(A~B)(A~C)(交换律,结合律)=(A-B)(B-A)(补交转换律).#第25页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲26对称差的性质交换律:AB=BA结合律:A(BC)=(AB)C分配律:A(BC)=(AB)(AC)A=A,AE=~AAA=,A~A=E第26页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲27对称差的性质(证明2)结合律:A(BC)=(AB)C证明思路：

分解成“基本单位”,例如:1.A~B~C2.AB~C3.ABC4.~A~B~CABCABC1234第27页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲28对称差的性质(证明2、续1)结合律:A(BC)=(AB)C证明:

首先,AB=(A-B)(B-A)(定义)=(A~B)(B~A)(补交转换律)=(A~B)(~AB)(交换律)(*)ABAB第28页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲29对称差的性质(证明2、续2)其次,A(BC)=(A~(BC))(~A(BC))(*)=(A~((B~C)(~BC)))

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

(~A((B~C)(~BC)))(德•摩根律)第29页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲30对称差的性质(证明2、续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)(分配律…)第30页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲31对称差的性质(证明2、续4)

同理,(AB)C=(AB)~C)(~(AB)C)(*)=(((A~B)(~AB))~C)(~((A~B)(~AB))C)(*)=(((A~B)(~AB))~C)((~(A~B)~(~AB))C)(德•摩根律)第31页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲32对称差的性质(证明2、续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.#第32页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲33对称差的性质(讨论)有些作者用△表示对称差:

AB=A△B消去律:AB=ACB=C(习题一,23)A=BCB=ACC=AB对称差与补:~(AB)=~AB=A~BAB=~A~B问题:ABC=~A~B~C?第33页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲34对称差的性质(讨论、续)如何把对称差推广到n个集合:

A1A2A3…An=?x,xA1A2A3…Anx恰好属于A1,A2,A3,…,An中的奇数个特征函数表达:A1A2…An(x)=A1(x)+A2(x)+…+An(x)(mod2)=A1(x)A2(x)…An(x)((mod2),,都表示模2加法,即相加除以2取余数)第34页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲35特征函数与集合运算: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)AB第35页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲36对称差的性质(讨论、续)问题: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页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲37对称差的性质(证明3)分配律:A(BC)=(AB)(AC)证明

A(BC)=A((B~C)(~BC))=(AB~C)(A~BC)ABCA(BC)第37页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲38对称差分配律(证明3、续)(续)(AB)(AC)=((AB)~(AC))(~(AB)(AC))=((AB)(~A~C))((~A~B)(AC))=(AB~C)(A~BC)A(BC)=(AB)(AC).#第38页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲39对称差分配律(讨论)A(BC)=(AB)(AC)A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?A(BC)=(AB)(AC)?第39页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲40集族的性质设A,B为集族,则1.AB

∪A∪B2.AB

A∪B

3.A

AB

∩B∩A4.AB

∩BA5.A

∩A∪A第40页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲41集族的性质(证明1)AB

∪A∪B证明:x,x∪A

A(AA

xA)(∪A定义)

A(AB

xA)(AB)x∪B

(∪B定义)∪A∪B.#第41页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲42集族的性质(证明2)AB

A∪B

证明:x,xA

AB

xA(AB,合取)A(AB

xA)(EG)x∪B

A∪B.#第42页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲43集族的性质(证明3)A

AB

∩B∩A说明:若约定∩=E,则A的条件可去掉.证明:x,x∩B

y(yB

xy)y(yA

xy)(AB)x∩A

∩B

∩A

.#第43页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲44集族的性质(证明4)AB

∩BA证明:x,x∩B

y(yB

xy)AB

xA(UI)

xA

(AB)∩B

A

.#第44页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲45集族的性质(证明5)A

∩A∪A说明:A的条件不可去掉!证明:

A

y(yA),设AA.x,x∩Ay(yA

xy)AA

xAxA(AA)AAxAy(yA

xy)

x∪A∩A

∪A

.#第45页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲46幂集的性质ABP(A)P(B)P(A)P(B)

P(AB)P(A)P(B)

=

P(AB)P(A-B)

(P(A)-P(B)){}第46页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲47幂集的性质(证明1)ABP(A)P(B)证明:()x,xP(A)xAxB(AB)xP(B)P(A)P(B)第47页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲48幂集的性质(证明1、续)ABP(A)P(B)证明(续):()x,xA{x}P(A){x}P(B)(P(A)P(B))

xBAB.#第48页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲49幂集的性质(证明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)第49页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲50幂集的性质(证明2、续)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).#第50页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲51幂集的性质(证明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).#第51页，讲稿共63页，2023年5月2日，星期三2023/7/4《集合论与图论》第4讲52幂集的性质(证明4)P(A-B)

(P(A)-P(B)){}证明:x,分两种情况,(1)x=,这时

xP(A-B)并且x(P(A)-P(B)){}(2)x,这时

xP(A-B)xA-B

xAxB