南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）集合及其运算

计算机问题求解一论题1-8 集合及其运算 2017年11月23日

计算机问题求解 – 论题1-8 - 集合及其运算 2017年11月23日

问题1：什么是集合？ a朴素集合论(Naive Set Theory) 口一堆（满足特定性质的）物件构成的整体 口悖论： 罗素悖论：设集合S是由一切不属于自身的集 合所组成 LetR={x|x走x,thenR∈R←→R庆R Georg Cantor(1845-1918) Burali-Forti paradox ● a公理集合论(Axiomatic set theory) 口集合和集合成员并不直接被定义，而是先 规范可以描述其性质的一些公理 Bertrand Russell(1872-1970) https://en.wikipedia org/wiki/Georg Cantor https://en.wikipedia.org/wiki/Bertrand Russell

问题1：什么是集合？ ◼ 朴素集合论(Naïve Set Theory) ❑ 一堆（满足特定性质的）物件构成的整体 ❑ 悖论： ◼ 罗素悖论：设集合S是由一切不属于自身的集 合所组成 ◼ Burali-Forti paradox ◼ … ◼ 公理集合论(Axiomatic set theory) ❑ 集合和集合成员并不直接被定义，而是先 规范可以描述其性质的一些公理 Georg Cantor(1845-1918) Bertrand Russell(1872-1970) https://en.wikipedia.org/wiki/Georg_Cantor https://en.wikipedia.org/wiki/Bertrand_Russell

问题2： 两个集合“相等”究 竞是什么意思？

关于集合相等 ■集合“完全由其包含的元素所确定”。 因此：两个集合相等，就是“两个集合所包含 的元素完全一样”。 口完全一样如何以严格的数学方式表述？ ·与集合包含的关系 口对任意集合A,B,A=Bif.AcB,且BcA

关于集合相等 ◼ 集合“完全由其包含的元素所确定”。 ◼ 因此：两个集合相等，就是“两个集合所包含 的元素完全一样”。 ❑ 完全一样如何以严格的数学方式表述？ ◼ 与集合包含的关系 ❑ 对任意集合A, B, A=B iff. AB, 且 BA

基本证明方式（1) ·直接使用集合包含或相等定义 口例1：AUB=B→AcB 口例2：AcB→A∩B=A 例1，待证结论：AcB 因此：证明过程如下： 即：对任何XX∈A→X∈B 对任何x,假设x∈A 因此：证明过程如下： 由集合并定义：x∈AUB 对任何x,假设x∈A 由已知条件：AUB=B ∴.X∈B ∴.X∈B 因此：AcB 因此：AcB

基本证明方式（1） ◼ 直接使用集合包含或相等定义 ❑ 例1：𝐴 ∪ 𝐵 = 𝐵 ⇒ 𝐴𝐵 ❑ 例2：𝐴𝐵 ⇒ 𝐴 ∩ 𝐵 = 𝐴 例1，待证结论：AB 即：对任何x, xA  xB 因此：证明过程如下： 对任何x, 假设xA x B 因此： AB 因此：证明过程如下： 对任何x, 假设xA 由集合并定义：𝑥𝐴 ∪ 𝐵 由已知条件：𝐴 ∪ 𝐵 = 𝐵 x B 因此： AB

基本证明方式(2) ■利用运算定义作逻辑等值式推演 口 例：A-(BUC)=(A-B)n(A-C) A-(BUC)={x|XEA,but xeBUC} ={x]XEA,but (xeB and xeC)} ={xX(X∈A,but xeB)and(X∈A,but xeC)} =(A-B)⌒(A-C) 另一种等价的描述方式： X∈A-(BUC)→(X∈A)A(XE(BUC)台X∈A∧XEB∧XEC 台(x∈AΛXEB)∧(X∈AΛXEC) →(X∈(A-B)∧(X∈(A-C) 台X∈(A-B)⌒(A-C)】

基本证明方式（2） ◼ 利用运算定义作逻辑等值式推演 ❑ 例：𝑨 − 𝑩 ∪ 𝑪 = 𝑨 − 𝑩 ∩ (𝑨 − 𝑪) A-(BC)={x|xA, but xBC} ={x| xA, but (xB and xC)} ={x|(xA, but xB) and (xA, but xC)} = (A-B)  (A-C) 另一种等价的描述方式： xA-(BC)  (xA) ⋀ (x(BC))  xA⋀ xB ⋀ xC  (xA⋀ xB) ⋀ (xA⋀ xC)  (x(A-B)) ⋀ (x(A-C))  x((A-B)  (A-C))

基本证明方式(3) ■利用已知恒等式或等式作集合代数推演 1.0C A and A CA. 13.AU(BnC)=(AUB)(AUC).(Distributive property) 2.(Ac)=A. 14.An(BUC)=(AnB)U(AnC).(Distributive property) 3.AU0=A. 15.X(AUB)=(XA)(X B).(DeMorgan's law) 4.An0=0. (When X is the universe we also write (AUB)c=AnB. 5.AnA=A. 16.X(AnB)=(XA)(XB).(DeMorgan's law) 6.AUA=A. (When X is the universe we also write (AnB)c=AcUBe. 7.AnB=BA.(Commutative property) 17.A\B=AOBC. 8.AUB=BUA.(Commutative property) 18.A CB if and only if (X B)C(XA). 9.(AUB)UC=AU(BUC).(Associative property) (When X is the universe we also write A C B if and only if BeCAc.) 10.(AnB)nC=An(BC).(Associative property) 19.A CC and BC C if and only if AUBCC. 11.AnBCA. 20.CCA and CC B if and only ifC CAnB. 12.ACAUB. 21.AUB=A if and only if BCA. 22.AnB=B if and only if B C A

基本证明方式（3） ◼ 利用已知恒等式或等式作集合代数推演

基本证明方式(3 A∩B=A→A-B=b: A-B=b→A∩B=A: 利用已知恒等式或等 A⌒B=(A△BL 口例：AOB=A令A-B= =A AU(AOB B=O⊕B =(A⊕A)⊕B 口例：AUAB)=A =A⌒(E =A⊕(A⊕B) 口例：已知A⊕B=A①C,证明B=C =A⊕(A⊕C) 口一个比较复杂的代入的例子： =C 利用A∩B=A台AcB证明： (AUBUC)∩(AUB)-(AU(B-C)⌒A)=B-A (AUBOC)⌒(AUB)=(AUB) (AU(B-C)∩A)=A,s0原式左边=(AUB)-A=B-A

基本证明方式（3） ◼ 利用已知恒等式或等式作集合代数推演 ❑ 例：AB=A  A-B= ❑ 例：A(AB) = A ❑ 例：已知AB=AC, 证明B=C ❑ 一个比较复杂的代入的例子： ◼ 利用A B=A  AB证明： ((ABC)  (AB))-((A(B-C)) A)=B-A AB=AA-B=: A-B = AB = (AB)(AA) = A(BA) = A(AB) = AA =  A-B=AB=A: AB=(AB)(AB) =A(BB)=AE=A (ABC)  (AB)= (AB) (A(B-C)) A)=A, so 原式左边=(AB)-A=B-A A(AB)=(AE) (AB) = A(EB) = AE = A B=ØB =(AA)B =A(AB) =A(AC) =C

基本证明方式(4) ■循环证明一系列逻辑等值式 口AUB=B台AcB台A∩B=A←台A-B=0 (1) (2) (3) (4) 口对于上述等价命题序列，我们只需要证明： (1)→(2)→(3)→(4)→(1) 口在以上例子的基础上，只要再证明： ■A-B=0→AUB=B。 注意：AUB=(AUB)∩E=(AUB)∩(BUB) =(A∩~B)UB=B

基本证明方式（4） ◼ 循环证明一系列逻辑等值式 ❑ 𝐴 ∪ 𝐵 = 𝐵 ⇔ 𝐴𝐵 ⇔ 𝐴 ∩ 𝐵 = 𝐴 ⇔ 𝐴 − 𝐵 = ∅ ❑ 对于上述等价命题序列，我们只需要证明： (1)  (2)  (3)  (4)  (1) ❑ 在以上例子的基础上，只要再证明： ◼ 𝐴 − 𝐵 = ∅ ⇒ 𝐴 ∪ 𝐵 = 𝐵。 ◼ 注意：𝐴 ∪ 𝐵 = 𝐴 ∪ 𝐵 ∩ 𝐸 = 𝐴 ∪ 𝐵 ∩ (~𝐵 ∪ 𝐵) = 𝐴 ∩ ~𝐵 ∪ 𝐵 = 𝐵 (1) (2) (3) (4)

问题3： 文氏图是否可以用于关于 集合的数学证明？