南京大学：《计算机问题求解》课程教学资源（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