离散数学二元关系和函数.ppt

关于离散数学二元关系和函数
第1页，讲稿共36张，创作于星期二
在高等数学中，函数是在实数集合上进行讨论的，其定义域是连续的。
本章把函数概念予以推广
⑴定义域为一般的集合，支持离散应用。
⑵把函数看作是一种特设 f：N→N, 且
令A={0,1}, B={2}, 那么有 f(A) = f({0,1}) = { f(0), f(1) } = {0, 2}

第10页，讲稿共36张，创作于星期二
函数的性质
定义 设 f：A→B,（1）若ranf = B, 则称 f：A→B是满射的.（2）若任意x1， x2 A 而且不相等，都有f(x1)与
f(x2)不相等, 则称 f：A→B是单射的.（3）若 f：A→B既是满射又是单射的, 则称 f：
A→B是双射的
f 满射意味着：y B, 都存在 x使得 f(x) = y.
f 单射意味着：f(x1) = f(x2)  x1= x2

第11页，讲稿共36张，创作于星期二
注意：
①由单射的定义可知，设X和Y是有限集合，若存在单射函数f:X→Y，则|X|≤|Y|。
②由满射的定义可知，设X和Y是有限集合，若存在满射函数f:X→Y，则|X|≥|Y|。
③由双射的定义可知，设X和Y是有限集合，若存在双射函数f:X→Y，则|X|=|Y|。

第12页，讲稿共36张，创作于星期二
实例
例4
判断下面函数是否为单射, 满射, 双射的, 为什么? (1) f：R→R, f(x) = x2+2x1 (2) f：Z+→R, f(x) = lnx, Z+为正整数集 (3) f：R→Z, f(x) = x (4) f：R→R, f(x) = 2x+1 (5) f：R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集.

第13页，讲稿共36张，创作于星期二
解 (1) f：R→R, f(x)=x2+2x1
在x=1取得极大值0. 既不单射也不满射. (2) f：Z+→R, f(x)=lnx
单调上升, 是单射. 但不满射, ranf={ln1, ln2, …}.
(3) f：R→Z, f(x)= x
满射, 但不单射, 例如 f()=f()=1. (4) f：R→R, f(x)=2x+1
满射、单射、双射, 因为它是单调的并且ranf=R. (5) f：R+→R+, f(x)=(x2+1)/x
有极小值f(1)=2. 该函数既不单射也不满射.
实例（续）

第14页，讲稿共36张，创作于星期二
构造从A到B的双射函数
有穷集之间的构造
例5 A=P({1,2,3}), B={0,1}{1,2,3}
解 A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
 B={ f0, f1, … , f7 }, 其中 f0={<1,0>,<2,0>,<3,0>}, f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}, f3={<1,0>,<2,1>,<3,1>}, f4={<1,1>,<2,0>,<3,0>}, f5={<1,1>,<2,0>,<3,1>}, f6={<1,1>,<2,1>,<3,0>}, f7={<1,1>,<2,1>,<3,1>}.
令 f：A→B,
f()=f0, f({1})=f1, f({2})=f2, f({3})=f3,
f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7

第15页，讲稿共36张，创作于星期二
实数区间之间构造双射
构造方法：直线方程
例6 A=[0,1]
B=[1/4,1/2]构造双射 f :A→B
构造从A到B的双射函数（续）
解
令 f：[0,1]→[1/4,1/2]
f(x)=(x+1)/4

第16页，讲稿共36张，创作于星期二
构造从A到B的双射函数（续）
A 与自然数集合之间构造双射
方法：将A中元素排成有序图形，然后从第一个元素开始