离散数学集合映射运算省公共课一等奖全国赛课获奖课件.pptx

离散数学离散数学Discrete Mathematics邓辉文编著邓辉文编著清华大学出版社清华大学出版社普通高等教育普通高等教育“十二五十二五”国家级规划教材国家级规划教材http:/ 孤孤立立:社社会会网网络络(social networks)研研究究人人与与人人之之间间关关系系,Internet研研究究计计算算机机之之间间关系关系,WWW研究网页之间关系研究网页之间关系,第4页离散数学就是研究离散对象及其之间关系离散数学就是研究离散对象及其之间关系学科学科.实际上实际上,科学研究任务就是发觉对象之间内科学研究任务就是发觉对象之间内在关系和规律在关系和规律.第5页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第6页2、计算机专业为何要学离散数学、计算机专业为何要学离散数学第7页(1)当今计算机处理对象均离散当今计算机处理对象均离散:0和和1.(2)为后继专业课程学习作知识上准备为后继专业课程学习作知识上准备.(3)培养各种能力培养各种能力:抽象思维能力抽象思维能力,逻辑思维逻辑思维能力能力,计算思维计算思维(computational thinking,Jeannette M.Wing)能力能力,.(4)(教育部教育部,)离散数学是计算机各专业离散数学是计算机各专业专业专业基础课基础课.第8页程序设计语言程序设计语言离散数学离散数学数据结构与算法数据结构与算法计算机组成原理计算机组成原理计算机网络计算机网络操作系统操作系统数据库数据库软件工程软件工程第9页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第10页3、离散数学基本内容、离散数学基本内容数学世界数学世界http:/ 第11页1.集合与关系集合与关系Chapter 1 集合、映射与运算集合、映射与运算 Chapter 2 关系关系2.数理逻辑数理逻辑Chapter 3 命题逻辑命题逻辑Chapter 4 谓词逻辑谓词逻辑3.代数结构代数结构Chapter 5 代数结构代数结构4.图论图论Chapter 6 图论图论Chapter 7 几类特殊图几类特殊图5.组累计数组累计数(Chapter 8)第12页各章内容之间框架结构各章内容之间框架结构:第13页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第14页4、学习离散数学方法、学习离散数学方法第15页数学学习方法数学学习方法1.预习预习2.听课听课3.复习复习4.作业作业这么就能够专心致志地学好离散数学理论这么就能够专心致志地学好离散数学理论知识知识,在后继课程中有实际应用价值在后继课程中有实际应用价值.第16页本讲内容本讲内容什么是离散数学什么是离散数学1计算机专业为何要学离散数学计算机专业为何要学离散数学2离散数学基本内容离散数学基本内容3学习离散数学方法学习离散数学方法4离散数学学习资源离散数学学习资源5第17页5、离散数学学习资源离散数学学习资源第18页参考文件参考文件(均为国家精品课程均为国家精品课程):屈婉玲屈婉玲,耿素云耿素云,张立昂张立昂,离散数学离散数学,高等教育出高等教育出版社版社,.(108144课时课时)傅彦傅彦,顾小丰顾小丰,王庆先王庆先,离散数学及其应用离散数学及其应用,高等高等教育出版社教育出版社,.(两个学期两个学期)王元元王元元,沈克勤沈克勤,李拥军李拥军,贺汛贺汛,离散数学教程离散数学教程,高高等教育出版社等教育出版社,.Ebooks?第19页相关网络教学资源：相关网络教学资源：(1)Kenneth H.Rosen website:http:/ Mathematics and Its Applications(世界上有世界上有600多所大学使用多所大学使用,有影印本和翻译本有影印本和翻译本)(2)ArsDigita University:http:/aduni.org/courses/discrete/index.php?view=cw 第20页(3)Harver Mudd College:http:/ Institute of Technology):http:/ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-042JFall-/CourseHome/index.htm 第21页离散数学是计算机相关专业离散数学是计算机相关专业主要专业基础课程主要专业基础课程.好好学习好好学习天天向上天天向上第22页第第1章章 集合、映射与运算集合、映射与运算1.1 集合相关概念集合相关概念第23页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第24页1.1 集合相关概念集合相关概念1 集合集合集合是数学中最基本概念集合是数学中最基本概念,什么是集合什么是集合?在一定范围内在一定范围内,集合集合(set)是其是其含有某种特定含有某种特定性质性质对象聚集成一个整体对象聚集成一个整体,其中每一个对象其中每一个对象都称为该集合元素都称为该集合元素(element).第25页这里所指范围是全集这里所指范围是全集U.在数学中在数学中惯用惯用 表示整体表示整体.能够将考虑离散对象装在集合中能够将考虑离散对象装在集合中第26页(classic set)若若x是是集合集合A中中元素元素,则记则记x A,不然不然x A.第27页N是自然数集合是自然数集合,包含数包含数0Z是整数集合是整数集合Z+是正整数集合是正整数集合(N+)Q是有理数集合是有理数集合R是实数集合是实数集合素数集合素数集合P:2,3,5,7,11,13,17,19,23等等.第28页(a)m,n Z,m|n:n=qm,q Z.m是是n因因数数,n是是m倍数倍数.2|6,-2|6,2|-6,-2|-6.m|0,0|0.(b)Dn表示表示n全部正因数组成集合全部正因数组成集合,如如D6=1,2,3,6.(c)设设p 1,若若Dp=1,p,则称则称p为素数为素数(prime).第29页表示集合惯用方法表示集合惯用方法:(1)列举法列举法:将集合中元素按一定规律列举将集合中元素按一定规律列举出来出来,如如2,b,s,n,N=0,1,2,3,P?(2)描述法描述法:x|x满足条件满足条件.x|0 x 5,x;0 x 5第30页(3)递归法递归法递归思想递归思想:“知道他过去知道他过去,就知道他现在就知道他现在;知知道他过去和现在道他过去和现在,就知道他未来就知道他未来”.N递归定义递归定义:(a)0 N.(b)若若n N,则则n后继后继n+1 N.(c)有限次使用有限次使用(1)和和(2)得到元素是得到元素是N中仅有中仅有元素元素.其它方法其它方法?第31页Remarks(i)集合中元素能够是任意元素集合中元素能够是任意元素,如集合如集合,比比如如A=a,a,b,b,c.a,b A.(ii)集合之间元素集合之间元素标准上标准上是没有次序是没有次序,如如 A=a,a,b,b,c就是就是 a,b,c,a,b.(iii)集合中元素集合中元素标准上标准上不重复不重复,如如a,a,b,b,b,c还是集合还是集合A=a,a,b,b,c.第32页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第33页2.子集子集(1)A B空集空集是任意集合子集是任意集合子集.“小小”(2)A=B第34页Theorem 1-2(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.第35页注意注意 与与 不一样不一样:例例1-2 由由A B,B C可否得出可否得出A C?Solution 不成立不成立,比如比如A=a,b,B=a,b,c,C=a,a,b,c.A B?课堂练习课堂练习:习题习题1.1 4,5.第36页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第37页3.幂集幂集(power set)(X),X=a,b P(X)=,a,b,a,b.为何要考虑幂集为何要考虑幂集(结合其上运算及性质结合其上运算及性质)?第38页P()=.P(P()=P()=,.区分区分:,.第39页有限集合有限集合A元素个数元素个数|A|,card(A).Theorem 1-4 Hint 第40页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第41页4.n元组元组(抽象抽象!)Def 1-4 将将n个个元素元素(?)x1,x2,xn按一定次序按一定次序排列就得到一个排列就得到一个n元元(有序有序)组组(n-tuple).第42页线性代数中线性代数中n维向量维向量(?)元组在数据结构中是一个线性表、栈或队元组在数据结构中是一个线性表、栈或队列列,在数据库中是一条统计在数据库中是一条统计,如如(张三张三,男男,19,重庆重庆).n=2,n=3:第43页 n=2:(x,y).n=3:(x,y,z)4元组元组?普通说来普通说来(x,y)(y,x).第44页2元组常称为有序对元组常称为有序对(ordered pair)或序偶或序偶.(x,y)第45页本讲内容集合集合1子集子集2幂集幂集3n元组元组4笛卡儿积笛卡儿积5第46页5.笛卡儿积笛卡儿积(cross product)解析几何之父笛卡儿解析几何之父笛卡儿(R.Cartesian,1596-1650)是法国数学家是法国数学家,“我思故我在我思故我在”和和“越越学习越发觉自己无知学习越发觉自己无知”是他名言是他名言.第47页例例1-4 设设A=a,b,B=1,2,C=,求求A B,B A,A B C,B C.Solution ABC=(a,1,),(b,1,),(a,2,),(b,2,).BC=(1,),(2,)Remark A=B =.课堂练习课堂练习:习题习题1.1 10第48页Theorem 1-5Hint 第49页小结与作业小结与作业集合就是一些对象组成整体集合就是一些对象组成整体习题习题1.1 6,7,10作业作业A B,A=B第50页第第1章章 集合、映射与运算集合、映射与运算1.2 映射相关概念映射相关概念第51页本讲内容映射定义映射定义1映射性质映射性质2第52页1.2 映射相关概念映射相关概念1.映射定义映射定义映射映射(mapping)=函数函数(function).y=f(x)=x2,ceiling function ,floor function ,编写编写C语言程序主要就是编写函数语言程序主要就是编写函数:从从main开始开始.第53页Def 任意给定两个集合任意给定两个集合A和和B,若存在对应法若存在对应法则则f,使得对于使得对于任意任意 x A,均存在均存在唯一唯一y B与与它对应它对应,则称则称f是集合是集合A到到B映射映射,或称其为或称其为A到到B函数函数,记为记为AB第54页为何讨论映射为何讨论映射?集合之间对应关系集合之间对应关系.其它了解方式其它了解方式:第55页映射两个特点映射两个特点:(1)全函数全函数.(2)唯一性唯一性.注意区分函数注意区分函数 f 与与 f(x).y=f(x)?第56页函数符号选取函数符号选取:f,g,F,G,sin,exp,main,add,average,hanoi,delete_string,第57页例例1-5 写出全部写出全部A到到B映射映射.x1x2x3y1y2第58页n元函数元函数(n 1):第59页float average(float array,int n)n=0:C语言中无参函数语言中无参函数?第60页本讲内容映射定义映射定义1映射性质映射性质2第61页2.映射性质映射性质(1)单射单射(injection)第62页例例1-6 设设f:N N,f(x)=2x,则则f是是N到到N单射单射,试证实之试证实之.Proof 对任意对任意x1,x2 A,由由f(x1)=f(x2),可得可得出出2x1=2x2,进而进而x1=x2.第63页(2)满射满射(surjection)第64页例例1-7 说明说明 是是Z到到N满射满射,但不是但不是Z到到Z满射满射.第65页(3)双射双射(bijection,one-to-one correspondence)双射又称为一一对应双射又称为一一对应:既单又满既单又满.例例1-8第66页例例1-9第67页Def 1-11 有限集合有限集合A上本身双射称为上本身双射称为A上置上置换换(permutation).例例1-10第一个方式第一个方式:123123第68页第二种方式第二种方式:A=1,2,3,4上全部置换有多少个上全部置换有多少个?4!主要应用主要应用:置换置换加密加密.第69页小结与作业小结与作业映射映射(函数函数)定义定义单射单射满射满射双射双射(一一对应一一对应)习题习题1.2 1,2,3作业作业第70页第第1章章 集合、映射与运算集合、映射与运算1.3 运算定义及性质运算定义及性质第71页本讲内容运算定义运算定义1第72页1.运算定义A1,A2,An到到Bn元运算元运算(n-ary operation):第73页A1=2,S,N,A2=B,B=2B,SB,NB第74页A到到B(或或A上上)n元运算元运算:A=5角硬币角硬币,1元硬币元硬币,B=打火机打火机,矿泉矿泉水水,雪糕雪糕,智能手机智能手机,平板电脑平板电脑第75页(运算封闭性运算封闭性)A上上n元封闭运算元封闭运算(代数运算代数运算):A=1,2,3,A上取小运算上取小运算min:第76页n元运算就是元运算就是n元函数元函数:n=0?普通处理方式普通处理方式:A到到B一个一个0元运算可元运算可了解为了解为B中某一个元素中某一个元素.第77页考虑运算目标考虑运算目标?运算是由已知对象得出运算是由已知对象得出新对象一个方法新对象一个方法.例例1-15(模运算模运算)f:Z N,f(x)=x(mod m),x=qm+r,0 r 1)表示小于等于表示小于等于n且与且与n互素正整数个数互素正整数个数:第84页(1)=1,(2)=1,(3)=2,(4)=2,(5)=4,(6)=2,第85页D.Euclid算法算法:Solution 第86页第87页Remarks(1)运算符号运算符号(算符算符,算子算子)选取选取函数符号函数符号f,g,F,G,;常见运算符号常见运算符号+,/,;自定义符号自定义符号 ,第88页(2)运算符号位置运算符号位置 第89页(3)运算表运算表A=a,b,c,*:思索思索 A上封闭上封闭1元运算元运算,2元运算和元运算和3元运算元运算个数是多少个数是多少?*a b cabc b a c b c c c a b第90页运算本质上是映射运算本质上是映射.为何还要研究运算为何还要研究运算?但研究侧重点不一样但研究侧重点不一样,在运算中更重视于运在运算中更重视于运算满足一些运算性质算满足一些运算性质,而依据这些性质能够而依据这些性质能够对一些离散对象分门别类进行讨论对一些离散对象分门别类进行讨论.第91页小结与作业小结与作业n元运算和元运算和n元封闭运算定义元封闭运算定义模模m运算运算gcd(m,n)及及Euclid算法算法,lcm(m,n)运算符号及运算表运算符号及运算表习题习题1.3 2,3,7作业作业第92页第第1章章 集合、映射与运算集合、映射与运算1.3 运算定义及性质运算定义及性质第93页本讲内容运算性质运算性质(常见有常见有11种种)2第94页2.运算性质运算性质(1)对合对合(involutive)性性 Def 1-15 设设*是是A上上1元元代数运算代数运算,例例 第95页(2)幂等幂等(idempotent)性性 幂等元幂等元x:A关于关于*含有幂等性含有幂等性:A中每个元素对于中每个元素对于*都是都是幂等元幂等元.第96页两个例子两个例子:*1 2 3123 1 3 2 2 3 2 3 1 3第97页(3)交换交换(commutative)性性 Def 设设*是是A上上2元代数运算元代数运算,若对于任意若对于任意x,y A,都有都有 则称则称*满足交换律满足交换律.映射复合运算映射复合运算不满足交换律不满足交换律:加法运算加法运算”+”满足交换律满足交换律,而减法运算而减法运算”-”不满足交换律不满足交换律:2 3 3 2.怎样依据定义运算判断运算含有交换性怎样依据定义运算判断运算含有交换性?第98页(4)结合结合(associative)性性 映射复合运算映射复合运算满足结合律满足结合律:加法运算加法运算“+”满足结合律满足结合律,而减法运算而减法运算“-”不满足结合律不满足结合律:(2-3)-5 2-(3 5).第99页(5)幺元律幺元律 Def 1-19 设设*是是A上上2元代数运算元代数运算,若存在若存在e A,对于任意对于任意x A,以下条件均成立：以下条件均成立：则称则称e为集合为集合A关于关于*运算单位元素或幺元素运算单位元素或幺元素第100页例例 Z关于加法运算关于加法运算+单位元素为单位元素为0,而而Z关于关于乘法运算乘法运算“.”单位元素为单位元素为1,Z关于减法运关于减法运算算-没有单位元素没有单位元素.第101页(6)零元律零元律 Def 设设*是是A上上2元代数运算元代数运算,若存在若存在 A,对对于任意于任意x A,以下条件均成立：以下条件均成立：则称则称 为集合为集合A关于关于*运算零元素运算零元素.第102页例例1-28 Z关于加法运算关于加法运算+和减法运算和减法运算-均没有均没有零元素零元素,而而Z关于乘法运算关于乘法运算 零元素为零元素为0.第103页(7)逆元律逆元律若若A关于运算关于运算*有单位元素有单位元素e,则能够讨论则能够讨论A中中取定元素取定元素x是否有逆元是否有逆元.Def 设设*是是A上上2元代数运算且有单位元素元代数运算且有单位元素e,若对于若对于x A,存在存在y A,使得以下条件均成使得以下条件均成立立:则称则称y为为x关于关于*逆元素逆元素.第104页一个映射关于函数复合运算逆元就是其逆一个映射关于函数复合运算逆元就是其逆映射映射,当然只有双射才有逆元当然只有双射才有逆元,其单位元素是其单位元素是恒等映射恒等映射.例例1-29 R中各元素关于加法运算中各元素关于加法运算+和乘法运和乘法运算算 逆元素逆元素.第105页(8)消去消去(cancellation)性性.Def 设设*是是A上上2元代数运算元代数运算,若若A关于关于*运算运算有零元则记为有零元则记为 ,假如对于任意假如对于任意x,y,z A,只要只要x ,那么以下条件均成立：那么以下条件均成立：则称则称*含有消去性含有消去性,或称或称*满足消去律满足消去律.第106页例例1-31 Z上加法运算上加法运算+和乘法运算和乘法运算 均满足消均满足消去律去律.例例1-32 实数集实数集R上全部上全部2阶方阵组成集合阶方阵组成集合,关关于矩阵乘法运算不满足消去律于矩阵乘法运算不满足消去律.第107页(9)分配分配(distributive)性性.Def 设设*和和是集合是集合A上两个上两个2元代数运算元代数运算,若对若对于任意于任意x,y,z A,有有 则称则称*对于对于是可分配是可分配.第108页例例1-33 实数集合实数集合R上乘法运算上乘法运算 对加法运算对加法运算+可分配可分配,但加法运算但加法运算+对乘法运算对乘法运算 不可分配不可分配.矩阵乘法和加法运算矩阵乘法和加法运算?集合并和交运算集合并和交运算?第109页(10)吸收吸收(absorptive)性性 Def 设设*和和是集合是集合A上两个上两个2元代数运算元代数运算,若对若对于任意于任意x,y A,有有 则称则称*对于对于是可吸收是可吸收.集合并和交运算集合并和交运算?第110页(11)德德摩根摩根(De Morgan)律律 Def 设设 是集合是集合A上上1元代数运算元代数运算,*和和是是A上上两个两个2元代数运算元代数运算,若对于任意若对于任意x,y A,都有都有下面两个等式成立下面两个等式成立:则称这三种运算满足德则称这三种运算满足德 摩根律摩根律.集合补、并和交运算集合补、并和交运算?第111页小结与作业小结与作业对合律对合律幂等律、交换律、结合律、幺元律、零元律、逆元律、消去律幂等律、交换律、结合律、幺元律、零元律、逆元律、消去律分配律、吸收律分配律、吸收律De Morgan律律习题习题1.3 8,12,15作业作业第112页第第1章章 集合、映射与运算集合、映射与运算1.4 集合运算集合运算1.5 集合划分与覆盖集合划分与覆盖第113页本讲内容123并运算并运算交运算交运算45补运算补运算差运算差运算对称差运算对称差运算集合划分与覆盖集合划分与覆盖6第114页最常见集合运算是并、交和补最常见集合运算是并、交和补.1.并并(union)运算运算第115页Theorem1-17(并运算满足性质并运算满足性质)(1)(2)(3)(4)A =A=A(5)A U=U A=U第116页第117页本讲内容123并运算并运算交运算交运算45补运算补运算差运算差运算对称差运算对称差运算集合划分与覆盖集合划分与覆盖6第118页2.交交(intersection)运算运算第119页Theorem1-19(交运算满足性质交运算满足性质)(1)(2)(3)(4)A =A=(5)A U=U A=A第120页Theorem 1-20(并运算与交运算之间所满足并运算与交运算之间所满足性质性质.)(1)吸收性吸收性.(2)分配性分配性.第121页例例1-41第122页本讲内容123并运算并运算交运算交运算45补运算补运算差运算差运算对称差运算对称差运算集合划分与覆盖集合划分与覆盖6第123页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第124页排中律成立排中律成立:.排中律排中律:x U,x A或或 x A二者必居其二者必居其一一,没有中间情况没有中间情况.第125页集合补运算和集合并交运算满足集合补运算和集合并交运算满足De Morgan律律:推广推广?第126页P(n),nn0.第一数学归纳法第一数学归纳法:(1)P(n0)成立成立.(2)假定假定P(n-1)时成立时成立,证实证实P(n)成立成立.第二数学归纳法第二数学归纳法:(1)P(n0)成立成立.(2)假定比假定比n小都成立小都成立,证实证实P(n)成立成立.第127页本讲内容123并运算并运算交运算交运算45补运算补运算差运算差运算对称差运算对称差运算集合划分与覆盖集合划分与覆盖6第128页4.差差(subtraction)运算运算例例1-43 第129页Theorem 1-23Proof(1)(2)第130页例例1-45 对于任意集合对于任意集合A,B和和C,证实证实:(A B)C=A (B C)Poof第131页例例1-46 .例例1-47(A B)(A C)=充要条件充要条件?Solution由上例知由上例知,A (B C)=第132页本讲内容123并运算并运算交运算交运算45补运算补运算差运算差运算对称差运算对称差运算集合划分与覆盖集合划分与覆盖6第133页5.对称差对称差(symmetric difference)运算运算See Venn Figure below.例例1-48第134页第135页Theorem(对称差运算性质对称差运算性质)(1)交换性交换性:(2)单位元单位元:A =A.(3)A A=.(4)结合性结合性:第136页例例1-49(消去律消去律)Hint第137页例例1-50 A B=A=B.Proof()显然显然.()A B=A B=且且B A=第138页思索思索 还能定义集合其它运算还能定义集合其它运算(共共9种！种！)?加法原理推广加法原理推广:容斥原理容斥原理:第139页容斥原理另一个形式容斥原理另一个形式:第140页1.5 集合划分与覆盖集合划分与覆盖第141页集合划分就是集合元素间一个集合划分就是集合元素间一个分类分类.流行术语流行术语:聚类聚类.比集合划分更广概念是集合覆盖比集合划分更广概念是集合覆盖.这些内容这些内容在下章会用到在下章会用到.1.集合划分集合划分(partition)第142页Def 1-31(1),i I.(2),i j.(3)分组分组,磁盘分区磁盘分区?第143页例例1-53 设设A=a,b,c,则则A全部不一样划分全部不一样划分分别为分别为:第144页 1和和 2交叉划分交叉划分:.1是是 2加细划分加细划分:第145页|A|=n,A不一样划分个数不一样划分个数N=N(n):S(n,k):n个元素划分成个元素划分成k个块方案数个块方案数.Theorem n 1.Proof(?)第146页2.集合覆盖集合覆盖Def 设设A是集合是集合,由由A若干非空子集组成集合若干非空子集组成集合称为称为A覆盖覆盖(covering),假如这些非空子集并假如这些非空子集并等于等于A.a,b,b,c集合划分集合划分集合覆盖集合覆盖,但反过来不成立但反过来不成立.第147页小结与作业小结与作业集合并、交、补运算及其性质集合并、交、补运算及其性质集合差和对称差运算及结论集合差和对称差运算及结论数学归纳法数学归纳法容斥原理容斥原理习题习题1.4 1,8,10 习题习题1.5 1 作业作业集合划分与覆盖集合划分与覆盖第148页第第1章章 集合、映射与运算集合、映射与运算1.6 集合对等集合对等第149页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第150页集合对等集合对等,它是集合间另一个关系它是集合间另一个关系.经过集合对等以及相关内容学习经过集合对等以及相关内容学习,加深对函加深对函数概念了解数概念了解,提升正确使用函数工具作为研提升正确使用函数工具作为研究伎俩能力究伎俩能力.1.集合对等集合对等(equivalent)Def 1-33 若存在双射若存在双射f:A B,则则 A B.第151页N EZ N(0,1)RN N N(see below):第152页第153页Theorem 1-28(对等性质对等性质)(1)A A.(2)A B B A.(3)A B,B C A C.第154页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第155页2.无限集合无限集合有了集合对等概念有了集合对等概念,就能够给出无限集合及就能够给出无限集合及有限集合严格定义有限集合严格定义.Def 1-34 设设A是集合是集合,若存在若存在A一个子集与自一个子集与自然数集合然数集合N对等对等,则称则称A为无限集合为无限集合(infinite set),不然称不然称A为有限集合为有限集合(finite set).N.0,1a,b,c?第156页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第157页3.集合基数集合基数有限集合基数就是元素个数有限集合基数就是元素个数(因为因为0=,1=,n+1=n n),无限集合无限集合?Def 若集合若集合A和和B对等对等,则称这两个集合基数则称这两个集合基数(cardinality)相同相同.|A|,card(A),#(A).第158页G.Cantor(18451918,德国数学家德国数学家)被这些问题所被这些问题所折磨难以自拔折磨难以自拔(除自己牙齿外除自己牙齿外,还有什么不能自拔还有什么不能自拔).1884年后患精神病年后患精神病(受到很多人批评和攻击受到很多人批评和攻击,包含包含他老师他老师L.Kronecker(18231891).用脑过分吗用脑过分吗?第159页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第160页4.可数集合可数集合(可数名词可数名词?)Def 1-36 能与自然数集合能与自然数集合N对等集合称为可对等集合称为可数集合数集合(countable set)或可列集合或可列集合.第161页可列集合可列集合:N0,2,4,6,ZQ第162页无限集合特征性质无限集合特征性质:Theorem 1-29 设设A是无限集合是无限集合,则存在则存在A一一个真子集个真子集B,使得使得 A B.Proof 因为因为A是无限集合是无限集合,存在可数子集合存在可数子集合考虑考虑第163页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第164页5.不可数集合不可数集合(不可数名词不可数名词?)是否全部没有限集合都是可数是否全部没有限集合都是可数?例例 证实证实:(0,1)是不可数集合是不可数集合.Proof(反证反证)取取(see below)第165页第166页本讲内容集合对等定义集合对等定义1234不可数集合不可数集合5无限集合无限集合集合基数集合基数可数集合可数集合6基数比较基数比较第167页6.基数比较基数比较Def 1-37 给定集合给定集合A和和B,若存在若存在A到到B单射单射,则称则称A基数小于等于基数小于等于B基数基数,记为记为|A|B|.若若深入深入,不存在不存在A到到B双射双射,则称则称A基数小于基数小于B基基数数,记为记为|A|B|.第168页由定义易知由定义易知,若存在若存在B到到A满射满射,则则|B|A|.显然显然,Problem 是否存在集合是否存在集合A,满足满足(著名连续统假设著名连续统假设?!)第169页小结与作业小结与作业A B无限集合与集合基数无限集合与集合基数可数集合与不可数集合可数集合与不可数集合习题习题1.6 4,5,6 作业作业基数比较基数比较第170页离散数学第第1 1章复习小结章复习小结第171页1、集合相关概念 集合就是一些对象组成整体集合就是一些对象组成整体.若若x是集合是集合A中中元素元素,记为记为x A,不然不然x A.了解集合就是要把集合中元素搞清楚了解集合就是要把集合中元素搞清楚,需要需要知道一些背景知识知道一些背景知识,如整数、整除、偶数、如整数、整除、偶数、素数、因数、空集、元组等素数、因数、空集、元组等.第172页表示集合能够用列举法、描述法和递归法表示集合能够用列举法、描述法和递归法.集合中元素能够是任意对象集合中元素能够是任意对象,如元素本身又如元素本身又能够是集合能够是集合;集合中元素本身没有次序关系集合中元素本身没有次序关系;集合中元素标准上不重复集合中元素标准上不重复.第173页给定集合给定集合B,B子集子集A就是集合就是集合B中一些元素中一些元素组成组成“新新”集合集合,记为记为A B.要注意要注意 和和 区分区分.例例1 判断题判断题.(1).(2).(3).(4).第174页例例2 由由A B,B C可否得出可否得出A C?Solution 不成立不成立,比如比如A=a,b,B=a,b,c,C=a,a,b,c.A B?第175页证实两个集合相等惯用到证实两个集合相等惯用到“A=B充要条件充要条件是是A B且且B A.”结论结论.第176页集合集合X幂集幂集P(X)是是X全部子集组成集合全部子集组成集合.注意注意P(X),要求会计算给定集合幂集要求会计算给定集合幂集.主要结论是主要结论是:若若|X|=n,则则|P(X)|=2n.第177页例例3 计算计算P(),P(P()和和P(,a)Solution P()=.P(P()=P()=,.P(,a)=?X=,a P(X)=?第178页选取选取n个元素个元素x1,x2,xn按一定次序排列排按一定次序排列排列起来就是一个元组列起来就是一个元组,记为记为 (x1,x2,xn).数据结构数据结构:(D,R).图图G=(V,E).文法文法G=(V,T,P,S)自动机自动机M=(Q,q0,F)第179页笛卡儿积笛卡儿积A1 A2 An =(x1,x2,xn)|xi Ai,i=1,2,n.能熟练计算笛卡儿积能熟练计算笛卡儿积.若若|X|=m,|Y|=n,则则|X Y|=mn.第180页例例4 设设A=a,b,B=1,2,C=,求求A B,A B C,B C.SolutionA B C=(a,1,),(b,1,),(a,2,),(b,2,).B C=(1,),(2,)Remark A=B =.第181页2、映射相关概念 映射映射 f:AB 就是将集合就是将集合A元素唯一对应到元素唯一对应到集合集合B中元素中元素.要深入了解映射含义要深入了解映射含义,包含函包含函数符号选取和多元函数数符号选取和多元函数,区分区分f和和f(x)不一样不一样,了解天花板函数和地板函数了解天花板函数和地板函数.第182页映射映射f:AB:若不一样若不一样A中元素对应不一样中元素对应不一样B中元素中元素,f就就是单射是单射;若函数值充满整个集合若函数值充满整个集合B,f就是满射就是满射;既是单射又是满射即为双射既是单射又是满射即为双射.第183页设设f:AB,若将若将f方向逆转能得到方向逆转能得到B到到A函数函数,它就是它就是f逆函数或反函数逆函数或反函数,记为记为f-1.函数函数f有反函数充要条件是有反函数充要条件是f是双射是双射.第184页先进行映射先进行映射,再进行映射再进行映射,可得到可得到A到到C映射映射,它就是它就是f与与g复合映射复合映射,记为记为f g.要求掌握两要求掌握两个函数复合运算个函数复合运算.普通来说普通来说,f g g f,但但(f g)h=f(g h).尤其应注意函数复合运算尤其应注意函数复合运算与单射、满射和双射之间关系与单射、满射和双射之间关系.第185页例例5(习题习题1.2,4)假定假定f:AB,证实证实(1)f IB=f(2)IAf=f.Proof(1)x A,(f IB)(x)=IB(f(x)=f(x)f IB=f.(2)x A,(IAf)(x)=f(IA(x)=f(x)IAf=f.第186页例例6(习题习题1.2,8)设设f:AB,若存在若存在g:BA,使得使得f g=IA且且g f=IB,则则f是双射且是双射且f-1=g.Proof 由由f g=IA,知知f是单射是单射.由由g f=IB,知知f是满射是满射.于是于是 f是双射是双射,进而进而f-1 存在存在.因为因为f-1(f g)=f-1 IA,而而f-1(f g)=(f-1 f)g=IB g=g且且 f-1 IA=f-1,所以所以f-1=g.第187页例例7(习题习题1.2,13)设设f:AB,g:BC,h:CA,若若f g h=IA,g h f=IB,h f g=IC,则则f,g,h均可逆均可逆,并求出并求出f-1,g-1和和 h-1.Hint f?f g h=IA,g h f=IB f是双射是双射.f-1=g h.第188页补充练习补充练习1 设设R为实数集合为实数集合,定义定义f:R R R R为为(1)证实证实f是双射是双射.(2)求求f逆函数逆函数f-1.(3)计算计算f-1 f 及及f f.第189页补充练习补充练习2 设设N为自然数集合为自然数集合,定义定义N 到到 N函数函数f 和和g以下以下:x N,f(x)=x+1,g(x)=max0,x-1.证实：证实：(1)f是单射而不是满射是单射而不是满射,g是满射而不是单射是满射而不是单射.(2