离散数学-----函数

这种对应所表示的函数是：
f:Z N ,f(x) 2 x 2x1
x0 x0
f是Z到N的双射函数。从而证明了Z≈N。
2020/8/5
32
8.5 集合的势
例2：N≈NE
▪ 解：构造函数f : N →NE
▪ 将N中元素以下列顺序排列并与NE中元素对应：
N 0 1 2 3 4 5…
NE 0 2 4 6 8 10 …
这种对应所表示的函数是：
f:N N E,f(x)2x
2020/8/5
f是N到NE的双射函数。从而证明了N≈NE。 33
8.5 集合的势
一个结论：
▪ 从上例可以看出：
N E N Z ， N E 但 N Z 。
这说明： ▪ 无限集合能与它的真子集等势，这在有限集合中是不可能
的。
▪ 这是无限集合与有限集合的本质区别之一。
（1）若ranf = B, 则称 f : A→B是满射的.
（2）若 y∈ranf 都存在唯一的 x∈A使得 f(x)=y, 则
称 f : A→B是单射的.
（3）若 f : A→B既是满射又是单射的, 则称 f : A→B
是双射的。
注:
(1) f 满射意味着：y B, 都存在 xA 使得 f(x)=y.
▪ f: (0,1) →（-π/2, π/2),f(x)= π(x- 1/2)，显然f为 双射
▪ g: (-π/2, π/2) →R,g(x)= tgx ，显然g为双射
▪ 于是f∘g : (0,1) → (π/2, π/2) , f∘g (x)=g(f(x)= tgπ(x- 1/2) ，也是双射函数
(2) f 单射意味着：f(x1)=f(x2) x1=x2
2020/8/5
9
8.2 函数的性质
例：
2020/8/5
10
8.2 函数的性质
例8.4 判断下面函数是否为单射, 满射, 双射的, 为什 么? （1）f : R→R, f(x)= x2+2x1 （2）f : Z+→R, f(x)=lnx （3）f : R→Z, f(x)=x （4）f : R→R, f(x)=2x+1
16
8.3 一些常用函数
例：
▪ 已知 A={1, 2, 3}上的等价关系如下，确定A到相
应商集的自然映射。
▪ R1={<2,3>,<3,2>}∪IA ▪ R2={<1,3>,<3,1>}∪IA ▪ R3={<1,2>,<2,1>}∪IA ▪ R4=EA ▪ R5=IA
2020/8/5
17
8.3 一些常用函数
2020/8/5
f6={<1,1>,<2,1>,<3,0>}, f7={<1,1>,<2,1>,<3,1>}.
27
8.5 集合的势
▪ 令 f : A→B,
▪ f()=f0 ▪ f({2})=f2 ▪ f({1,2})=f4 ▪ f({2,3})=f6
▪ 故： A≈B
f({1})=f1 f({3})=f3 f({1,3})=f5 f({1,2,3})=f7
f7={<1,b>,<2,b>,<3,b>}
2020/8/5
6
8.1 函数的定义
3.B上A
▪定义8.4
▪ 所有从A到B的函数的集合记作BA，读作“B上 A”即：
BA＝{f | f : A→B}
思考：设|A|=m,|B|=n,则|BA|=？
2020/8/5
7
8.1 函数的定义
解：
▪ 设：A={x1, x2, …,xm}, B={y1, y2, …,yn}, ▪ 则集合A到B的函数f形如：
2020/8/5
4
8.1 函数的定义
▪例2：判断下列关系中哪些能构成函数？
▪（1）f＝{<x,y>|x,y∈N, x＋y＜10} ▪（2）f＝{<x,y>|x,y∈R, x＝y2} ▪（3）f＝{<x,y>|x,y∈N, y＝x＋1}
2020/8/5
5
8.1 函数的定义
例3：
▪ 设A ＝ {1, 2, 3}, B ＝ {a, b}，则A到B共有多少个不
▪ (2) 若A≈B，则B≈A
▪ (3) 若A≈B，B≈C，则A≈C。
2020/8/5
26
8.5 集合的势
如何证明A≈B？ ▪ 构造从A到B的双射函数
1.有穷集之间的双射函数的构造
▪ 例1： A=P({1,2,3}), B={0,1}{1,2,3}
▪ 解：A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.
则称 f 为严格单调递增的.
▪ 单调递减 ▪ 严格单调递减
2020/8/5
14
8.3 一些常用函数
(4) 设 A 为集合, 对于任意的 A’ A, A’ 的特征 函数 A’ : A→{0,1} 定义为
实例：
A'(a)10,,
aA' aAA'
设A={a,b,c}, A的每一个子集 A'都对应于一个
特征函数, 不同的子集对应于不同的特征函数. 如
A ≤.B
▪ f为双射的，则 |A|＝|B|。 A≈B
▪ f是单射的，且不存在A到B的双射，则|A|＜|B|。
A ＜.B
2020/8/5
25
8.5 集合的势
例如:
▪ |N|≤|R|
▪ 定义f:N →R，f(x)=x，显然f为单射函数，所以|N|≤|R|。 定理8.6
▪ 设A，B，C是任意集合，
▪ (1) A≈A
是满射的, 但不是单射的, 例如 f(1.5)=f(1.2)=1.
(4) f : R→R, f(x)=2x+1
是满射、单射、双射的, 因为它是单调函数并且ranf=R.
2020/8/5
12
8.3 一些常用函数
定义8.7
▪ (1) 设f：A→B, 如果存在 c∈B 使得对所有的
x∈A 都有 f(x)=c, 则称 f : A→B是常函数.
▪ (2) 称 A 上的恒等关系 IA为 A 上的恒等函数, 对所
有的x∈A 都有 IA(x)=x.
2020/8/5
13
8.3 一些常用函数
(3) 设f : A→B，
▪ 如果对任意的 x1, x2∈A, x1≺x2, 就有 f(x1) ≼ f(x2),
则称 f 为单调递增的；
▪ 如果对任意的 x1, x2∈A, x1≺x2, 就有 f(x1) ≺ f(x2),
同的函数？分别列出来。
▪ 解：
f0={<1,a>,<2,a>,<3,a>} , f2={<1,a>,<2,b>,<3,a>} , f4={<1,b>,<2,a>,<3,a>},
f6={<1,b>,<2,b>,<3,a>} ,
f1={<1,a>,<2,a>,<3,b>} f3={<1,a>,<2,b>,<3,b>} f5={<1,b>,<2,a>,<3,b>}
2020/8/5
34
8.5 集合的势
例3： N×N≈N
▪ 解：分析
f :NNN f (m,n) (mn1)(mn) m
在 x 的值.
例如
▪ f1＝{<x1,y1>,<x2,y2>,<x3,y2>}
▪ f2＝{<x1,y1>,<x1,y2>}
2020/8/5
2
8.1 函数的定义
从A到B的函数
▪ 定义8.3
▪设A, B为集合, 如果 ▪ (1) f 为函数 ▪ (2) domf = A ▪ (3) ranf B,
▪则称 f 为从A到B的函数, 记作 f : A→B.
2020/8/5
▪ 故： (0,1) ≈ R
30
8.5 集合的势
3.A与N之间构造双射
▪方法：
▪ 将A中元素排成有序图形，然后从第一个元素 开始按照次序与自然数对应.
2020/8/5
31
8.5 集合的势
例1：Z≈N
▪ 解：构造函数f : Z→N
▪ 将Z中元素以下列顺序排列并与N中元素对应： Z：0 1 1 2 2 3 3 … ↓↓↓↓↓ ↓↓ N：0 1 2 3 4 5 6 …
▪f＝{<x1,□>， {<x2,□>，…… {<xm,□>} ▪对于每个□所在的 位置都可用B中的任何一个
元素代替，即有n种不同的取法，这样的组合 共有nm个。
▪因此A到B共有nm个不同的函数,即： |BA|= |B||A| 。
2020/8/5
8
8.2 函数的性质
定义8.6 设 f : A→B,
推论2 设f : A→B, g : B→C, 则 f∘g : A→C, 且x∈A都有
f∘g(x) = g(f(x)).
2020/8/5
21
8.4 函数的复合和反函数
函数复合的性质
定理8.2 设 f : A→B, g : B→C.
▪ (1) 如果 f : A→B, g : B→C都是满射的, 则 f∘g :
2020/8/5
11
8.2 函数的性质
解 (1) f : R→R, f(x)= x2+2x1
在x=1取得极大值0. 既不是单射也不是满射的.