代数运算-计算机学院离散数学优秀课.ppt

1、计算机科学与工程学院2014年秋,主讲教师：王涛,离 散 数 学,Chapter 1 Sets, Mappings and Operations,集合是现代数学的最基本概念.映射又称为函数, 它是现代数学的基本概念, 可以借助于集合下定义.运算本质上是映射, 但有其特殊性.(关系也是集合)集合、映射、运算及关系是贯穿于本书的一条主线.,主要内容:,集合论是一门研究数学基础的学科，产生于16世纪末德国数学家康托（Georg Cantor, 18451918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人1902年英国数学家罗素（Russell,18721970）证明朴素集合论导致悖

2、论，随后为弥补这一缺陷出现了各种公理化集合论体系集合不仅可以表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中,集合论发展史,1873年至1883年德国数学家康托尔（Cantor）发表的系列论文奠定了集合论的基础。特别是1883年康托尔的集合论基础专著的出版，成为集合论理论研究的里程碑。这门学科今天已经成为整个数学的基础。,1899年德国数学家舍恩弗利斯第一篇点集论的论文在德国数学家联合会年报上发表。1914年德国数学家豪斯道夫出版集合论大纲更是集合论及点集拓扑学的经典著作。,集合论发展史,1.1 集合的有

3、关概念,集合 集合是指具有某种特定性质的对象汇集成的一个整体。集合中的每一个对象称为集合的元素，通常用大写字母表示集合，用小写字母表示集合中的元素。,在数学中常用 表示整体.集合通常用大写字母A, B, C, D,表示.在讨论集合时，应指定讨论范围，称为全集。记作U（或E）,说明：读作属于；读作不属于例:A=a,b,c,d，则有b A，e A,给定一个集合A， 若x是集合A中的元素，记作xA，读作x属于A； 若x不是集合A中的元素，则记作xA，读作x不属于A。,集合与集合中元素的关系隶属关系,对集合概念的理解:集合是现代数学的最基本的概念;集合不能给出精确定义,只能给出说明性描述;集合是我们描

4、述问题的一种基本工具;集合将世间万物分成两类:属于或不属于.,集合概念的深化,N是自然数集合,包括数0；Z是整数集合；Q是有理数集合；R是实数集合；C是复数集合.,几类特殊集合的表示,？,检查一个大于1的正整数是否为素数,对于任意整数m和n，若存在整数q，使得n=qm，则称m为n的因数，或称n被m整数，m整除n.,对于任意正整数n，用Dn表示n的所有正因数组成的集合.,对于大于1的正整数p，若Dn=1，p，则称p为素数，否则称p为合数.,集合的表示方法, 列举法就是把集合中的所有元素一一列举出来，或列出足够多的元素以反映出集合中成员的特征，元素之间用逗号分开，并用花括号括起来。如：A=a1，a

5、2，an B=0，2，4，6，8，2n，。,例：,设A=2，4，8，试判断16A吗？解： 若A=2，4，8，2n，则16A。 若A=2，4，8，2+n(n-1)，则16A。因此用列举法表示集合时通常给出通项式。, 描述法 是指把集合中的元素所满足的条件或具有的性质描述出来，即将条件或性质用文字或符号在花括号内竖线后面表示出来。一般形式为A=x|x满足的条件或具有的性质如：A=x|x-1=0，xR B= x|x是英文字母，x元音,集合的表示方法, 递归法 是指通过计算规则定义集合中的元素。首先给出该集合的初始元素；然后给出由集合中已知元素构造其他元素的方法；最后强调有限次使用前面的步骤得到的元素

6、是集合中仅有的元素。如：设a0=1,a1=1,an+1=an+an-1, A=a0,a1,a2,=akk0。,集合的表示方法, 巴科斯范式(BNF)表示法 BNF常用来定义高级程序设计语言的标识符或表达式集合。, 文氏图法(John Venn) 首先画一个大矩形表示全集，然后在矩形内画一些圆，用圆的内部表示集合，集合之间的相互关系和有关的运算可以用文氏图给予形象的描述。如：集合V=a，e，i，o，u,集合的表示方法,集合的其他表示法 对于A= 1,2,3,4，有1A，2,3A，3 A结论，此时可以用如下树形图表示这种关系。,集合的表示方法,集合的特性, 确定性 确定性是指一旦给定了集合A，对于

7、任意元素a，我们就可以准确地判定a是否在A中。如：A=x|x是自然数，且x100 则必有30A，101A, 互异性 互异性是指集合中的元素之间是彼此不同的，即集合中不允许出现重复的元素。如：集合 A=a,b,c,c,b,d 应为 A=a,b,c,d,集合的特性, 无序性 无序性是指集合中的元素之间没有次序关系。在不特别说明情况下，我们所讨论的集合都不是多重集。 如： A = a, a, b, b, c 与 A=a, b, c , a, b 相同,集合的特性, 抽象性 抽象性是指集合中的元素是抽象的，甚至可以是集合。如：A = a, a, b, b, c；,集合的特性, 多样性 多样性是指集合中

8、的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。如：A=1,a,*,-3,a , b,x|x是汽车,地球,有限集由有限个元素a1,an组成的集合称为有限集。基数（或势） 若集合A是有限集，则集合A中的元素个数称为集合A的基数（或势），通常记作|A|。无限集 无限集是指由无限个元素组成的集合。,几个相关概念,不含有任何元素的集合是空集。记或 。,空集定义,给定两个集合A和B，若A中的任意元素都属于B，则称A是B的子集，或称A包含在B，或称B包含A，通常记作A B，或BA。（若任意aA，必有aB，则A B） 如，集合A=1，2，3，4，5，B=1，3， C=1，3，5，7， 则有

9、B A ，C A， B C。,子集集合间关系,集合相等集合间关系,当集合A中的元素和集合B中元素完全相同时，称集合A和B相等，记作A=B。,例： 设A=x|x是偶数，且0x10，B= 2,4,6,8，试判断集合A、B关系。解：A=x|x是偶数，且0x10=2,4,6,8 =BA=B,定理1-4,对于任意的集合A，有 A。,设A、B、C是任意的集合，则有A A.A B,B A A = B.A B,B C A C.,真子集集合间关系,若AB，且AB，则称A是B的真子集，通常记作AB。（若A是B的真子集，则B中至少有一个元素不属于A。）,由A B, B C可否得出A C?,例,解：不成立,如A =

10、a, b, B = a, b, c, C = a, a, b, c.,上面这个例题给你什么启示？,幂 集,设X是一个集合，由X的所有子集作为元素构成的集合称为X的幂集，记以P(X)或2X。,定理 设A是一个有限集且|A|=n，则|P(A)|=2n,X = a, b P(X) = , a, b, a, b.P() = , .区分：, , ,例,n 元组,将n个元素x1, x2, xn按一定顺序排列就得到一个n元(有序)组.记为：,n=2,n=3,一般说来(x, y) (y, x).,n 元组,注意区别(a, b, c), (a, b), c), (a, (b, c)的不同.,2元组常称为有序对或

11、序偶.,笛卡儿积,设A1，A2，An是集合，称集合,为A1，A2，An的笛卡儿积（直积，叉积）。,定理, A = B = ,例：设A = a, b, B = 1, 2, C = , 求A B, B A, A B C , B C.,解： A B= (a, 1), (b, 1), (a, 2), (b, 2).B A= (1,a), (1, b ), (2, a), (2 ,b). AB C = (a, 1, ), (b, 1, ), (a, 2, ), (b, 2, ). B C= (1, ), (2, ),1.2 映射的有关概念,映射的定义,任意给定两个集合A和B，若存在对应法则 f ，使得对

12、于任意xA，均存在唯一的yB与它对应，则称 f 是集合A到B的一个映射，或称A到B的一个函数，记为 f :AB。,映射概念的理解,映射mapping = 函数function. A中任一元素在B中必有一个元素和其对应； A中任一元素在B中仅有一个元素和其对应；映射中每个序偶的第一个元素一定是互不相同的，且对应B中的唯一元素，而B中的元素未必都被对应到。f 代表一个集合,f (x)表示一个变值.因此f f (x).,(1)解析式 (2)图形(3)表格(数值计算中出现较多)函数符号的选取:f, g, F,G, , sin, exp, main, add, average, ,函数的表示,假定 f

13、:AB, y= f(x) ,通常把x称为自变量，其取值范围称为定义域记为dom f ；将y称为因变量，其取值范围称为值域，记为ran f。,全函数.映射f的定义域是集合A,记为dom f =A；唯一性.对于任意xA,对应于B中唯一的元素f(x),x为f的自变量(也称为原像),f(x)称为x在映射f下的像,通常记为y= f(x).,映射的两个特点,BA （读作B上A）定义,对于集合A和B，用BA表示A到B的所有映射组成的集合，即,定理： 对于集合A和B，若|A|=m，|B|=n，则|BA|=nm。,x1x2x3,y1y2,例,f:AB,设f :AB，令XA，用f (X)=f(x)|xX表示X在映

14、射f下的像.令YB, 用f -1(Y)=x | f(x)Y 表示Y在映射f下的原像.,像，原像定义,单 射,映射的性质,假设f :AB,如果对任意x1,x2A,由f(x1)=f(x2)可推出x1=x2,则称f是A到B的单射,或称f是A到B的一对一映射。,映射的性质,满 射,假设f :AB，如果对任意yB,均存在xA，使得y = f(x)，则称f是A到B的满射，或称f是A到B的映上的映射。,双 射,映射的性质,假设f :AB，f 既是单射又是满射，则称f是A到B的双射,或称f 是A到B的一 一对应。,例,1.设 f :NN ， f（x）=2 x，试证f 是N到N的单射。,证：对于任意x1 ，x2

15、 N，由f（x1）= f（x2），可得出2x1 =2x2 ，进而x1 =x2,3.试建立一个Z到N的确一一对应。,2.设 f :ZN ， f（x）=|x|，试证 f 是Z到N的满射。,证：任意yN，取x= y Z ，显然有y = f （x）。,课堂练习,当|A|=3，|B|=4，能构成f:AB且为单射的有多少种，若|A|=m，|B|=n(mn)呢？,当|A|=4，|B|=3，能构成f:AB且为满射的有多少种呢？,C43P33,CnmPmm,C42P33,置换定义,设A是有限集合,A到A的双射称为A上的置换.,逆映射,定义：设f: AB, 若将对应关系f逆转后能得出一个得到B到A的映射, 则称该

16、映射为f的逆映射, 记为f-1.,对应关系f逆转后一定得到B到A的映射？,定理：设f: AB ，则f的逆映射存在的充要条件是f是双射.,在什么情况条件下对应关系f逆转后一定得到B到A的映射？,1 f必须是单射；2 f必须是满射；,判定所给出的映射是否有逆映射，若有，求出其逆映射.,f: RR ，f(x)=x2. g: RR ，g(x)=x3.,复合映射,定理 设f: A B, g: B C，对于任意 xA，令h(x)=g(f(x)则h是集合A到集合C的映射。,x,y=f(x),z=g(y)=g(f(x),定义 设f: A B, g: B C,对于任意 xA,h(x)=g(f(x)则称h为f和g

17、的复合映射或复合函数，记为fg。,复合映射,例,在什么情况条件下fg 有意义？,f(A)dom(g),fg和 g f有意义，则fg=g f 成立？,1.3 运算的定义及性质,运算的定义,称f为A1, A2, An到B的n元运算:,区别?,称f A到B(或A上)的n元运算:,称f A上的n元封闭运算(代数运算):,(n = 0? 一般处理方式: A到B的一个0元运算可理解为B中某一个元素.),例1 （绝对值运算） f: Z N, f(x) = |x|.例2 (模运算) f: Z N, f(x) = x(mod k), x = qk + r, 0 r k: 8 = 2 3 + 2; -5 = -2

18、 3 + 1.,例：,模运算的两个简单应用(1) 加密;(2) Hash function.,课后延伸,运算符号的选取 函数符号 常见运算符号 自定义符号,运算的定义符号与位置,运算符号的位置,运算表A = a, b, c, *:,运算的定义运算表,思考: A上封闭的1元运算, 2元运算和3元运算的个数是多少?,2.运算的性质对合性,对合性 设*是A上的1元代数运算， 若对于任意的xA,均有*(*x)=x,则称*具有对合性，或称*满足对合律。,集合的非运算；数集的取反运算，矩阵的逆运算及转置运算均具有对合性。,实数集上的取相反数运算？,2.运算的性质幂等性,幂等性（等幂律）设*是A上的2元代数

19、运算， 若对于xA，有x*x=x则称x为关于*运算的幂等元；若对于A中每个元素x对于*都是幂等元，则称*运算具有幂等性或称*满足幂等律（等幂律）。,集合上的交、并运算具有幂等性.,2.运算的性质交换性,交换性（交换律） 设*是A上的2元代数运算， 若对于任意的x, y A， 均有 x*y=y*x，则称*满足交换律。,如何根据定义的运算判断是否可(交换)结合?,如何根据运算表判断运算是否可(交换)结合?,2.运算的性质结合性,结合性（结合律）设*是A 上的2元代数运算，若对于任意的x，y，zA,均有(x*y)*z=x*(y*z)，则称*运算具有结合性，或称*运算满足结合律。,2.运算的性质特殊元

20、素,单位元素设*是A上的2元代数运算,若存在eA,对于任意的xA,下列条件均成立： e*x=x； x*e=x. 则称e为集合A关于*运算的单位元素或幺元素。零元素 设*是A上的2元代数运算,若存在A,对于任意的xA,下列条件均成立：*x = ；x* = . 则称为集合A关于*运算的零元素。,2.运算的性质特殊元素,逆元素设*是A上的2元代数运算且有单位元素e，若对于xA,存在yA，使得下列条件均成立:x * y = e ;y * x = e.则称y为x的关于*的逆元素。,举例说明哪些运算具有幂等元、单位元、零元素和逆元素。,2.运算的性质消去性,消去性. 设*是A上的2元代数运算， 若A关于*

21、运算有零元则记为 , 如果对于任意的x, y, zA， 只要x , 那么下列条件均成立： x*y = x*z y=z；y*x = z*x y=z；则称*具有消去性， 或称*满足消去律。,2.运算的性质分配性,分配性（分配律）设*和是集合A上的两个2元代数运算，若对于任意x,y,zA,有 x*(yz)=x*yx*z； (yz)*x=y*xz*x成立，则称*对于是可分配的（分配律）。,2.运算的性质吸收性,吸收性 设*和是集合A上的两个2元代数运算,若对于任意x, yA,有 x*(xy)=x； (yx)*x=x成立，则称*对于是可吸收的（吸收律）。,2.运算的性质德摩根律,德摩根律 设是集合A上的

22、1元代数运算, *和是A上的两个2元代数运算,若对于任意x,y A， 均有下面两个等式成立:(x*y)=(x)(y)和(xy)=(x)*(y)则称这三种运算满足德摩根律。,1.4 集合的运算,并运算 设A和B是两个任意集合，由所有属于A或属于B的元素组成的集合称为集合A和B的并集，通常记作AB。即：AB=x|xA或xB如：设 A=a，b，c，d，B=b，d，e，f AB=a,b,c,d,e,f。,1.4 集合的运算,【并运算性质】幂等律： AA=A交换律： AB= BA结合律： (AB) C=A (BC)同一律： A=A(空集是并运算的单位元)零一律： UA=U(全集U是并运算的零元素),交运

23、算 设A和B是两个任意集合，由所有属于A又属于B的元素组成的集合，称为A和B的交集，通常记作AB。即AB=x|xA且xB如：设 A=a,b,c,d，B=b,d,e,f AB=b,d ,1.4 集合的运算,【交运算性质】 幂等律：AA=A 交换律：AB= BA 结合律：(AB)C=A (BC) 零一律：A=（空集是交运算的零元素） 同一律：UA= A（全集U是交运算的单位元素） 分配律： A(BC)=(AB)(AC)； A(BC)=(AB) (AC) 吸收律：A(AB)=A；A(AB)=A,1.4 集合的运算,补运算 设A和B是两个任意集合，由所有属于A又属于B的元素组成的集合，称为A和B的交集

24、，通常记作AB。即AB=x|xA且xB如：设 A=a,b,c,d，B=b,d,e,f AB=b,d ,1.4 集合的运算,【补运算性质】 有补律 A =U A = De Morgan律,1.4 集合的运算,差运算集合A，B的差集定义如下：A-B=x|xA且xB（由所有属于A但不属于B的元素组成的集合称为A和B的差集。）如：设A=a,b,c,d,B=b,c,e,f A-B=a,d B-A=e,f,1.4 集合的运算,【差运算性质】 A-A = A- = A A-U = ,1.4 集合的运算,对称差运算集合A，B的对称集定义如下：AB =（A-B） （B-A）（由所有属于A但不属于B或者属于B但不

25、属于A的元素构成的集合）如：设A=a,b,c,d,B=b,d,e,f AB =a,e,f ,1.4 集合的运算,【对称差运算性质】 A B = B A A = A A A = （A B） C = A （B C）,1.4 集合的运算,分别对条件到,确定 X 集合与下述那些集合相等。 S1 = 1, 2, , 8, 9 ,S2= 2, 4, 6, 8 , S3= 1, 3, 5, 7, 9 ,S4 = 3, 4, 5 ,S5= 3, 5 若 XS3=, 则 X= 若 XS4, XS2=, 则X= 若 XS1，XS3, 则X=若 XS3=, 则X=若 XS3，XS1, 则X=,例题,请指明下列的对应

26、关系 F：一年级大学生的集合 S：二年级大学生的集合 R：计算机系学生的集合 M：数学系学生的集合 T：选修离散数学的学生的集合 L：爱好文学学生的集合 P:爱好体育运动学生的集合,例题,所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运动只有一、二年级的学生才爱好体育运动除去数学和计算机系二年级学生外都不选修离散数学,TM(RS)RS T(MF)T=MLPPFSS(MR)P,例题,全集E为所有该图书馆藏书的书名所组成的集合, F:所有法国的书所组成的书名集; G:所有19世纪出版的书所组成的书名集; H:所有以农村为题材的书所组成的书名集

27、; R:所有长篇小说所组成的书名集; S:所有1999年出版的书所组成的书名集; C:所有中国的书所组成的书名集; K:所有描写改革开放的书所组成的书名集; 这样,此读者所要了解的书名可用集合论方法描述. R（GFH）（SCK）,练习：,某图书管有藏书100万册,有一读者前往查阅,他希望能了解所有19世纪出版的以农村为题材的法国长篇小说以及1999年出版的不是描写改革开放的长篇小说的书名.请将此读者要了解的书名用集合论方法描述.,练习：,容斥原理,第一种形式： 设A，B是有限集合，则| AB | = |A| |B| AB |另一种形式： 设A，B是有限集合，则,一个班有50个学生，在第一次考试

28、中得95分的有26人，在第二次考试中得95分的有21人，如果两次考试中没有得95分的有17人，那么两次考试都得95分的有多少人？解： 设A和B分别表示在第一次和第二次考试中得95分的学生的集合，则|A|=26，|B|=21，我们所求为|AB|，根据题意知：于是有 ， 则|AB|=14。,例题,1.5 集合的划分与覆盖,集合的划分设A是任意集合， P(A)，如果下列3个条件成立： ； 任意Ai,Aj，ij，有AiAj=； 。 则称是集合A的一种划分。,集合的划分定义的理解,设A = a, b, c, 则A的所有不同的划分分别为:,解:,例题,1和2的交叉划分:,集合的交叉划分与加细划分,1是2的

29、加细划分:,集合的覆盖 设A是集合, 由A的若干非空子集构成的集合称为A的覆盖, 如果这些非空子集的并等于A.,1.5 集合的划分与覆盖,集合的划分 集合的覆盖, 但反过来不成立.A = a, b, c上所有不同的覆盖有哪些?,世界文学名著唐吉诃德中有这样一个故事： 唐吉诃德的仆人桑乔潘萨跑到一个小岛上，成了这个岛的国王。他颁布了一条奇怪的法律：每一个到达这个岛的人都必须回答一个问题：“你到这里来做什么？”如果回答对了，就允许他在岛上游玩，而如果答错了，就要把他绞死。对于每一个到岛上来的人，或者是尽兴地玩，或者是被吊上绞架。有多少人敢冒死到这岛上去玩呢？一天，有一个胆大包天的人来了，他照例被问

30、了这个问题，而这个人的回答是：“我到这里来是要被绞死的。”请问桑乔潘萨是让他在岛上玩，还是把他绞死呢？如果应该让他在岛上游玩，那就与他说“要被绞死”的话不相符合，这就是说，他说“要被绞死”是错话。既然他说错了，就应该被处绞刑。但如果桑乔潘萨要把他绞死呢？这时他说的“要被绞死”就与事实相符，从而就是对的，既然他答对了，就不该被绞死，而应该让他在岛上玩。小岛的国王发现，他的法律无法执行，因为不管怎么执行，都使法律受到破坏。他思索再三，最后让卫兵把他放了，并且宣布这条法律作废。,罗素悖论(Russells paradox),设集合S=A|A是集合，且AA思考：若SS，则S是集合S的元素，但根据S的定

31、义，有S S，与假设矛盾；若SS，则S是不以自身为元素的集合，但根据S的定义，有SS，与假设矛盾；,罗素悖论(Russells paradox),我将为本城所有不给自己刮脸的人刮脸,我也只给这些人刮脸,我给不给自己刮脸?,是否存在集合A和B, 使得AB 且A B ？若存在，请举一例。 设A=a ，B=a,a,b,c，则有:AB 且A B 再例如： 且 ,讨论：,证明：,证明：任取 ，即aAB，亦即aA且aB，于是 且 ，故 ，所以任取 ,即 且 ，亦即aA且aB，于是aAB ，故,所以从而， 得证。,1.R1 = (a,1),(b,3),(c,5),(d,7)是A到B的双射 ？2.R2 = R1 (e,10),(f,9)是A C到B的满射?3.P = 1,10,9,3,5,1,7,9, 是B的一个划分? 4.ran(R1-1 R2) = A,对吗？5. 1, 2 , 1 , 2 , 是 1, 2 的幂集？,给出三个集合：A = a,b,c,d B = 1,3,5,7,9,10 C = d,e,f ,判断下列说法是否正确？,野 马 露宿风餐炼铁蹄，叱云啸月唤晴曦。 纵横大地行空阔，踔厉奔腾永不羁。,