离散数学 第4章函数

离散数学,通用

第 4章 函 数§1 函数的概念 §2 逆函数和复合函数 §4 基数的概念§5 可数集与不可数集

§6 基数的比较

离散数学,通用

§4-1 函数的概念函数是一种特殊的关系。也就是说，函数是 一种特定类型的二元关系。本章讨论的是离散函 数，它能把一个有穷集合变换到另一个有穷集合。例：在计算机上执行程序可以看作是函数的变换： (自变量)输入-----计算机-----输出(函数值)

离散数学,通用

§4-1 函数的概念一、函数的定义定义1 设X和Y是任意两个集合，f是从X→Y的一种关 系，若对于每一个x∈X,都存在一个唯一的 y∈Y,能使 <x,y>∈f ,则称关系 f 为函数(映

射),记作： f:X→Y 或 X

f

Y。

离散数学,通用

§4-1 函数的概念讨论定义： (1)f:X→Y中，若<x, y> f ,则称x为自变元，与 x对应的y称作f作用下的象；也可用y=f(x)表示 <x,y> f ,y称作函数f在x点处的值。 (2)X中每一个元素均有定义，

∴函数f的定义域是dom f =X,不能是X的真子集

离散数学,通用

§4-1 函数的概念(3)对应于某一个x X ,其值f(x)是唯一的，即 <x, y> f <x, z> f y=z (4)f 的值域ran f Y,有时也记为Rf 。

Rf ={ y | x (x X y=f (x) )}集合Y称为f 的共域， ran f 也称为函数的象集合

离散数学,通用

§4-1 函数的概念例：判定下列关系是否为函数

Df=X Rf Y 是函数

Df X 不是函数

值不是唯一的 不是函数

离散数学,通用

§4-1 函数的概念例：设X=Y=R(实数)

(1) f { x, y | x, y R y x 2}

Df R, y x2 值是唯一的(2) g { x, y | x, y R x y 2}

x y

2

这不是函数

离散数学,通用

§4-1 函数的概念定义2 设f:A B,g:C D,若A=C,B=D,且对每一x A都有f(x)=g(x),则称函数f 和g相等， 记为f = g。

离散数学,通用

§4-1 函数的概念例：设X={a,b,c},Y={0,1},则 X Y={<a,0> <a,1> <b,0> <b,1> <c,0> <c,1>} X Y中，有26=64个子集，但64个子集中只有8个(23) 函数 abc f 0 { a,0 b,0 c,0 } 000 abc f2 010 abc f4 100 abc f6 110

abc f1 001 abc f3 011 abc f5 101 abc f7 111

离散数学,通用

§4-1 函数的概念讨论：从此例中可得到三点结论：

(1)设|X|=m,|Y|=n,则函数 f : X→Y中均是m个序偶的集合；(即序偶个数=定义域的基数) (2)X中每一个元素所对应的象点 f(x)可能是Y中n 个元素中的一个。 从X → Y的所有函数个数:

| Y | n | Y |X m

|X |

离散数学,通用

§4-1 函数的概念(3)X→Y函数的个数和X Y子集个数的关系为：

| Y X | nm | X Y | 2m n即二个集合之间能构成的函数个数比能构成的二 元关系数少

得多

离散数学,通用

§4-1 函数的概念二、几种特殊函数 定义3:给定函数 f: X→Y,如果值域ran f =Y,即 Y的每一个元素是X中一个或多个元素的象点，

则称 f 为满射函数。例： 满射函数一定有：

(1) ran f =Y(2) |X|≥|Y|12

离散数学,通用

§4-1 函数的概念定义4 :给定 f : X→Y,X中没有两个元素有相同 的象，则称 f 是入射函数(一对一映射)。

如果有 x1 x2 f ( x1 ) f ( x2 ) 或者： f ( x1 ) f ( x2 ) x1 x2

离散数学,通用

§4-1 函数的概念例：

入射函数有：(1) ran f Y (2) |X| ≤ |Y|14

离散数学,通用

§4-1 函数的概念定义5 :给定函数 f: X→Y,如果 f 既是满射函数，

又是入射函数，则称f为双射函数。 (或一一对应函数 ) 例： 双射函数一定有： (1) ran f =Y (2) |X|=|Y|

离散数学,通用

§4-1 函数的概念例：在全班同学的集合中，设X={学号},Y={姓名}

则 f: X→Y是一双射函数(学号和姓名的关系) 定理1:令X和Y为有限集，若X和Y的元素个数相 同，即|X|=|Y|,则 f: X→Y是入射的，当且 仅当它是一个满射。