教师介绍教师 : 吴永辉博士副教授简历 : 上海科技大学计算机系本科复旦大学计算机系硕士华东师范大学计算机系工作复旦大

Size: px

Start display at page:

Download "教师介绍教师 : 吴永辉博士副教授简历 : 1984-1988 上海科技大学计算机系本科 1988-1991 复旦大学计算机系硕士 1991-2003 华东师范大学计算机系工作 1998-2001 复旦大"

皇频
7 years ago
Views:

1 离散数学教程 ( 集合论与图论 ) 离散数学 : 计算机科学与技术的数学基础课内容 : 集合论, 图论, 组合数学, 代数结构, 数理逻辑集合论 :( 第 1-4 章 ) 组合数学初步 :( 第 5-7 章 ) 图论 :( 第 8-11 章 )

2 教师介绍教师 : 吴永辉博士副教授简历 : 上海科技大学计算机系本科复旦大学计算机系硕士华东师范大学计算机系工作复旦大学计算机系博士复旦大学计算机系工作答疑 yhwu@fudan.edu.cn

3 集合论与图论课件制作软件 Microsoft PowerPoint MathType Equation

4 集合论与图论课程大纲课程性质与目的教学内容与要求使用教材参考书籍命题说明和题型

5 课程性质目的与基本要求课程性质本课程讲授计算机科学与技术的数学基础课离散数学的部分主要内容 : 集合论图论与组合数学初步, 是计算机专业的主干课程之一本课程前行课程为线性代数, 数学分析 ( 上 ) 课程目的使学生掌握集合论图论与组合数学初步的基本内容, 并对证明的思想和方法深入理解和体会, 初步培养学生的思维过程的数学化

6 基本要求 : 掌握集合论组合学和图论的基本概念, 清楚了解引入基本概念的实际背景各概念间相互关系 ; 掌握基本定理以及有关理论题的证明技巧 ; 掌握解决计数问题的基本方法和技巧 ; 掌握图论中各算法设计的思想正确性证明以及算法的应用为进一步学习计算机其他课程打下坚实的基础

7 教学方式本课程以课堂讲授为主

8 考核方式平时作业 ; 集合论组合数学和图论 3 次课堂练习 ; 期中, 期末的两次笔试考试

9 教学内容与要求 ---- 集合论第一章集合的基本概念掌握 : 集合的基本概念, 集合的运算了解 : 集合论的悖论掌握证明两个集合相等的基本法和公式法第二章关系掌握 : 关系的性质运算和关系的闭包, 以及等价关系和偏序关系了解 : 关系在关系数据库中的应用掌握证明的类型

10 第三章函数掌握 : 函数的基本概念, 复合函数和逆函数了解 : 集合的特征函数第四章无限集掌握 : 基数及基数的比较, 判断可列集与不可列集的方法了解 : 集合的递归定义

11 教学内容与要求 ---- 组合数学初步第五章鸽笼原理掌握 : 利用鸽笼原理解决组合数学中一些存在性问题的技巧第六章排列与组合掌握 : 集合的排列与组合, 多重集的排列与组合等计数方法, 有序划分和无序划分第七章生成函数与递推关系掌握 : 用生成函数和递推关系解决组合计数问题的方法, 以及求解递推关系的生成函数方法了解 : 求解递推关系的特征根方法

12 教学内容与要求 ---- 图论第八章图的基本概念掌握 : 图的基本术语, 路回路和连通的基本概念, 求最短路的算法及算法正确性证明, 欧拉图和哈密顿图的基本概念判别方法以及有关定理第九章平面图与图的着色掌握 : 平面图的基本概念平面图的特征和欧拉公式, 掌握图的点着色和平面图的面着色概念了解 : 图的边着色概念树掌握 : 树的基本性质和生成树割集有根树的概念, 求最小生成树和最优树的算法及算法的正确性证明了第十章解 : 树的计数问题

本概念平面图的特征和欧拉公式, 掌握图的点着色和平面图的面着色概念了解 : 图的边着色概念树掌握 : 树的基本

13 教学内容与要求 ---- 图论第十一章连通度网络与匹配教学时间 :10 学时 ; 掌握 : 点连通度和边连通度的基本概念, 掌握最大网络流算法及算法正确性证明, 掌握匹配的基本概念和判别方法, 掌握独立集和覆盖的基本概念和有关定理及证明方法了解 : 佩特里网及其图的表示

14 使用教材离散数学, 赵一鸣, 阚海斌, 吴永辉编著人民邮电出版社,2011

15 参考书籍一基础 [1] Bernard Kolman, etc.. Discrete Mathematical Structure, Third Edition 清华大学出版社, Prentice Hall. ( 中英文版 ) [2] 左孝凌, 李为槛, 刘永才. 离散数学理论分析题解 1988, 上海科技文献出版社 [3] 左孝凌, 李为槛, 刘永才. 离散数学 1988, 上海科技文献出版社

16 二提高 [4] Kenneth H. Rosen. Discrete Mathematics and its Applications. (4th, 5th Edition). 机械工业出版社, McGraw-Hill. ( 中英文版 ) [5] 吴永辉, 王建德数据结构编程实验 : 大学程序设计课程与竞赛训练教材 ( 附光盘 ) 机械工业出版社 2012

17 参考课件 [1] Discrete Mathematics and Its Applications 课件

18 在线学习网站 [1] 北京大学计算机系离散数学教程网上教室 [2] 北京邮电大学离散数学在线课件 [3] 国立交通大学离散数学电脑辅助教学 CAI ( 台湾 ) t/discrete.html

19 在线计算机和数学类书库计算机和数学类书库吉林大学的藏经阁 elmo 站 :

20 理论计算机科学经典网站国内 : 国际 : ory-home.html

21 命题说明和题型 1 填空题 : 基本概念的理解和掌握 2 判断题 : 概念的掌握与应用 3 计算证明题 : 概念的综合应用, 数学方法的运用

22 集合论集合论是现代数学的基础, 它已深入到各种科学和技术领域中, 被广泛应用到数学和计算机科学的各分支中去集合论的创始人 : 康托尔 (Cantor, ), 1874 年, 关于所有实代数数所成集合的一个性质的论文理论中出现了悖论为解决悖论, 在 20 世纪初开始了集合论公理学方向的研究, 它是数理逻辑的中心问题之一 ( 本书避免用集合的公理化方法, 直观地介绍朴素集合论 )

23 集合论部分提高参考书籍沈恩绍集论与逻辑 ---- 面向计算机科学科学出版社集合论部分内容与常规教材相似, 强调公理化

24 图论图论提供了一个自然的结构, 由此产生的数学模型几乎适合于所有科学 ( 自然科学与社会科学 ) 领域, 只要这个领域研究的主题是对象与对象之间的关系

25 图论部分提高参考书籍 Bela Bollobas. Modern Graph Theory ( 现代图论 ). 科学出版社 & Springer

26 组合数学 1666 年莱布尼兹所著组合学论文一书问世, 这是组合数学的第一部专著书中首次使用了组合论 (Combinatorics) 一词组合数学的蓬勃发展则是在计算机问世和普遍应用之后由于组合数学涉及面广, 内容庞杂, 并且仍在很快地发展着, 因而还没有一个统一而有效的理论体系这与数学分析形成了对照

27 组合数学部分提高参考书籍 Richard A.Brualdi. Introductory Combinatorics (3E),( 组合数学 ( 第 3 版 ), ( 冯舜玺等译 )), 机械工业出版社, 2002.

28 第一章集合的基本概念 1.1 集合的表示 1.2 集合的子集 1.3 笛卡尔积 1.4 集合的运算 1.5 罗素悖论

29 引言 : 什么是集合? 一些自行车在计算机系车棚内的自行车

30 一些自行车不是集合, 无法确定范围和性质在计算机系车棚内的自行车是集合, 可以确定范围和性质

31 1.1 集合的表示一集合的定义 <1> 集合 : 具有共同性质的一些东西汇集成一个整体例 : 复旦大学教师 <2> 元素 : 构成一个集合中的那些对象 a A a 是 A 的元素,a 属于 A a A a 不是 A 的元素,a 不属于 A 例 : 吴永辉复旦大学教师, 沈恩绍复旦大学教师常用大写字母表示集合, 小写字母或数字表示元素

32 1.1 集合的表示二集合的表示 <1> 列出集合中的元素 :A={1,3,5,7,9} <2> 描述集合中元素具有的共同性质 2 { x p(x) }: A { x x 1 0} <3> 通过某规则的计算来定义集合中的元素

33 1.1 集合的表示三术语 <1> 空集 : 不含任何元素的集合, 记为 <2> 有 / 无限集 : 集合中有有限个元素 / 否则.. 有限集 A 的元素个数称为集合 A 的基数, 记为 A 集合中元素之间的次序是无关紧要的 <3> 多重集 : 集合中元素可以重复出现 <4> 集合族 : 以集合为元素组成的集合 <5> 与 { } 是不同的 : { } 表示以为元素的集合

34 例 : 设 A, B, C 是任意 3 个集合, 如果 A B, B C, 则 A C 可能吗? A C 常真吗? 举例说明 /* 集合论题集, 经典习题, 集合基础 */

35 1.2 集合的子集一文氏图 : 用平面上封闭曲线包围点集的图形来表示集合图 1.1, 图 1. 2

36 二定义 1.1( 子集 ) 集合 A, B,A 的每一元素都是 B 的元素, 则 A 是 B 的子集 A B 或 B A 特别 :A A 此外, 若存在元素 a A, 但 a B, 则 A 不是 B 的子集.

37 三定义 1.2( 集合相等与不相等 ): 集合 A 和 B 的元素全相同, 则称 A 和 B 相等,A=B; 否则称 A 和 B 不相等,A B

38 定理 1.1 A=B A B 并且 B A

39 1.2 集合的子集证明的方法定理 1.1: A=B A B 并且 B A 当且仅当 : 证明由两部分组成 : 1) 由条件证明结论 A=B A B 并且 B A 2) 由结论证明条件 A B 并且 B A A=B

40 证明 : A=B A B 并且 B A 因为 A=B, 由定义 A 中的每个元素是在 B 中, 所以 A B, 同理 B 中的每个元素是在 A 中, 所以 B A A B 并且 B A A=B 反证, 如果 A B, 则 A 中至少有一个元素不在 B 中, 与 A B 矛盾 ; 或者 B 中至少有一个元素不在 A 中, 与 B A 矛盾所以 A B 不可能成立所以 A=B

41 四定义 1.3( 真子集 ):A B 并且 A B, 则 A B ( 和不同 : 元素集合 ; 集合集合 )

42 例 : 设 A, B, C 是集合, 判断下列命题真假, 如果为真, 给出证明 ; 如果为假, 给出反例 : 1) A B, B C A C; 2) A B, B C A C; 3) A B, B C A C; 4) A B, B C A C; 5) a A, A B a B. /* 集合论题集, 经典习题, 集合基础 */

43 五定义 1.4( 全集 ): 在取定一个集合 U 以后, 对于 U 的任何子集而言, 称 U 为全集

44 定理 1.2: (1) A (2) A A (3) A U

45 1.2 集合的子集证明的方法证明 :(1) A (2) A A (3) A U (1) 反证法 : 假设结论不成立, 导出矛盾结果不是 A 的子集, 导致矛盾 (2,3) 基本法 : 由子集定义 x 左 x 右, 则左右

46 证明 :(1) A 假设不是 A 的子集, 则至少有一个元素 x, 使得 x 且 x A 又因为是空集, 它没有元素, 所以对任何 x, 必有 x, 导致矛盾因此是集合 A 的子集

47 反证法的证明步骤 (1) 假设命题的结论不成立 ; (2) 进行一系列的推理 ; (3) 推理过程中出现下列情况中的一种 : 1) 与已知条件矛盾 ; 2) 与公理矛盾 ; 3) 与已知定理矛盾 ; (4) 由于上述矛盾的出现, 可以断言, 原来的假定结论不成立是错误的 (5) 肯定原来命题是正确的

48 反证法的思想 / 思维过程结论不成立与结论成立必有一个正确结论不成立会导致出现错误, 推理过程已知条件公理和已知定理没有错误, 惟一有错误的是一开始接假定的结论不成立, 所以结论不可能不成立, 即结论成立

49 1.2 集合的子集六定义 1.5( 幂集 ): A 的所有子集组成的集合称为 A 的幂集记为 P(A) 例 1.1( 已知 A, 求幂集 ) 定理 1.3 P(A) =2 A 证明方法 : 组合的方法

50 求幂集代数法 P13 习题 1.13 设 A={a, {a}}, 问 : (1) {a} P(A)? {a} P(A)? (2) {{a}} P(A)? {{a}} P(A)? (3) 又设 A={a, {b}}, 重复 (1) (2) 解 : (1, 2) 首先求 P(A), 代数法 : 代入 : 设 x={a}, 则 A={a, x}; P(A)={, {a}, {x}, {a, x}}; 回代 : P(A)={, {a}, {{a}}, {a, {a}}}

51 P(A)={, {a}, {{a}}, {a, {a}}} (1) {a} P(A) {a} P(A) (2) {{a}} P(A) {{a}} P(A) (3) 同理, 用代入法, 设 x={b}, 则 A={a, x}; 回代 : P(A)={, {a}, {{b} }, {a, {b}}}, 则 {a} P(A),{a} P(A), {{a}} P(A),{{a}} P(A)

52 1.3 笛卡尔积一定义 1.6( 有序对 ) 两个对象按一定次序组成一对, 称为有序对 (a, b) (a, b)=(c, d) a=c 和 b=d

53 二定义 1.7( 有序 n 元组 ) n 个对象的序列 a 1, a 2,,a n 组成一组称为有序 n 元组, 记为 (a 1, a 2,,a n ), 其中 a i 称为第 i 个分量两个有序 n 元组相等每个对应分量相等

54 1.3 笛卡尔积三定义 1.8( 直积 ) 两个集合 A 和 B, 定义 A 和 B 的笛卡尔积为 A B={(a, b) a A, b B}, 又称 A B 为 A 和 B 的直积

55 1.3 笛卡尔积四定义 1.9( 笛卡尔积 ) n 个集合 A 1, A 2,, A n, A 1 A 2 A n ={(a 1, a 2,,a n ) a i A i, i=1,, n} 若对所有 i,a i =A, 则 A 1 A 2 A n 记为 A n

56 1.4 集合的运算一定义 1.10 ( 并, 交, 差, 补, 对称差 ) (1) A B={x x A 或 x B} (2) A B={x x A 且 x B} (3) A-B={x x A 且 x B} (4) Ã=U-A (5) A B=(A-B) (B-A)

57 例集合运算 :A={1,2,3,4,5}, B={1,2,4,6}, C={7,8}, U={1,2,3,4,5,6, 7,8,9,10} A B={1,2,3,4,5,6}, A B={1,2,4}, A C=, A-B={3,5}, A-C=A

58 A { 6,7,8,9,10}, B {3,5,7,8,9,10}

59 1.4 集合的运算证明两个集合相等, 可用如下办法 : <1> 基本法集合相等的充要条件是两个集合互为子集 ; 即, 左式右式, 右式左式所以证明 : x 左式 x 右式 ;x 右式 x 左式经典实例 : 例 1.4, 例 1.5, 例 1.6 证明理论基础 : 定理 1.1 和定义 1.1, 1.2 <2> 公式法由集合运算的基本性质, 通过推演, 进行证明经典实例 : 例 1.7, 例 1.8 证明理论基础 : 定理 1.4 和定义 1.10

60 基本法例 1.4 A (B C)=(A B) (A C) 证明 : 1)A (B C) (A B) (A C) 任一 x A (B C) x (A B) (A C) 2)(A B) (A C) A (B C) 任一 x (A B) (A C) x A (B C)

61 基本法例 1.5 若 A B, 则 (A B)=A, A B=B. 证明 : 1) 证 (A B)=A 思想 : (A B) A; A (A B) 2) 证 A B=B 思想 : A B B; B A B

62 例 1.6 证明 : B A B A B A B A : 首先证明 B, A x 有, B A x 对, B x A x 或故 B, x A x 或即 A B A B 因此有 B A x 因此有 B A B A 然后证明 : B, x A x 或有, B A x 对, B x A x 或故 B A x 即, B A x 因此有 B A B A 所以 B A B A

63 1.4 集合的运算三定理 1.4 ( 集合运算的基本性质 ) (1) 幂等律 A A=A A A=A (2) 交换律 A B=B A A B=B A (3) 结合律 A (B C)=(A B) C A (B C)=(A B) C (4) 分配律 A (B C)=(A B) (A C) A (B C)=(A B) (A C)

64 1.4 集合的运算 (5) 恒等律 A U=U A U=A A =A A = (6) 取补律 U U A A U A A

65 1.4 集合的运算 (7) 双重补 A A

66 1.4 集合的运算 (8) 狄摩根律 A B A B A B A B

67 证明类似于例 1.4, 例 1.5, 例 1.6 证明

68 判断题, 为真给出证明, 为假给出反例 : 若 A B=A C, 则 B=C /* 北京大学 1994 考研 */

69 解 : 错误如果 A 为空集, 则有 A B=A C, 即使 B C, 原式成立

70 公式法原则 : 1) 根据集合运算的定义, 将集合运算表达式中 - 和转换为和 ; A B A B ; A B ( A B ) ( B A ) 2) 将补运算作用到单一集合上 ; 3) 左式右式 ; 右式左式 ; 左式中间式, 右式中间式 ; 4) 根据定义 1.10 和定理 1.4 转换

71 例 :(A B)-C=(A-C) (B-C) C B A C B A ) ( ) ( : 证明左 ) )( ) ( ) ( 分配律 C B C A ) ( ) ( C B C A

72 例 1.7 证明 (A B)-(A C)=A (B-C) 证明思想 : 将集合运算表达式中 - 转换

73 例 1.8 证明 A B=(A B)-(A B) 证明思想 : 将集合运算表达式中 - 和转换

74 P( { })=. /* 北京理工大学 1999 考研 */

75 判断题, 为真给出证明, 为假给出反例 : (1){ } {x}-{{x}} (2)(A B) C= (A C) (B C) /*(1) 北京大学 1994 考研, (2) 上海交通大学 2001 考研 */

76 解 : 错误 {x}-{{x}}={x} 显然,{ } {x} 不成立

77 幂集证明基本法幂集的定义证明 :P(A) P(B) P(A B), 并说明等号成立的条件 /* 上海交通大学 1999 考研 */

78 判断下式是否成立, 如果成立, 则证明 ; 否则举出反例 P(A) P(B)=P(A B) /* 上海交通大学 2001 考研 */

79 1.4 集合的运算四定义 1.11 ( 多个集合的并和交 ) 设集合 A 1,, A n, 定义 : A 1 A n ={ x 至少有某个 i,1 i n, x A i }, 称为 A 1,, A n 的并 ; A 1 A n ={ x x A i, 对一切 i=1,,n 成立 }, 称为 A 1,, A n 的交

80 1.4 集合的运算五多个集合的运算, 除对并 ( 交 ) 的结合律交换律成立以外, 还有 (1) 分配律 B (A 1 A 2 A n )=(B A 1 ) (B A 2 ) (B A n ) B (A 1 A 2 A n )= (B A 1 ) (B A 2 ) (B A n ) (2) 狄摩根律 A A n n i 1 i i 1 i A A n n i 1 i i 1 i

81 1.4 集合的运算六广义并广义交 1. 定义 ( 广义并 ) 设 Ǽ 为一个集合族, 称由 Ǽ 中全体元素的元素组成的集合成为的 Ǽ 广义并集, 记作 Ǽ, 称为广义并运算符, 读作大并 Ǽ={x z (z Ǽ 并且 x z)} 例 :Ǽ={{a, b}, {c, d}, {d, e, f}} Ǽ={a, b, c, d, e, f}.

82 1.4 集合的运算 2. 定义 ( 广义交 ) 设 Ǽ 为一个非空集合族, 称由 Ǽ 中全体元素的公共元素组成的集合成为的 Ǽ 广义交集, 记作 Ǽ, 称为广义交运算符, 读作大交 Ǽ={x z ( 如果 z Ǽ, 则 x z)} 例 : 设 Ǽ={{1, 2, 3}, {1, a, b}, {1, 6, 7}} Ǽ={1}

83 3. 在广义并与广义交的运算中, 集合族中的元素仍看成集合族例, 给出下列集合族 : Ǽ 1 ={a, b, {c, d}}, Ǽ 2 ={{a, b}}, Ǽ 3 ={a}, Ǽ 4 ={, { }}, Ǽ 5 =a (a ), Ǽ 6 = Ǽ 1 =a b {c, d}, Ǽ 1 =a b {c, d}, Ǽ 2 ={a, b}, Ǽ 2 ={a, b}, Ǽ 3 =a, Ǽ 3 =a, Ǽ 4 ={ }, Ǽ 4 =, Ǽ 5 = a, Ǽ 5 = a, Ǽ 6 =, Ǽ 6 无意义.

84 设, 为集合族, 试证明 : (1) 若, 则 ; (2) 若, 则 ; (3) 若, 且, 则 ; (4) 若, 则 ; (5) 若, 则.

85 证明 : (1) 对于任意的 x, x, 则存在 A, A 并且 x A, 所以 A, 则 x. 所以. /* 证明方法 : 基本法 */

86 (2) 因为, 由广义并集定义,.

87 (3) 由于, 所以, 故与均有意义. 对于任意的 x, x 当且仅当对于任意的 y, 如果 y, 则 x y. 所以, 如果 y, 则 x y. 所以 x. 所以.

88 (4), (5) 的证明比较简单, 请自行完成.

89 1.5 罗素悖论命题 : 能区别真假的陈述语句例 : 我是学生今天不下雨上述两个都是命题因为它们都能判别真假例 : 祝你一帆风顺! 你明天下午出去吗? 上述两个都不是命题

90 1.5 罗素悖论一悖论一个命题 Q, 如果从 Q 为真, 可以推导出 Q 为假 ; 又从 Q 为非真推导出 Q 为真, 命题 Q 是一个悖论

91 二说谎悖论和理发师悖论 1, 说谎悖论我正在说谎我们要问 : 这个人是在说谎还是在讲真话?

92 如果他在说谎, 这表明他的断言我正在说谎是谎话, 也就是说他在讲真话即他说谎, 推出他是讲真话 ( 即没有说谎 ) 另一方面, 如果他讲真话, 这表明他的断言我正在说谎是真话, 也就是说他正说谎话, 即他讲真话, 推出他在说谎 ( 即没有讲真话 ) 通过以上分析让我们看到, 以命题出现的断言我正在说谎就是一个悖论, 因为我们无法断言它的真伪

93 2 理发师悖论一个村上, 有一个理发师宣布他给而且只给所有自己不替自己理发的人理发现在要问 : 谁给这个理发师理发?

94 如果理发师的头由别人给他理, 也就是说理发师自己不替自己理发, 那么按照规定, 这位理发师应该给自己理发另一方面, 如果理发师的头由自己理, 那么按照规定, 理发师不能给自己理发因此上述也是一个悖论 : 理发师的头由别人来理, 不行 ; 理发师的头由自己理, 也不行

95 理发师悖论的数学化表示 : 设 S={ 自己给自己理发的人 } 若理发师 S, 即理发师是自己给自己理发的人, 但由理发师所宣布的, 他不该给自己理发, 则理发师 S; 若理发师 S, 即理发师不是自己给自己理发的人, 但由理发师所宣布的, 他应该给自己理发, 则理发师 S;

96 罗素将理发师悖论表示为数学悖论罗素将理发师悖论表示为数学悖论 : 设 S={ 集合 A A A}, 问 S S 还是 S S? 显然 S

97 3 悖论欣赏古希腊哲学问题 : 鳄鱼两难中国民间故事 : 师徒打官司柏拉图与苏格拉底悖论

98 古希腊哲学问题 : 鳄鱼两难一条鳄鱼从一位母亲手中抢走了一个小孩鳄鱼对孩子的母亲说 : 请你回答, 我会不会吃掉你的孩子, 答对了, 我就把孩子不加伤害地还给你 ; 否则, 就别怪我不客气了! 孩子的母亲回答 : 你是要吃掉我的孩子的鳄鱼是否将孩子还给母亲?

99 中国民间故事 : 师徒打官司一位律师收徒弟, 协议规定 : 学成之后, 打赢一场官司交给律师一两银子, 打输一场官司就不交弟子满师后, 打赢官司却一直不交钱给老律师, 老律师告到县衙, 和弟子打官司这场官司该如何裁决?

100 柏拉图与苏格拉底悖论柏拉图说 : 苏格拉底老师下面的话是假话苏格拉底说 : 柏拉图上面的话是对的柏拉图苏格拉底二人的话是真话还是假话?

101 4 何谓集合? 1897 年, 康托尔 : 一个集合就是指我们观察到的或者在我们思维中的一些确定的不同事物的总体 ; 这些事物称为该集合的元素

102 1) 某些集合是集合自身的元素如 : 所有不是苹果的东西的集合 /* 它本身就不是苹果, 它必须是此集合自身的元素 */ 2) 问题 : 一个由一切不是集合本身的元素组成的集合, 这个集合是它本身的元素吗?

103 1.5 罗素悖论三罗素悖论 1) 罗素将集合分成两类 : 一类是集合 A 本身是 A 的一个元素, 即 A A; 如上例 ; 另一类是集合 A 本身不是 A 的一个元素, 即 A A; 例如 26 个英语字母组成的集合 A, 由于 A 本身不是一个字母, 所以 A A

104 2) 构造一个集合 S:S={A A A}}, 即,S 是由满足条件 A A 的那些 A 组成的一个新的集合问 : S 是不是它自己的一个元素? 即 S S, 还是 S S?

105 分析 : 如果 S S, 因为集合 S 由所有满足条件 A A 的集合组成, 由于 S S, 所以 S 满足对于集合 S 中元素的定义, 即 S 是集合 S 的元素, 也就是说 S S 如果 S S, 因为 S 中任一元素 A 都有 A A, 又由于 S S, 根据集合 S 的规定, 知 S 不是集合 S 的元素, 也就是说 S S

106 2) 罗素悖论既不是 S S, 也不是 S S

107 罗素悖论的出现, 说明朴素集合论有问题, 从而使数学的基础发生了动摇 ( 第 3 次数学危机 ), 引起了一些著名数学家的极大重视

108 在现代数学中为了防止这类悖论的出现, 产生各种公理化的集合论和不同的学派 : 1) 蔡梅罗 (Zermelo) 创立集合论的一个公理系统 ; 经过费兰克尔 (A. Fraenkel) 改进, 形成著名的 ZF 系统 ; 2) 罗素也发表了他的集合论公理系统类型论 ; 3) 以后,John von Nenmann, P. Bernays, Godel 等相继建立了其他类型的公理系统 ;

109 沈恩绍集论与逻辑科学出版社

110 经典例题之一集合运算 1. 某学院学生选课情况如下 :260 人选艺术课,208 人选生物课,160 选计算机课,76 人选艺术与生物课,48 人选艺术与计算机课,62 人选生物与计算机课,30 人三门全选,150 人三门都不选问 1) 共有多少名学生? 2) 有多少学生选艺术与生物课, 但不选计算机课? 3) 有多少学生选艺术与计算机课, 但不选生物课?

111 经典例题之一集合运算 4) 有多少学生选生物与计算机课, 但不选艺术课? 5) 有多少学生选艺术课, 但不选生物或计算机课? 6) 有多少学生选生物课, 但不选艺术或计算机课? 7) 有多少学生选计算机课, 但不选艺术或生物课?

112 集合运算解题思想容斥原理 : 1) 设 A 1, A 2 为有限集, 则 A 1 A 2 = A 1 + A 2 - A 1 A 2 2) 设 A 1, A 2,,A n 为有限集, 则 A A... A A A A A A A 1 2 n 1... ( 1) A A A n n i i j i j k i 1 i, j i, j, k n

113 3) 设 U 为全集,A 1, A 2,,A n 为 U 的有限子集, 则 A A... A 1 2 U A A... A 1 2 n n

114 集合运算解题思想容斥原理 ( 包含排斥 ) 应用 1) 讨论的范围是什么? 即那些是全集中的元素?---- 某学院的学生全体构成全集 ; 2) 将全集中的元素进行分类 ---- 按学生选课的情况进行分类 : 选修艺术课为具有性质 P A, 选修生物课为具有性质 P B, 选修计算机课为具有性质 P C, 具有上述性质的集合记为 A, B, C; 3) 列出计算公式 ; 4) 用文氏图辅助运算

115 求解 ---- 按题意给出已知条件解 : 设 A={ 选修艺术课学生 },B={ 选修生物课学生 },C={ 选修计算机课学生 } 则 A =260, B =208, C =160, A B =76, A C =48, B C =62, A B C =30, A B C 150

116 求解 ----a) 学生总数 N A B C A B C A B C A B A C B C A B C A B C

117 求解 ---- 答案答案 a) 622 b) 46 c) 18 d) 32 e) 166 f) 100 g) 80

118 2. 求 1 到 250 这 250 个整数中, 至少能被 2,3,5 之一整除的数的个数

119 解 : 设 A, B, C 表示 1 到 250 这 250 个整数中, 能分别被 2,3,5 整除的数的集合则有 : A =125, B =83, C =50 A B =41, A C =25, B C =16, A B C =8, 那么, A B C = A + B + C - A B - A C - B C + A B C =184

120 3. 75 名儿童到游乐场去玩他们可以骑旋转木马, 坐滑行铁道, 乘宇宙飞船已知其中 20 人这 3 种东西都玩过, 其中 55 人至少乘坐过其中的两种若每样乘坐一次的费用是 0.5 元, 游乐场总共收入 70 元, 试用容斥原理确定, 在 75 名儿童中有多少儿童没有乘坐其中任何一种

121 经典例题之二证明方法反证法引用已知的结论来简化证明步骤证明两个集合相等常用的方法

122 证明方法 1 1) 反证法设 A 为一个集合,B 为 A 的补集合, 则 A B= 证明 : 设 A B, 则存在非空元素 x A B, 故 x A 且 x B, 此与 B 为 A 的补集合矛盾所以 A B=

123 证明方法 2 2) 引用已知的结论来简化证明步骤对任意的集合 A, A 证明 : 反证法, 假设存在一个集合 A, 使得 A 即存在元素 x, 但 x A 这与是空集矛盾空集合是唯一的证明 : 设 1 和 2 都是空集合, 由上题, 1 2 且 2 1, 则 1 = 2

124 证明方法 3 3) 证明两个集合相等常用的方法基本法, 公式法习题 1.3 基本法习题 1.11 公式法

125 证明方法练习 1) 设 A 为一个集合,B 为 A 的补集, 则 A B= 证明 : 反证法设 A B, 则存在 x A B, 所以 x A, 并且 x B, 矛盾

126 证明方法练习 2) 证明 A B=B A 证明 : 分两部分证明首先证明左式是右式的子集, 然后证明右式是左式的子集若两个集合互为子集时, 必然相等设任意 x A B x A 或者 x B x B A 设任意 x B A x A 或者 x B x A B

127 经典例题之三是非判断判断命题是否正确, 并说明理由习题 1.4, 1.9.

128 习题 1.4 (1) A B, C D, (A C) (B D), 基本法证明 ; (A C) (B D), 基本法证明 ; (2) W X, Y Z, (W Y) (X Z), 反例 :W={1, 2}, Y={1, 3}, X={1, 2, 3}, Z={1, 3, 2}; 则 (W Y)={1, 2, 3}, (X Z)={1, 2, 3}; (W Y) (X Z), 反例 :W={1, 2}, Y={1, 3}, X={1, 2, 4}, Z={1, 3, 5}; 则 (W Y)={1}, (X Z)={1}

129 学生练习习题 1.9

130 经典例题之四幂集习题 1.12 代数法设 A={ }, B=P(P(A)), 问 : (1) B? B? (2){ } B? { } B? (3){{ }} B? {{ }} B? /* 重庆大学 1998 研究生入学考试试题 */

131 解 : 设 x=, 则 P(A)={, {x}}={, { }}; 设 x=, y={ }, 则 P(A)={x, y}; 所以,P(P(A))={, {x}, {y}, {x, y}}; 回代,P(P(A))={, { }, {{ }}, {, { }}}.

132 B=P(P(A))={, { }, {{ }}, {, { }}}. (1) B, B; (2) { } B, { } B; (3) {{ }} B, {{ }} B.

133 例 : 设 A 和 B 为两个集合, 则 P(A) P(B)=P(A B) 证明思想 : 幂集定义和基本法

134 证明 : 先证 P(A) P(B) P(A B); 对任意 X P(A) P(B), 有 X P(A) 且 X P(B), 所以 X A 且 X B, 即 X A B, 因此 X P(A B); 所以 P(A) P(B) P(A B); 再证 P(A B) P(A) P(B); 对任意 X P(A B), 有 X A B, 即 X A 且 X B, 所以 X P(A) 且 X P(B), 因此 X P(A) P(B); 所以 P(A B) P(A) P(B) 所以,P(A) P(B)=P(A B)

135 思考练习题幂集性质的证明 1. 对于任意的集合 A 和 B, (1) A B P(A) P(B). (2) A=B P(A)=P(B). /* 幂集定义和基本法 */

136 2. 对于任意的集合 A 和 B, P(A) P(B) A B.

137 3. 对于任意的集合 A 和 B, (1) P(A) P(B)= P(A B) (2) P(A) P(B) P(A B)

138 4. 对于任意的集合 A 和 B, P(A-B) (P(A)- P(B)) { }.

139 作业习题 1.1, 1.2, 1.3, 1.4, 1.7, 1.9(1),(3),(5), 1.11(1),(2), 1.12, 1.13

140

Ps22Pdf

Ps22Pdf A B C D A B C D A B C D a a b c x x x x x x x x x x x x x x x x x a b c x a x x x x x x x x x x a b a b a b x x x x x x x x x x x x A B C A B C A B A B A x B C x D A B C a b c a b x x x x x x x A B A

教 师 介 绍 教 师 : 吴 永 辉 博 士 副 教 授 简 历 : 上 海 科 技 大 学 计 算 机 系 本 科 复 旦 大 学 计 算 机 系 硕 士 华 东 师 范 大 学 计 算 机 系 工 作 复 旦 大

教师介绍教师 : 吴永辉博士副教授简历 : 上海科技大学计算机系本科复旦大学计算机系硕士华东师范大学计算机系工作复旦大