离散数学Lecture1-1.ppt

集合及其表示 主要内容 朴素集合论：G. Cantor于19世纪末创立。 什么是集合？ 集合的概念 如何表示集合？ 列举法 部分列举法 命题法 归纳定义法 原始概念与派生概念 集合的直观描述 集合的基本属性 无序 无论a, b, c代表什么， {a, b, c} = {a, c, b} = {b, a, c} ={b, c, a} = {c, a, b} = {c, b, a}. 元素可区别（独一无二性） 如果a=b，则 {a, b, c} = {a, c} = {b, c} = {a, a, b, a, b, c, c, c, c}. 该集合最多只有两个元素 集合实例 所有中文字的集合 10以内的素数 {a, b, c, d} 以集合{2}和{3}的元素为元素的集合 以集合{2}和集合{3}为元素的集合 以集合{2}的元素和集合{3}为元素的集合 可以是任意元素组成的集合： {a, 2, Fred, New Jersey} 元素 vs 集合 任意对象a、任意集合A a 属于A ：a是A中的元素， 记为 a?A a不属于A：a不是A中的元素，记为 a?A 两者必具其一 按元素个数的集合种类 设A为任意一个集合 用 n(A) 表示A含有的元素的个数。 A为空集 ：n(A)=0； 常用符号 ? 表示 A为非空集：n(A)≠0 ； A为有限集：n(A)为自然数； A为无限集：n(A)为无穷大。 Venn图（文氏图） 集合之间的关系 设A，B为任意两个集合。 A为B的子集（A ? B） 若对每个a∈A皆有a∈B； A和B相等（A = B） 若A ? B且B ? A； A为B的真子集（A ? B） 若A ? B且A≠B。 集合的常用描述方法 列举法 {4, 5, 6, 7} 部分列举法 {0, 1, ?, 9} {3, 6, 9, 12, ?} 命题法 {x | x为实数 且 x2 =1} {x | p(x)}或{x: p(x)} 归纳法 归纳法 第1步：基本项 定义非空集S0 ? A； 第2步：归纳项 定义一组规则。从A中元素出发，依据这些规则所获得的元素仍是A的元素； 第3步：极小化 如果集合S ? A也满足1和2，则S=A。 例 k?I+， Ak = {x | x为被k整除的自然数} 四种描述方法的比较 反证法 幂集 罗素（B.Russell）悖论 悖论：逻辑矛盾的论述 作业 习题1.1 2. a) c) ； 3. a) f) 5. b) g) ； 6. a) 8. e)； 9. b) d) 集合的运算 集合的运算 设A，B为任意两个集合。 A∪B =　{x｜x∈A或x∈B} A和B的并 A∩B =　{x｜x∈A且x∈B} A和B的交 A－B =　{x｜x∈A且x?B} A和B的差 A?B =　(A∪B) －(A∩B) A和B的对称差 ～A = U － A A的补集 A与B不相交：A∩B=? 文氏图 并运算举例 交运算举例 {a,b,c}?{2,3} = ___ {2,4,6}?{3,4,5} = ______ 差运算 差运算举例 {1,2,3,4,5,6} ? {2,3,5,7,9,11} = ___________ Z ? N ? {… , -1, 0, 1, 2, … } ? {0, 1, … } = {x | x 是整数但不是自然数} = {x | x 是负整数} = {… , -3, -2, -1} 补运算 集合运算举例 A∪B={1, 2, 5, 2, 4}={1, 2, 4, 5} A∩B={2} A－B={1, 5} A?B={1, 4, 5} ～A={0, 3, 4} ～B={0, 1, 3, 5} 集合运算的基本定律 小结（1） 小结（2） 作业 习题1.2 2. c) ； 3. d) 4. a) ； 6. e) 7. a) ； 8. c) A U U=N 0 1 2 5 4 U A B 3 U={0, 1, 2, 3, 4, 5}, A={1, 2, 5}, B={2,4} 定理1.2.1 设A，B和C为任意三个集合，则有 i) A ? A∪B且B ? A∪B； ii) A∩B ? A且A∩B ? B； iii) A － B ? A； iv) A