《第1章集合、映射与运算.ppt》由会员分享，可在线阅读，更多相关《第1章集合、映射与运算.ppt（87页珍藏版）》请在三一文库上搜索。
1、离散数学 Discrete Mathematics,邓辉文编著 清华大学出版社 2006.10 ISBN 978-7-302-13711-5,离散数学是计算机各专业的专业基础课. 离散数学研究的对象: 离散量及其之间的关系. 离散量与连续量及其之间的转换. 现今计算机的处理对象是非常特殊的离散量: 0和1. 学习离散数学的目的: 1.培养各种能力. 2.为后继专业课程的学习作知识上的准备.,离散数学的基本内容: 1.集合与关系 Chapter 1 集合、映射与运算 Chapter 2 关系 2.数理逻辑 Chapter 3 命题逻辑 Chapter 4 谓词逻辑 3.代数结构 Chapter
2、5 群、环和域 Chapter 6 格与布尔代数 4.图论 Chapter 7 图论 Chapter 8 几类特殊的图,学习离散数学的方法: 1.预习. 2.听课. 3.复习. 4.作业. 参考文献: 耿素云 屈婉玲,离散数学(修订版),高等教育出版社,2004. Kenneth H. Rosen, Discrete Mathematics and Its Applications (Fourth Edition), McGraw-Hill Companies, Inc.1998.(有中译本,2002),Chapter 1 Sets, Mappings and Operations,集合是现代
3、数学的最基本概念(?). 映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义. 运算本质上是映射, 但其研究有其特殊性. 集合、映射、运算及关系(Chapter 2)是贯穿于本书的一条主线.,1.1 集合的有关概念,1. 集合 集合(用处?)已渗透到自然科学以及社会科学的各个研究领域, 在信息的表示及处理中,可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关系. 在一定范围内, 集合(set)是其具有某种特定性质的对象汇集成的一个整体, 其中的每一个对象都称为该集合的元素(element). 这里所指范围是全集U(见图1-1).(避免悖论!) 在数学中常用 表示整体.
4、若x是集合A中元素,则记xA, 否则xA.,常见的数的集合用黑正体字母表示: N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合. 表示集合的常用方法: (1)列举法:0, 2, 4, 6, 8, N = 0, 1, 2, 3, . (2)描述法:x|x满足的条件. (3)递归法 自然数集合N可递归定义, 在后面章节定义命题公式及谓词公式时还会用此法. 有限集合A的元素个数|A|.,Remarks 1.集合中的元素可以是集合, 例如A = a, a, b, b, c. a, bA, a, bA. 2.集合之间的元素原则上是没有次序的, 如 A = a, a, b
5、, 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,
6、 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 = 2: (x, y). n = 3: (x, y, z) 4元组? 显然, 一般说来(x, y) (y, x). 注意区别(a, b, c), (a, b), c), (a,
7、(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 = , 求AB, BA, BC, ABC. Solution BC = (1, ), (2, ) AB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ).,Remark A = A = . P5, 10? Theorem Hint 可推广到更多个集
8、合的笛卡儿积的情形: 作业 习题1.1 6, 9, 10.,1.2 映射的有关概念,1.映射的定义 映射mapping=函数function. C语言是一种函数型语言: 从main开始. Def,A,B,函数的表示: (1)解析式 (2)图形 (3)表格(数值计算中出现较多) 函数符号的选取(P6):f, g, F,G, , sin, exp, main, add, average, 注意区别函数f与函数表达式f(x). 映射的两个特点: (1)全函数; (2)唯一性.,B上A: 例1-5 Theorem 1-6 注意B上A的记号与该结论的关系.,x1 x2 x3,y1 y2,像与原像,X,f
9、(X),Y,f-1(Y),n元函数(n 1): float average(float array, int n),2.映射的性质 (1)单射(injection),(2)满射(surjection) 例1-7 是Z到N的满射, 但不是Z到Z的满射(?).,(3)双射(bijection, one-to-one correspondence) 双射又称为一一对应:既单又满. 例1-8 例1-9(P8),例1-10 Def 1-11 有限集合A上自身的双射称为A上的置换(permutation). A = 1, 2, 3, 4上的所有置换有多少个? 4!,1 2 3,1 2 3,3. 逆映射 设
10、f: AB, 将对应关系f逆转(改变方向), 一般来说, 不能得到B到A的映射:,a b c,1 2 3,Def 1-12 设f: AB, 若将对应关系f逆转后能得出一个得到B到A的映射, 则称该映射为f的逆映射(invertible function), 记为f-1.,a b c,1 2 3,Theorem 1-7 f 的逆映射存在的充要条件是f是双射. 对于y = sin x, 当 时, 有反函数, 常记为 当 时, y = sin x仍有反函数, 但不能 记为arcsin. 显然, 当 时, 无反函数.,4. 复合映射(composition function) Theorem1-8 设
11、f: A B, g: B C: 则h: A C.,x,y=f(x),z=g(y)= g(f(x),Def 1-13 例1-12,a b c,1 2 3, ,Remarks (1) y = sin u, u = x2 未引入运算符号,有时是不方便的. (2)顺序问题: 有些专业书 但会出现一些混乱.,例1-13(P9) f: RR, f(x) = x2, g: RR, g(x) = x + 2, 求fg和gf. Solution x R: (fg)(x) = g(f(x) = g(x2) = x2 + 2. (gf)(x) = f(g(x) = f(x+2) = (x+2)2. Remark f
12、g gf.,IA: A A Theorem 1-9 理解:,a b c,1 2 3,a b c,1 2 3,a b c,1 2 3,Theorem 1-10 (1)若f和g是单射, 则fg是单射. (2)若f和g是满射, 则fg是满射. (3)若f和g是双射, 则fg是双射. Proof (2)任意z C, 由于g是满射, 存在y B, 使得z = g(y). 又由于f是满射, 存在x A, 使得y = f(x). 于是z = g(y) = g(f(x) = (fg)(x). 故fg是满射(see below).,Theorem 1-11 (1)若fg是单射, 则f是单射, g不一定. (2)
13、若fg是满射, 则g是满射, f 不一定. (3)若fg是双射, 则f是单射且g是满射. Proof (1)任意x1, x2 A, 若f(x1) = f(x2),显然, g(f(x1) = g(f(x2), 即(fg)(x1) = (fg)(x2). 由于fg是单射, 因此 x1 = x2. 故f是单射. g不一定(见上图)?,一般来说fg gf, 但 Theorem 1-12 作业 习题1.2: 3, 4, 7, 8, 12. Hint 7. 使用定理1-10和第3题. 8. 使用第7题结论. 12.使用第7题结论.,1.3 运算的定义及性质,运算是讨论对象之间有何联系的一种方法. 其实，我
14、们已经接触过很多运算,如数之间的加法运算、多项式之间的乘法运算、矩阵的逆运算、向量的线性运算等.在讨论离散数据结构时也会经常遇到各种各样的运算，如在下节即将研究的集合间的运算. 虽然运算本质上是映射，但研究的侧重点不同，在运算中更注重于运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论. 因此，有必要先把运算的一般定义及其性质进行讨论.,1. 运算的定义 (1)定义 A1, A2, An到B的n元运算(n-ary operation): A到B(或A上)的n元运算: A上的n元封闭运算(代数运算):,例1-14 f: Z N, f(x) = |x|. 例1-15 f: Z
15、 N, f(x) = x(mod k), x = qk + r, 0 r k: 8 = 2 3 + 2; -5 = -2 3 + 1. 例1-16 例1-17,(2)运算符号的选取 函数符号f, g, , F, G, ,; 常见运算符号+, , /, ,; 自定义符号 , , (3)运算符号的位置,(4)运算表 A = a, b, c, *: 思考 A上封闭的1元运算, 2元运算和3元运算的个数是多少?,2.运算的性质 (1)对合(involutive)性 Def 设*是A上的1元代数运算, 例,(2)幂等(idempotent)性 幂等元x: A关于*具有幂等性: A中每个元素对于*都是幂等
16、元. 两个例子:,(3)交换(commutative)性 Def 设*是A上的2元代数运算, 若对于任意的x, y A, 均有 则称*满足交换律. 显然, 映射的复合运算不满足交换律: 加法运算”+”满足交换律, 而减法运算”-”不满足交换律: 2 3 3 2. 如何根据定义的运算得出运算具有交换性?,(4)结合(associative)性 映射的复合运算满足结合律: 加法运算“+”满足结合律, 而减法运算“-”不满足结合律: (2 - 3) - 5 2 - (3 5). 如何根据运算表判断运算是否可(交换)结合?,(5)单位元素. Def 设*是A上的2元代数运算, 若存在e A,对于任意的
17、x A, 下列条件均成立： 则称e为集合A关于*运算的单位元素或幺元素.(幺元律?) 例 Z关于加法运算+的单位元素为0,而Z关于乘法运算“.”的单位元素为1,Z关于减法运算-没有单位元素. 定理：若A关于*运算存在单位元素，则单位元素是唯一的,(6)零元素(zero element). Def 设*是A上的2元代数运算, 若存在 A,对于任意的x A, 下列条件均成立： 则称为集合A关于*运算的零元素.(零元律?) 例1-28 Z关于加法运算+和减法运算-均没有零元素, 而Z关于乘法运算的零元素为0. 定理：若A关于*运算存在零元素，则零元素是唯一的,(7)逆元素(invertible el
18、ement) 若A关于运算*有单位元素e, 则可以讨论A中取定的元素x是否有逆元. Def 设*是A上的2元代数运算且有单位元素e,若对于x A,存在y A,使得下列条件均成立: 则称y为x的关于*的逆元素.,显然,一个方阵关于乘法运算的逆元就是其逆矩阵, 因为单位元素是单位矩阵. 对于函数来说,一个映射关于函数的复合运算的逆元就是其逆映射, 当然只有双射才有逆元,其单位元素是恒等映射. 例1-29 R中各元素关于加法运算+和乘法运算逆元素. 逆元素唯一？,(8)消去(cancellation)性. Def 设*是A上的2元代数运算, 若A关于*运算有零元则记为 , 如果对于任意的x, y ,
19、 z A, 只要x , 那么下列条件均成立： 则称*具有消去性, 或称*满足消去律. 例1-31 Z上的加法运算+和乘法运算均满足消去律. 例1-32 实数集R上的所有2阶方阵组成的集合,关于矩阵乘法运算不满足消去律.,(9)分配(distributive)性. Def 设*和是集合A上的两个2元代数运算,若对于任意x, y , z A, 有 则称*对于是可分配的. 例1-33 实数集合R上的乘法运算对加法运算+可分配,但加法运算+对乘法运算不可分配.,(10)吸收(absorptive)性 Def 设*和是集合A上的两个2元代数运算,若对于任意x, y A, 有 则称*对于是可吸收的. 如果
20、*和是集合A上的两个可交换的2元代数运算,则*运算对运算可吸收只需要满足两条件之一即可,但吸收性本身不需要*和可交换.,(11)德摩根(De Morgan)律 Def 设是集合A上的1元代数运算, *和是A上的两个2元代数运算, 若对于任意x, y A, 均有下面两个等式成立: 则称这三种运算满足德摩根律. 课堂练习 习题1.3 4. 作业 习题1.3 7, 11.,1.4 集合的运算,最常见的集合运算是并、交和补. 1.并(union)运算,Theorem 是包含A和B的最小集合. Theorem1-17 (并运算满足的性质) (1) (2) (3) (4)单位元 (5)零元,例1-38 设
21、f : A B, X, Y A, 则 Proof (1) (2),2. 交(intersection)运算 Theorem 是包含在A和B的最大集合.,Theorem1-19 (交运算满足的性质) (1) (2) (3) (4)单位元 (5)零元 例1-40:举例?,Theorem 1-20(并运算与交运算之间所满足的性质.) (1)吸收性. (2)分配性. 例1-41(P20),3. 补(complement)运算 例1-42 (A的补集依赖于全集U的选取.) A=a, b, c: (1)U = a, b, c, d (2)U = a, b, c, d,a,b,b,c,c,排中律成立: .
22、排中律?,集合的补运算和集合的并交运算满足De Morgan律: 表(P21). (cf. P86 & P182,与布尔代数的性质完全类似?! 因为它们是特殊的, 常见的布尔代数.),4. 差(subtraction)运算 例1-43,Theorem 1-23(P22) Proof 例1-45(P22),例1-46 . 例1-47(P22) Solution 由上例知, A (B C) = ,5. 对称差(symmetric difference)运算 See Venn Figure below. 例1-48,Theorem(对称差运算的性质) (1)交换性: (2)单位元: A = A. (
23、3) A A = . (4)结合性:,例1-49(消去律) Hint,例1-50 A B = A = B. Proof ()显然. () A B = A B = 且B A = 例1-51 ( 对 可分配),思考 还能定义集合的其他运算? 加法原理. 乘法原理. 容斥原理: 容斥原理的另一种形式: 推广到n个集合情形(P24, 15)? 作业 习题1.4 5, 8, 10, 13.,1.5 集合的划分与覆盖,集合的划分与覆盖是集合中的重要内容之一. 集合的划分就是集合元素间的一种分类. 在信息科学中,可以将知识库看作集合的一种划分. 因此, 研究集合的划分具有特别重要的意义. 比集合的划分更广的
24、概念是集合的覆盖. 这些内容在下章会用到. 1. 集合的划分(partition),Def (1) , iI. (2) , i j. (3) Hardware?,例1-53 设A = a, b, c, 则A的所有不同的划分分别为:,1和2的交叉划分: . 1是2的加细划分:,|A| = n, A的不同划分的个数N: S(n, k)? Theorem n 1. Proof (?),2. 集合的覆盖 Def 设A是集合, 由A的若干非空子集构成的集合称为A的覆盖(covering), 如果这些非空子集的并等于A. a, b, b, c,集合的划分 集合的覆盖, 但反过来不成立. A = a, b,
25、 c上所有不同的覆盖有哪些? 作业 习题1.5 1, 4, 7.,1.6 集合的对等,集合的对等, 它是集合间的另一种关系. 通过集合对等以及相关内容的学习, 加深对函数概念的理解, 提高正确使用函数工具作为研究手段的能力. 1.集合对等(equivalent) Def A B: 存在双射f : A B.,N E. ZN? (0, 1) R. N N N. Theorem 1-28(对等的性质) (1) A A. (2) A B B A. (3) A B, B C A C.,2. 无限集合 有了集合对等的概念, 就可以给出无限集合及有限集合的严格定义. Def 设A是集合, 若存在A的一个子集
26、与自然数集合N对等, 则称A为无限集合(infinite set), 否则称A为有限集合(finite set). N. 0, 1.,3. 集合的基数 有限集合的基数就是的元素个数. 借助于集合对等概念, 可以将其扩展到无限集合. Def 若集合A和B对等, 则称这两个集合的基数(cardinality)相同. |A|.,4. 可列集合 Def 能与自然数集合N对等的集合称为可列集合(countable set). 根据无限集合的定义知：任意无限集合均存在一个可列的子集合. 根据这一点, 可以证明无限集合的特征性质. Theorem 设A是无限集合, 则存在A的一个真子集B, 使得 A B.,Proof 因为A是无限集合, 存在可列的子集合 考虑 Q是可列集合.,5. 不可列集合 是否所有无限集合都是可列的? 答案是否定的. 例 证明: (0,1)是不可列集合. Proof(反证) 取,6. 基数的比较 Def 给定集合A和B, 若存在A到B的单射, 则称A的基数小于等于B的基数, 记为|A| |B|. 若进一步, 不存在A到B的双射, 则称A的基数小于B的基数, 记为|A| |B|. 由定义易知, 若存在B到A的满射, 则|B| |A|. 显然, Problem 是否存在集合A, 满足 (著名的连续统假设?!) 作业 习题1.6 2, 4, 6.,