第1章-集合映射与运算

离散数学是计算机各专业的专业基础课.离散数学研究的对象:离散量及其之间的关系.离散量与连续量及其之间的转换.现今计算机的处理对象是非常特殊的离散量:0和1.学习离散数学的目的:1.培养各种能力.2.为后继专业课程的学习作知识上的准备.离散数学的基本内容:1.集合与关系Chapter1集合、映射与运算Chapter2关系2.数理逻辑Chapter3命题逻辑Chapter4谓词逻辑3.代数结构Chapter5群、环和域Chapter6格与布尔代数4.图论Chapter7图论Chapter8几类特殊的图学习离散数学的方法:1.预习.2.听课.3.复习.4.作业.参考文献:耿素云屈婉玲,离散数学(修订版),高等教育出版社,2004.KennethH.Rosen,DiscreteMathematicsandItsApplications(FourthEdition),McGraw-HillCompanies,Inc.1998.(有中译本,2002)Chapter1Sets,MappingsandOperations集合是现代数学的最基本概念(?).映射又称为函数,它是现代数学的基本概念,可以借助于集合下定义.运算本质上是映射,但其研究有其特殊性.集合、映射、运算及关系(Chapter2)是贯穿于本书的一条主线.1.1集合的有关概念1.集合集合(用处?)已渗透到自然科学以及社会科学的各个研究领域,在信息的表示及处理中,可以借助于集合去实现数据的删节、插入、排序以及描述数据间的关系.在一定范围内,集合(set)是其具有某种特定性质的对象汇集成的一个整体,其中的每一个对象都称为该集合的元素(element).这里所指范围是全集U(见图1-1).(避免悖论!)在数学中常用{}表示整体.若x是集合A中元素,则记xA,否则xA.常见的数的集合用黑正体字母表示: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,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.不含有任意元素的集合称为空集(emptyset),记为或{}.?}|{AAAS2.子集AB,特别地是任意集合的子集.A=B.Theorem1-2(P3)(1)AA.(2)AB,BAA=B.(3)AB,BCAC.Theorem1-3A=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.幂集(powerset)X={a,b}P(X)={,{a},{b},{a,b}}.P(P())=P({})={,{}}(P5,6(1)).,{},{{}}(P5,2)}|{)(XAAXPTheorem1-4Proof由乘法原理证明?.2|)(|||nXPnX},...,,{21naaaX.2)11(...121nnnnnnCCC.22...22:},...,,{nnA4.n元组Def1-4将n个元素(?)x1,x2,…,xn按一定顺序排列就得到一个n元(有序)组(n-tuple).在数据结构中就是一个线性表..,...,,),,...,,(2121nnxxxxxxn=2:(x,y).n=3:(x,y,z)4元组?显然,一般说来(x,y)(y,x).注意区别(a,b,c),((a,b),c),(a,(b,c))的不同.),(yxO),,(zyxO.,),...,,(),...,,(2121iyxyyyxxxiinn),(xyn维向量是n元组,长度为n的线性表是n元组,抽象数据结构Data_Structure=(D,S)本身是一个2元组.2元组常称为有序对(orderedpair)或序偶.5.笛卡儿积(crossproduct)}.,..,2,1,|),...,,{(...2121niAxxxxAAAiinn}.,..,2,1,|),...,,{(...21niAxxxxAAAAinnn例1-4(P4)设A={a,b},B={1,2},C={},求AB,BA,BC,ABC.SolutionBC={(1,),(2,)}ABC={(a,1,),(b,1,),(a,2,),(b,2,)}.)}2,(),1,(),2,(),1,{(bbaaBA)},2(),,1(),,2(),,1{(bbaaABRemarkA=A=.P5,10?TheoremHint可推广到更多个集合的笛卡儿积的情形:作业习题1.16,9,10..||||,||mnBAnBmA}.,|),{(ByAxyxBA}.,...,2,1,|),...,,{(...2121niAxxxxAAAiinn1.2映射的有关概念1.映射的定义映射mapping=函数function.C语言是一种函数型语言:从main开始.DefABfBAf:函数的表示:(1)解析式(2)图形(3)表格(数值计算中出现较多)函数符号的选取(P6):f,g,…,F,G,…,,,…,sin,exp,main,add,average,…注意区别函数f与函数表达式f(x).映射的两个特点:(1)全函数;(2)唯一性..1)(R,R:2xxffB上A:例1-5Theorem1-6注意B上A的记号与该结论的关系.}.:|{BAffBA}.8,...,2,1|{ifBiAx1x2x3y1y2BAf:.||||,||mAnBnBmABA像与原像:)(),(1YfXf}|)({)(,:XxxfXfAXBAf})(,|{)(,:1YxfAxxYfBYBAfXf(X)Yf-1(Y)n元函数(n1):floataverage(floatarray[],intn),...,:21nAAAABAf,...),...,,(2121nnAAAxxxxAx.),...,,()),...,,(()(2121yxxxfxxxfxfnn2.映射的性质(1)单射(injection)BAf:.)()(,,212121xxxfxfAxx).()(,,212121xfxfxxAxxfBA(2)满射(surjection)例1-7是Z到N的满射,但不是Z到Z的满射(?).).(,,xfyAxBy.ranBff||)(xxfBA(3)双射(bijection,one-to-onecorrespondence)双射又称为一一对应:既单又满.例1-8例1-9(P8),...3,2,1,0,1,2,3...,:Z,...6,5,4,3,2,1,0:N1O.π21tanxy例1-10Def1-11有限集合A上自身的双射称为A上的置换(permutation).A={1,2,3,4}上的所有置换有多少个?4!123123f3.逆映射设f:AB,将对应关系f逆转(改变方向),一般来说,不能得到B到A的映射:abc123Def1-12设f:AB,若将对应关系f逆转后能得出一个得到B到A的映射,则称该映射为f的逆映射(invertiblefunction),记为f-1.abc123Theorem1-7f的逆映射存在的充要条件是f是双射.对于y=sinx,当时,有反函数,常记为当时,y=sinx仍有反函数,但不能记为arcsin.显然,当时,无反函数.]1,1[2π,2π:sin2π,2πx.2π,2π]1,1[:arcsin23π,2πx23π,0x4.复合映射(compositionfunction)Theorem1-8设f:AB,g:BC:则h:AC.)).(()(,xfgxhAxxy=f(x)z=g(y)=g(f(x))hfgDef1-13例1-12abc123fggfhRemarks(1)y=sinu,u=x2未引入运算符号,有时是不方便的.(2)顺序问题:有些专业书但会出现一些混乱..sin2xy)).(())((xfgxgf)).(())((xfgxfg例1-13(P9)f:RR,f(x)=x2,g:RR,g(x)=x+2,求f◦g和g◦f.SolutionxR:(f◦g)(x)=g(f(x))=g(x2)=x2+2.(g◦f)(x)=f(g(x))=f(x+2)=(x+2)2.Remarkf◦gg◦f.IA:AATheorem1-9理解:双射BAf:.,11BAIffIffxxabc123abcf1f123abc1231ffTheorem1-10(1)若f和g是单射,则f◦g是单射.(2)若f和g是满射,则f◦g是满射.(3)若f和g是双射,则f◦g是双射.Proof(2)任意zC,由于g是满射,存在yB,使得z=g(y).又由于f是满射,存在xA,使得y=f(x).于是z=g(y)=g(f(x))=(f◦g)(x).故f◦g是满射(seebelow)..:,:CBgBAfTheorem1-11(1)若f◦g是单射,则f是单射,g不一定.(2)若f◦g是满射,则g是满射,f不一定.(3)若f◦g是双射,则f是单射且g是满射.Proof(1)任意x1,x2A,若f(x1)=f(x2),x)(xfyzyg)())((xgfz.:,:CBgBAf显然,g(f(x1))=g(f(x2)),即(f◦g)(x1)=(f◦g)(x2).由于f◦g是单射,因此x1=x2.故f是单射.g不一定(见上图)?ab123gfABC一般来说f◦gg◦f,但Theorem1-12作业习题1.2:3,4,7,8,12.Hint7.使用定理1-10和第3题.8.使用第7题结论.12.使用第7题结论..)()(hgfhgfhgf1.3运算的定义及性质运算是讨论对象之间有何联系的一种方法.其实，我们已经接触过很多运算,如数之间的加法运算、多项式之间的乘法运算、矩阵的逆运算、向量的线性运算等.在讨论离散数据结构时也会经常遇到各种各样的运算，如在下节即将研究的集合间的运算.虽然运算本质上是映射，但研究的侧重点不同，在运算中更注重于运算满足的一些运算性质，而根据这些性质可以对一些离散对象分门别类进行讨论.因此，有必要先把运算的一般定义及其性质进行讨论.1.运算的定义(1)定义A1,A2,…,An到B的n元运算(n-aryoperation):A到B(或A上)的n元运算:A上的n元封闭运算(代数运算):BAAAfn...:21BAAAfn...:AAAAfn...:.),...,