4.2特殊函数类.pdf

离散数学 Discrete Mathematics 4.2特殊函数类 张晓西北工业大学计算机学院 zhangxiao@nwpu.edu.cn 2011328 定义 定义定义4.2―1 设f 是从X到Y的函数. 定义定义 (a 如果f (X)=Y, 那么f 是满射的满射的(映到的). 满射的满射的 (b 如果x ≠x ′蕴含着f (x)≠f (x ′ (即f (x)=f (x ′ ，那么x =x ′ ，那么f 是 单射的单射的(一对一的). 单射的单射的 (c 如果f 是满射的且是单射的(一对一和映 到的 ，那么f 是双射的双射的. 双射的双射的 具有这些性质的函数分别叫做满射函数满射函数, 单射单射 满射函数满射函数 单射单射 函数函数和双射函数双射函数. 函数函数 双射函数双射函数 2011110 离散数学 2 单射的但不满射单射的但不满射 双射的双射的 单射的但不满射单射的但不满射 满射的但不单射满射的但不单射 双射的双射的 满射的但不单射满射的但不单射 终止于陪域的每一终止于陪域的每一 有且只有一条弧有且只有一条弧 终止于陪域的每一终止于陪域的每一 至少有一条弧终止至少有一条弧终止 有且只有一条弧有且只有一条弧 至少有一条弧终止至少有一条弧终止 元素的弧不多于一元素的弧不多于一 终止于陪域的每终止于陪域的每 元素的弧不多于一元素的弧不多于一 于陪域的每一个元于陪域的每一个元 终止于陪域的每终止于陪域的每 于陪域的每一个元于陪域的每一个元 条条 一元素一元素 条条 素素 一元素一元素 素素 图4.2―1 例例1 例例 (a 皮亚诺函数S :N→N, S(n)=n+1是单 射函数但不满射, S 的映象是N 的真子集 ｛1, 2, …｝. (b g : ［0, 1 ］→［a, b ］, 这里a ＜b, g(x)=(b－a x +a是双射函数. 3 2 (c h :R→R, f (x)=x +2x 是满射函数但 不单射. 因为每一水平线横截图形至少一 次, 而有些地方多于一次(参看图4.2―2). 图 4.2―2 特殊函数的合成 定理4.2―1 设g :X→Y和f :Y→Z是函数, f g是合 成函数. (a 如果f 和g是满射的, 那么f g是满射的. (b 如果f 和g是单射的, 那么f g是单射的. (c 如果f 和g是双射的, 那么f g是双射的. 证 (a