第一章集合映射与运算.pptVIP

离散数学Discrete Mathematics;离散数学是计算机各专业的专业基础课. (1) 程序设计语言 (2) 离散数学 (3) 数据结构与算法 (4) 计算机组成原理 (5) 计算机网络 (6) 操作系统 (7) 数据库 (8) 软件工程;离散数学研究的对象: 离散量及其之间的关系. 离散量与连续量及其之间的转换. 现今计算机的处理对象是非常特殊的离散量: 0和1. 学习离散数学的目的: 1.培养各种能力. 2.为后继专业课程的学习作知识上的准备. ;离散数学的主要内容: 1. 集合与关系 Chapter 1 集合、映射与运算 Chapter 2 关系 2. 数理逻辑 Chapter 3 命题逻辑 Chapter 4 谓词逻辑 3. 代数结构(Chapter 5) 4. 图论 Chapter 6 图论 Chapter 7 几类特殊的图 5. 组合计数(Chapter 8);学习离散数学的方法: 1.预习. 2.听课. 3.复习. 4. (分组)作业. ;参考文献: 屈婉玲,耿素云, 张立昂, 离散数学, 高等教育出版社, 2007. (108—144学时) 傅彦, 顾小丰, 王庆先, 离散数学及其应用, 高等教育出版社, 2008. (两个学期) ;Chapter 1 Sets, Mappings and Operations;1.1 集合的有关概念;若x是集合A中元素,则记x?A, 否则x?A. Fuzzy set ? 集合通常用大写字母A, B, C, D,…表示. N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合. ;P : 2, 3, 5, 7, 11, 13, 17, 19, 23等. (1) m|n: n = mq. (2) Dn. (3) 素数测试与Mersenne素数: 2p - 1.;表示集合的常用方法: (1)列举法:{0, 2, 4, 6, 8}, N = {0, 1, 2, 3, …}. (2)描述法:{x|x满足的条件}. 可简记: {直角三角形}, {所有人} (3)递归法 自然数集合N可递归定义, 在后面章节定义命题公式及谓词公式时还会用此法. 有限集合A的元素个数|A|, card(A).;Remarks 1.集合中的元素可以是集合, 例如A = {a, {a, b}, b, c}. {a, b}?A, {a, b}?A. 2.集合之间的元素原则上是没有次序的, 如 A = {a, {a, b}, b, c}就是 {a, b, c , {a, b}}; 3.集合中的元素原则上不重复, 如{a, {a, b}, b, b, c}还是集合A. 不含有任意元素的集合称为空集(empty set), 记为?或{ }. ;2.子集 A ? B, 特别地?是任意集合的子集. A = B. Theorem 1-2(P3) (1) A ? A. (2) A ? B, B ? A ? A = B. (3) A ? B, B ? C ? A ? C. Theorem 1-3 A = B ? A ? B 且 B ? A.;注意 ?与 ? 的不同. 例1-2 由A ? B, B??? C可否得出A ? C? Solution 不成立,例如A = {a, b}, B = {a, b, c}, C = {a, {a, b, c}}. 课堂练习: 4, 5. ;3. 幂集(power set) X = {a, b} ? P(X) = {?, {a}, {b}, {a, b}}. P(P(?)) = P({?}) = {?, {?}}(P5, 6(1)). ?, {?}, {{?}}(P5, 2) ;Theorem 1-4 Proof(加法原理) 由乘法原理证明?;4.n元组 Def 1-4 将n个元素(?)x1, x2,…, xn按一定顺序排列就得到一个n元(有序)组(n-tuple). 线性代数中的n维向量(?): n = 2, n = 3(see below); n = 2: (x, y). n = 3: (x, y, z) 4元组? 显然, 一般说来(x, y) ? (y, x). 注意区别(a, b, c), ((a, b), c), (a, (b, c))的不同.;n维向量是n元组, 长度为n的线性表是n元组, 抽象数据结构Data_Structure = (D, S) 本身是一个2 元组. 2元组常称为有序对(ordered pair)或序偶. 5.笛卡儿积(cross product) ;例1-4(P4) 设A = {a, b}, B = {1, 2}, C = {?}, 求A ? B, B ? A,