当前位置:首页 >> 数学 >>

离散数学---二元关系和函数_图文

4.6 函数的定义与性质
?

函数的定义
? 函数定义
? 从A到B的函数 ? 函数的像

?

函数的性质
? 函数的单射、满射、双射性

? 构造双射函数

?

应用实例:问题描述
1

函数定义
定义 设 F 为二元关系, 若 ?x∈domF 都存在 唯一的y∈ranF 使 xFy 成立, 则称 F 为函数. 对于函数F, 如果有 xFy, 则记作 y=F(x), 并称 y 为 F 在 x 的值. 例1 F1={<x1,y1>,<x2,y2>,<x3,y2>} F2={<x1,y1>,<x1,y2>} F1是函数, F2不是函数
2

函数相等
定义 设F, G为函数, 则 F = G ? F?G∧G?F 如果两个函数 F 和 G 相等, 一定满足下面两个条件: (1) domF = domG (2) ?x∈domF = domG 都有 F(x) = G(x)
实例 函数 F(x)=(x2?1)/(x+1), G(x)=x?1 不相等, 因为 domF?domG.
3

从 A 到 B 的函数
定义 设A, B为集合, 如果 f 为函数 domf = A ranf ? B, 则称 f 为从A到B的函数, 记作 f:A→B. 实例 f:N→N, f(x)=2x 是从 N 到 N 的函数 g:N→N, g(x)=2也是从 N 到 N 的函数
4

B上 A
定义 所有从 A 到 B 的函数的集合记作 BA, BA ={ f | f:A→B }
计数: |A|=m, |B|=n, 且m, n>0, |BA|=nm. A=?, 则 BA=B?={?}. A≠?且B=?, 则 BA=?A= ?.
5

读作“B上A”,符号化表示为

实例
例2 设 A = {1, 2, 3}, B = {a, b}, 求BA. 解 BA = {f0, f1, … , f7}, 其中 f0={<1,a>,<2,a>,<3,a>}, f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>},f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>},f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>}, f7={<1,b>,<2,b>,<3,b>}
6

函数的像
定义 设函数 f:A→B, A1?A. A1 在 f 下的像: f(A1) = { f(x) | x∈A1 } 函数的像 f(A) 注意:函数值 f(x)∈B, 而像 f(A1)?B.
x/2 例3 设 f:N→N, 且 f ( x ) ? ? ? 若x为偶数 ? x ? 1 若x为奇数

令A={0,1}, B={2}, 那么有 f(A) = f({0,1}) = { f(0), f(1) } = {0, 2}

7

函数的性质
定义 设 f:A→B, (1)若ranf = B, 则称 f:A→B是满射的. (2)若 ?y∈ranf 都存在唯一的 x∈A使得 f(x)=y, 则称 f:A→B是单射的. (3)若 f:A→B既是满射又是单射的, 则称 f: A→B是双射的
f 满射意味着:?y ?B, 都存在 x?A 使得 f(x) = y. f 单射意味着:f(x1) = f(x2) ? x1= x2
8

实例
例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+为正实数集.
9

实例(续)
解 (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(1.5)=f(1.2)=1. (4) f:R→R, f(x)=2x+1 满射、单射、双射, 因为它是单调的并且ranf=R. (5) f:R+→R+, f(x)=(x2+1)/x 有极小值f(1)=2. 该函数既不单射也不满射.
10

构造从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
11

构造从A到B的双射函数(续)
实数区间之间构造双射
构造方法:直线方程

例6 A=[0,1]
B=[1/4,1/2] 构造双射 f :A→B 解 令 f:[0,1]→[1/4,1/2] f(x)=(x+1)/4
12

构造从A到B的双射函数(续)
A 与自然数集合之间构造双射
方法:将A中元素排成有序图形,然后从第一个元素开始 按照次序与自然数对应 例7 A=Z, B=N,构造双射 f:A→B 将Z中元素以下列顺序排列并与N中元素对应: Z:0 ?1 1 ?2 2 ?3 3 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N:0 1 2 3 4 5 6…

?0 ? 2x f:Z ? N, f ( x ) ? ? ?? 2 x ? 1 x ? 0
13

常函数、恒等函数、单调函数
1. 设f:A→B, 若存在 c∈B 使得 ?x∈A 都有 f(x)=c, 则称 f:A→B是常函数. 2. 称 A 上的恒等关系 IA为 A 上的恒等函数, 对所有 的 x∈A 都有 IA(x)=x. 3. 设 f:R→R,如果对任意的 x1, x2∈R,x1<x2, 就 有 f(x1) ? f(x2), 则称 f 为单调递增的;如果对任意 的 x1, x2∈A, x1< x2, 就有 f(x1) < f(x2), 则称 f 为 严 格单调递增 的. 类似可以定义单调递减 和严格单调递减 的函数.
14

集合的特征函数
4. 设 A 为集合, ?A’ ?A, A’ 的 特征函数 ?A’:A→{0,1} 定义为
?1, a ? A' ? A' (a ) ? ? ? 0, a ? A ? A'

实例 集合:X ={ A, B, C, D, E, F, G, H }, 子集:T = { A, C, F, G, H } T 的特征函数?T : x A B C D E F G ?T(x) 1 0 1 0 0 1 1

H 1
15

自然映射
5. 设 R 是 A 上的等价关系, 令 g:A→A/R g(a) = [a], ?a∈A 称 g 是从 A 到商集 A/R 的自然映射.

16

实例
例8 (1) A的每一个子集A’都对应于一个特征函 数, 不同的子集对应于不同的特征函数. 例如 A={a, b, c}, 则有 ?? = { <a,0>, <b,0>, <c,0> }, ?{a,b} = { <a,1>, <b,1>, <c,0>} (2) 给定集合 A, A 上不同的等价关系确定不同 的自然映射, 其中恒等关系确定的自然映射是双 射, 其他的自然映射一般来说是满射. 例如 A={1, 2, 3}, R={<1,2>,<2,1>}∪IA g(1) = g(2) = {1,2}, g(3) = {3}
17

4.7 函数的复合与反函数
?

函数的复合
? 函数复合的定理 ? 函数复合的性质

?

反函数
? 反函数存在的条件

? 反函数的性质

18

函数复合的定理
定理 设F, G是函数, 则F?G也是函数, 且满足 (1) dom(F?G)={ x | x∈domF ? F(x)∈domG} (2) ?x∈dom(F?G) 有 F?G(x) = G(F(x))

推论1 设F, G, H为函数, 则 (F?G)?H 和 F?(G?H) 都是函数, 且 (F?G)?H = F?(G?H) 推论2 设 f:A→B, g:B→C, 则 f?g:A→C, 且 ?x∈A 都有 f?g(x) = g(f(x)).

19

函数复合运算的性质
定理 设 f:A→B, g:B→C. (1) 如果 f:A→B, g:B→C 都是满射的, 则 f?g:A→C也是满射的. (2) 如果 f:A→B, g:B→C 都是单射的, 则 f?g:A→C也是单射的. (3) 如果 f:A→B, g:B→C 都是双射的, 则 f?g:A→C也是双射的. 证 (1) ?c∈C, 由 g:B→C 的满射性, ?b∈B 使得 g(b)=c. 对这个b, 由 f:A→B 的满射性,?a∈A 使得 f(a)=b. 由合成定理有 f?g(a)=g(f(a))=g(b)=c 从而证明了 f?g:A→C是满射的.
20

函数复合运算的性质
(2) 假设存在 x1, x2∈A使得 f?g(x1) = f?g(x2) 由合成定理有 g(f(x1))=g(f(x2)). 因为 g:B→C是单射的, 故 f(x1)=f(x2). 又由 于 f:A→B也是单射的, 所以 x1=x2. 从而证 明 f?g:A→C是单射的. (3) 由 (1) 和 (2) 得证.
定理 设 f: A?B,则 f = f?IB = IA?f
21

反函数存在的条件
任给函数 F, 它的逆F ?1不一定是函数, 是二元关系. 实例:F={<a,b>,<c,b>}, F ?1={<b,a>,<b,c>} 任给单射函数 f:A→B, 则 f ?1是函数, 且是从 ranf 到 A的双射函数, 但不一定是从 B 到 A 的双射函 数. 实例:f : N →N, f(x) = 2x, f ?1 : ranf →N, f ?1 (x) = x/2

22

反函数
定理 设 f:A→B是双射的, 则f ?1:B→A也是双射的. 证 因为 f 是函数, 所以 f ?1 是关系, 且 dom f ?1 = ranf = B , ran f ?1 = domf = A, 对于任意的 y∈B = dom f ?1, 假设有x1, x2∈A使得 <y,x1>∈f ?1∧<y,x2>∈f ?1 成立, 则由逆的定义有 <x1,y>∈f∧<x2,y>∈f 根据 f 的单射性可得 x1 = x2, 从而证明了f ?1是函数,且是 满射的. 下面证明 f ?1 的单射性. 若存在 y1, y2∈B 使得 f ?1 (y1) = f ?1 (y2) = x, 从而有 <y1,x>∈f ?1∧<y2,x>∈f ?1 ? <x,y1>∈f∧<x,y2>∈f ? y1 = y2
23

反函数的定义及性质
对于双射函数f:A→B, 称 f ?1:B→A是它的反 函数.

反函数的性质 定理 设 f:A→B是双射的, 则 f ?1?f = IB, f?f ?1 = IA
对于双射函数 f:A→A, 有 f ?1?f = f?f ?1 = IA
24

函数复合与反函数的计算
例设

? x2 f ( x) ? ? ?? 2

f:R→R, g:R→R

x?3 x?3

g( x ) ? x ? 2

求 f ? g, g ? f. 如果 f 和 g 存在反函数, 求出它们的反函数.

f ? g:R ? R ? x2 ? 2 f ? g( x ) ? ? ?0 x?3 x?3

g? f :R ? R ? ( x ? 2) 2 g ? f ( x) ? ? ?? 2 x?1 x?1

f:R→R不是双射的, 不存在反函数. g:R→R是双射的, 它 的反函数是 g?1:R→R, g?1(x) = x?2
25

问题描述——多机调度
问题: 有2台机器c1, c2; 6项任务t1, t2, …, t6. 每项任务的加工时间分别为: l(t1)=l(t3)=l(t5)=l(t6)=1, l(t2)=l(t4)=2 任务之间的顺序约束是: 任务t3只有在t6和t5完成之后才能开始加工; 任务t2只有在t6, t5和t4都完成后才能开始加工; 任务t1只有在t3和t2完成之后才能开始加工. 调度:任务安排在机器上加工的方案 截止时间:开始时刻0,最后停止加工机器的停机时刻
26

t5

t6

t4

两个调度方案
t3 t1 t2

t6 t5 t4 t3

t4

t2

t1 D=6

t2

t1 D=5
27

t6

t5

t3

问题描述
?

集合
任务集 T={t1, t2, ... , tn}, n?Z+ 机器集 M={c1, c2, ... , cm},m?Z+ 时间集 N

?

函数和关系
加工时间——函数 l:T?Z+. 顺序约束 R ——T上的偏序关系,定义为

R={<ti, tj>| ti, tj?T, i=j 或 ti完成后tj 才可以开始加工}

28

问题描述(续)
?

可行调度
分配到机器: T 的 划分 ?={T1, T2, ... , Tm},划分块Tj 是T 的非空子集, 由安排在机器cj上加工的所有任务组成.
?

每个机器上的任务开始时间 ?Tj??,存在调度函数 ?j:Tj?N, 满足以下条件: (1) 任意时刻 i,每台机器上正在加工至多1个任务 ?i, 0 ? i<D, | { tk | tk?Tj, ?j(tk)?i<?j(tk)+l(tk) }| ?1, j=1, 2, …, m
?

(2) 任务的安排满足偏序约束 ?ti?Ti, tj?Tj, <ti,tj>?R? ?i(ti)+l(ti)??j(tj) i, j=1, 2, …, m
29

问题描述(续)
机器 j 的停止时间 Dj=max{?j(tk)| tk?Tj}+l(tk) 所有任务的截止时间 D=max{Dj | j=1,2,...,m}.

我们的问题就是确定使得D达到最小的可行调度.

30


相关文章:
离散数学---二元关系和函数_图文.ppt
离散数学---二元关系和函数 - 4.6 函数的定义与性质 ? 函数的定义 ?
离散数学---二元关系和函数4.1-2_图文.ppt
离散数学---二元关系和函数4.1-2 - 第4章 二元关系与函数 4.1 集合
离散数学_第四章:二元关系和函数_图文.ppt
离散数学_第四章:二元关系和函数 - 第4章 二元关系与函数 ? ? ? ? ?
《离散数学》二元关系和函数-2_图文.ppt
离散数学二元关系和函数-2 - 第4章 二元关系和函数 Relation 4
二元关系和函数_图文.ppt
二元关系和函数_数学_自然科学_专业资料。离散数学 第4章 二元关系和函数 4.
离散数学第四章二元关系和函数.ppt
离散数学第四章二元关系和函数_数学_自然科学_专业资料。二元关系和函数理学
离散数学 二元关系和函数-2.ppt
离散数学 二元关系和函数-2 隐藏>> 第4章 二元关系和函数 Re
离散数学第6章二元关系汇总._图文.ppt
9/20 关系的基本概念 关系的表示与运算 关系的性质与闭包 等价关系 次序关系 函数 150-4 电子科技大学离散数学课程组国家精品课程 双语示范课程 教学目标 ? ...
离散数学 二元关系和函数-1.ppt
离散数学 二元关系和函数-1 隐藏>> 第四章 二元关系和函数 二元
离散数学 二元关系_图文.ppt
离散数学 二元关系_数学_自然科学_专业资料。计算机科学学院 刘芳 第7章 二元关系 7.1 有序对与笛卡儿积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 ...
4-2 二元关系与函数_图文.ppt
4-2 二元关系与函数_理学_高等教育_教育专区。离散数学第五版教学PPT 请交
离散数学---二元关系和函数4.5.ppt
离散数学---二元关系和函数4.5 隐藏>> 4.5 等价关系与偏序
离散数学 集合的笛卡儿积与二元关系_图文.ppt
离散数学 集合的笛卡儿积与二元关系_数学_自然科学_专业资料。第4章 二元关系与函数 4.1 集合的笛卡儿积与二元关系 ? 4.2 关系的运算 ? 4.3 关系的性质 ? 4.4...
离散数学---二元关系和函数4.3-4.ppt
离散数学---二元关系和函数4.3-4 隐藏>> 4.3 关系的性质
第四章 二元关系和函数_图文.ppt
第四章 二元关系和函数_IT认证_资格考试/认证_教育专区。离散数学 第4章 二元关系和函数 4.1 集合的笛卡儿积与二元关系 4.2 关系的运算 4.3 关系的性质 4.4 ...
离散数学第四章二元关系和函数知识点总结.doc
离散数学第四章二元关系和函数知识点总结 - 集合论部分 第四章、二元关系和函数 4.1 集合的笛卡儿积与二元关系有序对 定义 由两个客体 x 和 y,按照一定的顺序...
离散数学---二元关系和函数4.6-7.ppt
离散数学---二元关系和函数4.6-7 隐藏>> 4.6 函数的定义
离散数学 4.2复合函数与逆函数_图文.ppt
离散数学 4.2复合函数与逆函数_数学_自然科学_专业资料。复习定义4-1.1 设X,...离散数学---二元关系和函... 暂无评价 30页 1下载券 喜欢此文档的还喜欢 ...
离散数学 函数的复合与反函数_图文.ppt
离散数学| 函数|离散数学 函数的复合函数_理学_高等教育_教育专区。离散数学...反函数函数存在的条件 反函数的性质 由于函数是一种特殊的二元关系, ...
CH4 二元关系和函数 2 关系的运算和关系的性质_图文.ppt
CH4 二元关系和函数 2 关系的运算和关系的性质_理学_高等教育_教育专区。离散数学 CH4 二元关系和函数 2 关系的运算和关系的性质 今日内容 ? ? ? ? 关系运算...