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

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

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

预习检查 x∈T, x=s2,for some s∈S, smaller space x=2n+1,for some n∈Z, x∈S

预习检查

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

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

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

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

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

基本证明方式(2) ■利用运算定义作逻辑等值式推演 口例：A-BUC)=(A-B)⌒(A-C) A-(BUC)={x|XEA,but xeBUC} ={x|XEA,but (xgB and xgC)} ={x(x∈A,but xeB)and(x∈A,but xgC)} =(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) = (A-B)  (A-C) 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 A∩B=A→A-B=b: A-B=b→A⌒B=A: 利用已知恒等式或等 A∩B=(A△BL 口例：AOB=A台A-B= B=O⊕B =A AU(A⌒B =(A⊕A)⊕B 口例：AUA⌒B)=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=b (1) (2) (3) (4) 口对于上述等价命题序列，我们只需要证明： (1)→(2)→(3)→(4)→(1) 口在以上例子的基础上，只要再证明： ■A-B=b→AUB=B。 ■注意：AUB=(AUB)∩E=(AUB)⌒(~BUB) =(A~B)UB=B

基本证明方式（4）  循环证明一系列逻辑等值式  AB=B  AB  AB=A  A-B=  对于上述等价命题序列，我们只需要证明： (1)  (2)  (3)  (4)  (1)  在以上例子的基础上，只要再证明：  A-B=  AB=B。  注意：AB= (AB) E=(AB) (BB) =(AB)B = B (1) (2) (3) (4)

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

文氏图与数学证明 ■ 文氏图不能代替数学证明，但可以帮助推 测结论 ”例子： E (1)(A-B)(A-C)=A 充要条件： B A⌒B∽C=φ

文氏图与数学证明  文氏图不能代替数学证明, 但可以帮助推 测结论  例子：  (1) (A-B)(A-C)=A 充要条件： ABC=