离散数学 教学课件 作者 李盘林 第05章.ppt

《离散数学 教学课件 作者 李盘林 第05章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章函数5.1函数基本概念5.2函数类型5.3函数运算5.4基数退出5.1函数基本概念函数也常称为映射或变换，其定义如下：定义5.1.1设A和B是任意两个集合，且F是从A到B的关系，若对每一个xA，都存在唯一的yB，使F，则称F为从A到B的函数，并记作F:AB。A称为函数F的定义域，即D(F)=A，B称为函数F的陪域，R(F)称为函数F的值域，且R(F)B。有时也用F(A)表示函数F的值域，即F(A)=R(F)={y

2、yB(x)(xAy=F(x))}并称F(A)为函数

3、F的像。对于F:AB来说，若F，则称x为函数的自变元，称y为函数因变元，因为y值依赖于x所取的值，或称y是F在x处的值，或称y为F下x的像。通常把F记作F(x)=y。从本定义可以看出，从A到B的函数F和一般从A到B的二元关系之不同有以下两点：①A的每一元素都必须是F的有序对之第一分量。②若F(x)=y，则函数F在x处的值是唯一的，即F(x)=yF(x)=zy=z考虑到习惯用法，以下常常将大写函数符号F改为小写字母f。定义5.1.2设f:AB，g:CD，若A=C，B=

4、D，且对每一xA都有f(x)=g(x)，则称函数f和g相等，记为f=g。本定义表明了，两函数相等，它们必须有相同的定义域、陪域和有序对集合。有时需要缩小所给函数的定义域，或扩大所给函数的定义域以创建新的函数，为此有下面定义。定义5.1.3设f:AB，且CA，若有g=f∩(CB)则称g是f到C的缩小，记为f

5、c，即g为C到B的函数：g:CBg(x)=f(x)或f

6、c(x)=f(x)定义5.1.4设f:CB，g:AB，且CA，若g

7、c=f，则称g是f到A的扩大。下面讨论由集合A和B，构成

8、这样函数f:AB会有多少呢？或者说，在AB的所有子集中，是全部还是部分子集可以定义函数？令BA表示这些函数的集合，即BA={f

9、f:AB}设

10、A

11、=m，

12、B

13、=n，则

14、BA

15、=nm。这是因为对每个自变元，它的函数值都有n种取法，故总共有nm种从A到B的函数。上面介绍一元函数，下面给出多元函数的定义。定义5.1.5设A1,A2,···,An和B为集合，若f:AiB为函数，则称f为n元函数。在上的值用f(x1,x2,···,xn)表示。一元函数中概念对n元函数几乎完全

16、适用，在这里不多讨论了。5.2函数类型根据函数具有的不同性质，可以将函数分成不同的类型。本节将定义这些函数，并给出相应的术语。定义5.2.1设f:AB是函数，若R(f)=B，或对任意bB，存在aA，使得f(a)=b，或形式表为：(y)(yB(x)(xAf(x)=y))则称f:AB是满射函数，或称函数f:AB是满射的。本定义表明了，在函数f的作用下，B中每个元素b，都至少是A中某元素a的像，因此，若A和B是有穷集合，存在满射函数f:AB，则

17、A

18、≥

19、B

20、。定义5.2.2设f:A

21、B是函数，对任意的a，bA，且ab，都有f(a)f(b)，或形式表为(x)(y)(x,yAxyf(x)f(y))则称f:AB是单射函数（或一对一函数），或称函数f:AB是单射的，或入射的。本定义揭示了，A中不同的元素，其在B中像也是不同的。于是，若A的B是有穷集合，存在单射函数f:AB，则

22、A

23、≤

24、B

25、。定义5.2.3设f:AB是函数，若f既是满射又是单射，则称f:AB是双射函数（或一一对应），或称函数f:AB是双射的。该定义说明了，B中的每个元素b是且仅是A中某个

26、元素a的像。因此，若A和B是有穷集合，存在双射函数f:AB，则

27、A

28、=

29、B

30、。定义5.2.4设f:AB是函数，若存在bB，使对任意aA有f(a)=b，即f(A)={b}，则称f:AB为常值函数。定义5.2.5设f:AA是函数，若对任意aA，有f(a)=a，亦即f={

31、xA}则称f:AA为A上恒等函数，通常记为IA，因为恒等关系即是恒等函数。由定义可知，A上恒等函数IA是双射函数。定义5.2.6设A和B为集合，且AB，若函数A:B{0,1}为1xAxA(x)=0否则

32、则称xA为集合A的特征函数。{特征函数建立了函数与集合的一一对应关系。于是，可通过特征函数的计算来研究集合上的命题。定理5.2.1设A和B是全集合U的任意两个子集。对任意xU，则下列关系式成立。①A(x)=0A=②A(x)=1A=U③A(x)≤B(x)AB④A(x)=B(x)A=B⑤A’(x)=1-A(x)⑥A∩B(x)=xA(x)*xB(x)⑦A∪B(x)=A(x)+B(x)-A∩B(x)⑧A-B(x)=A∩B’(x)=