2009-7-29 离散数学 1
第四章 二元关系和函数
§ 4.1 集合的笛卡尔积与二元关系
§ 4.2 关系的运算
§ 4.3 关系的性质
§ 4.4 关系的闭包
§ 4.5 等价关系和偏序关系
§ 4.6 函数的定义和性质
§ 4.7 函数的复合和反函数
2009-7-29 离散数学 2
§ 4.1 集合的笛卡尔积与二元关系一、二元关系的概念有序对（序偶）,由两个元素 x 和 y 按一定顺序排成的二元组。记作,< x,y >。其中 x是它的第一元素,y是它的第二元素。
特点,(1)当 x?y 时,< x,y >? < y,x >
(2) < x,y > = < u,v > 当且仅当 x = u,y = v
(1)(2)说明有序对区别于集合。
如平面直角坐标系点的坐标。
2009-7-29 离散数学 3
一、二元关系的概念（续）
n 元有序对,第一元素是一个 n –1元 有序对的有序对。
记作,< x1,x2,…,xn >。
即 < x1,x2,…,xn > = << x1,…,xn-1 >,xn >
笛卡尔积,设 A,B为两集合,以 A中元素为第一元素,B中元素为第二元素构成的二元有序对的全体叫做 A和 B的笛卡儿积。
记作,A? B
符号化 A? B = { < x,y > | x?A? y?B }
2009-7-29 离散数学 4
一、二元关系的概念（续）
例 1：设 A = { a,b },B = { 0,1,2 },求 A? B,B? A。
解：由笛卡尔积的定义知
A? B = { < a,0 >,< a,1 >,< a,2 >,
< b,0 >,< b,1>,< b,2> }
B? A = { < 0,a >,< 0,b >,
< 1,a >,< 1,b >,
< 2,a >,< 2,b> }
一般地，若 |A| = m,|B| = n,则 |A? B| = |B? A| = mn
2009-7-29 离散数学 5
一、二元关系的概念（续）
笛卡尔积运算的性质：
(1)如果 A,B中有一个空集，则笛卡儿积是空集，
即, B = A =?
(3)当 A,B,C都不是空集时，有 (A? B)? C?
A? ( B? C)，即笛卡尔积不满足结合律。
(2)当 A? B,且 A,B都不是空集时，有 A? B? B? A,
即笛卡尔积不满足交换律。
2009-7-29 离散数学 6
一、二元关系的概念（续）
(4)笛卡尔积运算对 ∪ 或 ∩运算满足分配律，
即 A? (B∪ C) = (A? B)∪ (A? C)
(B∪ C)? A = (B? A)∪ (C? A)
A? (B∩C) = (A? B)∩(A? C)
(B∩C)? A = (B? A)∩(C? A)
证明,< x,y >? (B∪ C)? A? x?B∪ C? y?A
( x?B? x?C )? y?A
( x?B? y?A )? ( x?C? y?A )
( < x,y >? B? A )? ( < x,y >? C? A )
< x,y >?(B? A)∪ (C? A)
2009-7-29 离散数学 7
一、二元关系的概念（续）
例 2：设 A = {1,2},求 P (A)? A。
解,P (A)? A
推广,n阶笛卡尔积
A1? A2?…? An
= {<x1,x2,…,xn > | x1?A1? x2?A2?…? xn?An }
= {?,{1},{2},{1,2} }? {1,2}
= { <?,1>,<?,2>,<{1},1>,<{1},2>,<{2},1>,
<{2},2>,< {1,2},1>,< {1,2},2> }
2009-7-29 离散数学 8
一、二元关系的概念（续）
二元关系 是指在集合中两个元素之间的某种相关性,
例如,家庭成员集合 {a,b,c,d}上的父子关系,
R={<a,c>,<a,d>},
二元关系的数学定义,如果一个集合为空集或者它的元素都是二元有序对，则这个集合称为一个二元关系，记作,R
如果 < x,y >? R,记作 x R y
如果 < x,y >? R,记作 x R y
2009-7-29 离散数学 9
一、二元关系的概念（续）
从 A到 B的二元关系,设 A,B为集合,A? B的任何子集所定义的二元关系叫做从 A到 B的二元关系。
设 A={a,b,c}代表三个人的构成的集合
B={1,2,3,4}代表四项工作构成的集合若 a从事工作 1,b从事工作 2,c从事工作 3,则人从事工作之间的关系可以表示为,
R={<a,1>,<b,2>,<c,4>} 为 A到 B的二元关系之一
2009-7-29 离散数学 10
特别地，若 A = B，叫作 A上的二元关系 。
若 |A| = n，则 |A? A| = n2,A? A的所有子集有 个，
因此,A上有 个不同的二元关系。
22n
22n
例如,家庭成员集合 A={a,b,c,d}上的成员分别代表 父、母、兄、
弟,则该集合上的各种关系为：
父子关系,{ <a,c>,<a,d> },
母子关系,{ <b,c>,<b,d> },
兄弟关系,。。。夫妻关系。。。 都是 A上的二元关系
2009-7-29 离散数学 11
一、二元关系的概念（续）
例 3：设 A = {a,b}，写出 P(A)上的包含关系 R? 。
解,P(A) = {?,{a},{b},{a,b} }
R = { <?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}> <{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}> }
空关系 即空集?
恒等关系 IA = { < x,x >| x?A}
全域关系 EA = { < x,y >| x?A? y?A }= A? A
A的 3种特殊关系,空关系,全域关系 EA,恒等关系 IA
2009-7-29 离散数学 12
二、二元关系的表示方法
1,关系矩阵设 A = { x1,x2,…,xn },R是 A上的关系，
rij =
1 若 xi R xj
0 若 xi R xj
令 (i,j = 1,2,…,n)
则 ( rij )n× n = 是 R的关系矩阵
nnnn
n
n
rrr
rrr
rrr
...
............
...
...
21
22221
11211
2009-7-29 离散数学 13
二、二元关系的表示方法（续）
2,关系图以 V = A = { x1,x2,…,xn }为顶点的集合,以
E = { < xi,xj > | xi?A? xj?A? xi R xj}为有向边的集合,组成的有向图 G = < V,E >。
例如,{x1,x2,x3}上的关系 R={<x1,x2>,<x1,x3>}
x1 x2
x3
2009-7-29 离散数学 14
二、二元关系的表示方法（续）
例 4：设 A = {1,2,3,4},R = { <1,2>,<1,3>,<2,2>,
<2,4>,<3,4>,<4,2> }是 A上的关系，试写出 R的关系矩阵并画出关系图。
解,关系矩阵
0010
1000
1010
0110
关系图
12
43
思考：写出例 3的关系矩阵和关系图
2009-7-29 离散数学 15
关系 R的定义域 (domain),
dom R = { x |? y(< x,y >?R) },
即 R中所有有序对的第一元素构成的集合。
一、关系的定义域与值域
§ 4.2 关系的运算关系 R的值域 (range)：
ran R = { y |? x(< x,y >?R) },
即 R中所有有序对的第二元素构成的集合。
关系 R的域 (field),fld R = dom R∪ ran R
2009-7-29 离散数学 16
一、关系的定义域与值域（续）
例 5：分别求出下列关系的定义域和值域。
(1) R1 = { < x,y > | x,y?Z? x? y };
(2) R2 = { < x,y > | x,y?Z? x2 + y2 = 1 };
(3) R3 = { < x,y > | x,y?{1,2,3,4}? x > y }
解,(1) dom R1 = ran R1 = Z
(2) R2 = {<0,1>,<0,-1>,<1,0>,< -1,0>}
(3) R3 = {<2,1>,<3,1>,<4,1>,<3,2>,<4,2>,<4,3>}
dom R2 = ran R2 = { 0,1,-1 }
dom R3 = { 2,3,4 },ran R3 = { 1,2,3 }
2009-7-29 离散数学 17
1,逆：
2,合成：
3,限制：
4,象：
任意两个关系 F与 G的合成，记作,F? G
F? G = { < x,y > |? z( xFz? zGy ) } (右复合 )
二、关系的常用运算
F是任意关系,F 的逆 F -1 ={ < x,y > | yFx }
关系 F在集合 A上的限制，记作,F | A
F | A = { < x,y > | xFy? x?A }
集合 A在 F 下的象，记作,F [A]
F [A] = ran (F | A)
2009-7-29 离散数学 18
例,设 F＝ {<3,3>,<6,2>},G={<2,3>,<3,6>}，
则 F-1 ＝ {<3,3>,<2,6>},
F?G＝ {<3,6>,{<6,3>},G?F＝ {<2,3>,<3,2>}
例,设 R＝ {<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}
R | {1}＝ {<1,2>,<1,3>}
R | {2,3}＝ {<2,2>,<2,4>},<3,2>}
R[{1}]＝ {2,3}
R[{3}]＝ {2}
2009-7-29 离散数学 19
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解,G–1 = { < y,x > | x,y?N? y = x + 1 }
列出 G –1中的元素即为
G –1 = {<1,0>,<2,1>,<3,2>,…,< x + 1,x >,… }
2009-7-29 离散数学 20
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解：为了求 F? G可以先直观表示如下：
对任何 x?N
x x 2 = z z+1 = yGF
因此 F? G = {< x,y > | x,y?N? y = x 2+ 1}
即 y = x 2+ 1
2009-7-29 离散数学 21
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解：为了求 G? F可以先直观表示如下：
对任何 x?N
x x+1 = z z 2 = yG F
因此 G? F = {< x,y > | x,y?N? y = （ x + 1） 2}
即 y = （ x+ 1） 2
2009-7-29 离散数学 22
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解,F | {1,2} = { <1,1>,<2,4> }
F [{1,2}] = ran (F | {1,2}) = { 1,4 }
2009-7-29 离散数学 23
三、关系运算的性质
1,(F –1)–1 = F
2,dom F –1 = ran F,ran F –1 = dom F
3,(F? G)? H = F? (G? H )
4,(F? G)–1 = G –1? F –1
5,F? (G∪ H) = (F? G)∪ (F? H)
6,F? (G∩H)? (F? G)∩(F? H)
8,(G∩H)? F? (G? F)∩(H? F)
7,(G∪ H)? F = (G? F)∪ (H? F)
2009-7-29 离散数学 24
三、关系运算的性质（续）
4,(F? G)–1 = G –1? F –1的证明。
对任意 < x,y >?(F? G)–1
< y,x >?F? G
z( < y,z >?F? < z,x >?G )
z( < z,y >?F –1? < x,z >?G–1 )
z( < x,z >?G –1?< z,y >?F –1 )
< x,y >?G –1? F –1
2009-7-29 离散数学 25
三、关系运算的性质（续）
6,F? (G∩H)? (F? G)∩(F? H)的证明。
对任意 < x,y >? F? (G∩H)
z(< x,z >?F? < z,y >? G∩H )
z(< x,z >?F? < z,y >?G? < z,y >?H )
z((<x,z>?F? <z,y>?G)? (<x,z>?F? <z,y>?H))
z(<x,z>?F?<z,y>?G) z(<x,z>?F?<z,y>?H)
< x,y >? F? G? < x,y >? F? H
< x,y >? (F? G)∩(F? H)
2009-7-29 离散数学 26
四、关系的幂运算设 R是 A上的关系,n为自然数，则：
(1) R0 = { < x,x > | x?A }
(2) Rn = Rn-1? R,n? 1
定理
(1) Rm? Rn = Rm + n
(2) (Rm)n = Rmn
其中 m,n为自然数。
2009-7-29 离散数学 27
求 R的各次幂的方法,
(1) 集合运算法 ;
R2 =R? R
(2) 关系图法 ;
根据 R的关系图求 R2
(3)关系矩阵法 ; | R n|= |R| n (逻辑加 )
x3x2x1 x
3x1
2009-7-29 离散数学 28
四、关系的幂运算（续）
例 7：设 A= { a,b,c,d },A上的一个关系
R = { < a,b >,< b,a >,< b,c >,< c,d > }
求 R0,R2,R3。
解,R0= { < a,a >,< b,b >,< c,c >,< d,d > }
由 R的关系图知
R2 = R? R = { < a,a >,< a,c >,
< b,b >,< b,d > }
ab
dc
R3 = { < a,b >,< a,d >,< b,a >,< b,c >}
2009-7-29 离散数学 29
R3 = R2? R = { <a,b>,<a,d>,<b,a>,<b,c>}
四、关系的幂运算（续）
例 7：设 A= { a,b,c,d },A上的一个关系
R = { < a,b >,< b,a >,< b,c >,< c,d > }
求 R0,R2,R3。
R2 = R? R = { <a,a>,<a,c>,<b,b>,<b,d> }
R的关系矩阵
,
0000
1000
0101
0010
M,
0000
0000
1010
0101
2
M
0000
0000
0101
1010
3M
2009-7-29 离散数学 30
§ 4.3 关系的性质
1、自反性,?x?A,有 <x,x>?R
设 R是 A上的关系
R的关系矩阵：主对角线元素全为 1
R的关系图：每个顶点都有环
2、反自反性,? x?A,有 <x,x>? R
R的关系矩阵：主对角线元素全为 0
R的关系图：每个顶点都没有环
2009-7-29 离散数学 31
3、对称性,若 <x,y>?R，则 <y,x>?R
R的关系矩阵：对称阵
R的关系图：若两个顶点间有边，则一定是一对方向相反的边。
4、反对称性,若 <x,y>?R且 x? y，则 <y,x>?R
R的关系矩阵：若 rij = 1，且 i? j，则 rji = 0
R的关系图：若两个顶点间有边，则一定是只有一条有向边。
关系的性质
2009-7-29 离散数学 32
5、传递性,若 <x,y>?R且 <y,z>?R，则 <x,z>?R
R的关系图：若顶点 xi 到 xj 有边,xj 到 xk 有边，
则 xi 到 xk 有边。
关系的性质
2009-7-29 离散数学 33
若 A中有三个元素 x,y,z,满足 xRy且 yRz，
即 (x? y)/3?Z且 (y? z)/3?Z,则有 (x? z)/3?Z，
于是 xRz,R是 传递的 。
例 8：设 A = { 1,2,…,10 },对于 A上的关系
R = {< x,y > | (x? y)/3?Z },R具有哪些性质？
关系的性质解,对 任意 x?A，有 (x? x)/3 = 0?Z，则 < x,x >?R，
R是 自反的 。
若 xRy，即 (x? y)/3?Z，则有 (y - x)/3?Z，
于是 yRx,R是 对称的 。
2009-7-29 离散数学 34
例 9：
关系的性质解,(1) 关系非自反的，非反自反的，是对称的，
非反对称的，非传递的。
判断图中关系 具有哪些性质？
a?
bc
a?
bc
a?
bc
(2) 关系非自反的，是反自反的，非对称的，
是反对称的，是传递的。
(3) 关系是自反的，非反自反的，非对称的，
是反对称的，是传递的。
2009-7-29 离散数学 35
§ 4.4 关系的闭包闭包,设 R是 A上的关系，则包含 R而使之具有自反性质（对称性质或传递性质）的最小关系，
称为 R的自反闭包（对称闭包或传递闭包）。
自反闭包记作,r (R)
一、定义对称闭包记作,s (R)
传递闭包记作,t (R)
2009-7-29 离散数学 36
设 R是 A上的关系，则二、求解方法
(1) r (R) = R∪ R0
(2) s (R) = R∪ R–1
(3) t (R) = R∪ R2 ∪ R3 ∪ …
2009-7-29 离散数学 37
(1) Mr = M + E
矩阵形式,设 M是 R的关系矩阵，则
(2) Ms = M + M'
二、求解方法（续）
(3) Mt = M + M2 + M3 + …
其中 +均表示矩阵中对应元素的逻辑加。
2009-7-29 离散数学 38
关系图表示：
二、求解方法（续）
(1) 使 R的关系图中所有顶点都有一个环，
便得到 r (R)的关系图。
(3) 使 R的关系图中所有顶点到从它出发长度不超过 n (n是图中顶点个数 )的所有终点都有边，便得到 t (R)的关系图。
(2) 将 R的关系图中所有的单向边改成双向边，
便得到 s (R)的关系图。
2009-7-29 离散数学 39
例 10：设 A = {a,b,c},A上的关系 R = { <a,b>,<a,c>,
<b,a>,<b,c> }，求 r (R),s (R),t (R)。
三、应用解,r (R) = R∪ R0
s (R) = R∪ R–1
= R∪ { <a,a>,<b,b>,<c,c> }
= {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,c>}
= R∪ {<b,a>,<c,a>,<a,b>,<c,b>}
= {<a,b>,<a,c>,<b,a>,<b,c>,<c,a>,<c,b>}
2009-7-29 离散数学 40
则 t (R) = {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>}
例 10：设 A = {a,b,c},A上的关系 R = { <a,b>,<a,c>,
<b,a>,<b,c> }，求 r (R),s (R),t (R)。
三、应用（续）
解,t (R) = R∪ R2 ∪ R3 ∪ …
,
000
101
110
M,
000
110
101
2
M MM
000
101
110
3
000
111
111
2MMM
t
2009-7-29 离散数学 41
如例 8,设 A = { 1,2,…,10 },对于 A上的关系
R = { < x,y > | (x? y)/3?Z }
若 < x,y >?等价关系 R，则记作 x ~ y。
§ 4.5 等价关系和偏序关系一、等价关系等价关系,A上的关系 R是自反的、对称的和传递的，
则称 R为等价关系。
由 R具有自反性,对称性和传递性，知 R是等价关系，
且 1 ~ 4 ~ 7 ~ 10,2 ~ 5 ~ 8,3 ~ 6 ~ 9
2009-7-29 离散数学 42
一、等价关系例 11,设集合 A={1,2,3},下列关系中哪些不是等价的；
R1={<1,1>,<2,2>,<3,3> }
R2= { <1,1>,<2,2>,<3,3>,<3,2>,<2,3> }
R3= { <1,1>,<2,2>,<3,3>,<1,4}
R4= { <1,1>,<2,2>,<1,2>,<2,1>,<1,3>,
<3,1>,<3,3>,<2,3> <3,3>,<3,2> }
是是否是
2009-7-29 离散数学 43
一、等价关系（等价类）
等价类,设 R是 A上的等价关系，对任意 x?A，令
[x]R = { y | y?A? xRy },
则称 [x]R为 x关于 R的等价类。
简称为 x的等价类。简记为 [x]
于是例 8有 [1] = [4] = [7] = [10] = {1,4,7,10},
[2] = [5] = [8] = {2,5,8},
[3] = [6] = [9] = {3,6,9}
2009-7-29 离散数学 44
一、等价关系（性质）
等价类的性质,设 R是 A上的等价关系，
对任意 x,y?A，下列结论成立：
(1) [x]，且 [x]? A；
(2) 若 xRy 当且仅当 [x] = [y]；
(3) 若 x y,则 [x]∩[y] =?；
(4) 。
Ax
Ax
][?
R
2009-7-29 离散数学 45
(2) 若 xRy,则 [x] = [y]；
通过证明 [x]? [y]和 [y]? [x]来证明 [x]=[y] 。
证明,充分性：
z? [x],即 zRx，又 xRy，则 zRy，故 z? [y]，
即 [x]? [y]；
z? [y],即 zRy，又 xRy，即 yRx,则 zRx，故 z?[x]，
即 [y]? [x]；
所以 [x] = [y]；
必要性：
若 [x] = [y],由自反性,x? [x],则 x? [y],则 xRy。
一、等价关系（性质）
2009-7-29 离散数学 46
一、等价关系（商集）
集 A在等价关系 R下的商集：
设 R是 A上的等价关系，以 R的不交的等价类为元素的集合叫作 A在 R下的商集，记作 A?R，
即 A?R = { [x]R | x?A}
于是例 8中 A?R = { {1,4,7,10},{2,5,8},{3,6,9} }
2009-7-29 离散数学 47
一、等价关系（划分）
集合 A的划分：
设 A是非空集合，如果存在一个 A的子集族?( P(A)),满足以下条件：
(1)；
(2)? 中任意两个元素不交 ；
(3)? 中所有元素的并集等于 A；
则称?为 A的一个划分，且称?中的元素为划分块。
2009-7-29 离散数学 48
一、等价关系（续）
例 12：设 A = { a,b,c,d }，判断下列哪些集合是 A的划分。
(1) { {a},{b,c},{d} }
(2) { {a,b,c,d} }
(3) { {a,b},{c},{a,d} }
(4) {?,{a,b},{c,d} }
(5) { {a,b},{c} }
是是不是不是不是
2009-7-29 离散数学 49
一、等价关系（续）
等价关系与划分：
集合 A上的等价关系与 A的划分是一一对应的。
对于 A上给定的任意划分?，定义 A上二元关系 R为：对任何元素 x,y?A，若 x和 y在同一划分块中，则 xRy。于是 R是 A上的等价关系，称为由划分?所诱导的等价关系，且商集 A?R就等于?。
A在等价关系 R下的商集 A?R是 A的一个划分，
称为由 R所诱导的划分。
2009-7-29 离散数学 50
一、等价关系（续）
例 13：设 A = {1,2,3}，求出 A上所有的等价关系。
解：先求 A的各种划分：只有 1个划分块的划分?1，
具有 2个划分块的划分?2,?3,?4，
具有 3个划分块的划分?5。
于是?1= {{1,2,3}}，
2= {{1,2},{3}},? 3= {{1,3},{2}}，
4= {{1},{2,3}}，
5= {{1},{2},{3}}
2009-7-29 离散数学 51
一、等价关系（续）
例 13：设 A = {1,2,3}，求出 A上所有的等价关系。
R1= { <1,1>,<1,2>,<1,3>,<2,1>,<2,2>,
<2,3>,<3,1>,<3,2>,<3,3> }
设对应于划分?i 的等价关系为 Ri，则有
R2= { <1,1>,<1,2>,<2,1>,<2,2>,<3,3> }
R3= { <1,1>,<1,3>,<3,1>,<3,3>,<2,2> }
R4= { <2,2>,<2,3>,<3,2>,<3,3>,<1,1> }
R5= { <1,1>,<2,2>,<3,3> }
2009-7-29 离散数学 52
二、偏序关系偏序关系,A上的关系 R是自反的、反对称的和传递的，则称 R为偏序关系。记作 ≤
若 < x,y >?偏序关系 ≤，则可记作 x≤y。
偏 序 集,一个集合 A与 A上的偏序关系 R一起叫作偏序集。记作 < A,R > 。
2009-7-29 离散数学 53
(3) 对任意 <x,y>?R,<y,z>?R有 x≤y? y≤z，
则 x≤z，于是 <x,z>?R，所以 R是传递的。
二、偏序关系（续）
例 14,设 A = {1,2,3},A上关系 R是通常意义下的小于或等于关系，试写出 R并验证它是偏序关系。
解,R = { <1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3> }
(1) 因 <1,1>,<2,2>,<3,3>均属于 R，
所以 R是自反的。
(2) 对任意 <x,y>?R有 x≤y，当 x? y时 <y,x>?R
所以 R是反对称的。
2009-7-29 离散数学 54
对任意 <x,y>?R?且
<y,z>?R?有 x? y? y? z，则有 x? z，即 <x,z>?R?，
于是 R?是 传递的 。
二、偏序关系（续）
例 15,设 A = { a,b },证明 < P(A),R?>是偏序集。
解,R? = { <?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}>,<{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}> }
由 <?,?>,<{a},{a}>,<{b},{b}>,<{a,b},{a,b}>均属于 R?，
则 R?是 自反的 ； 对任意 <x,y>? R?有 x? y，当 x? y时有 <y,x>?R?，则 R?是 反对称的 ；
因此 < P(A),R?>是偏序集。
2009-7-29 离散数学 55
二、偏序关系（全序关系）
对于偏序集 < A,≤>
全序关系,偏序集 < A,≤>，若对任意的 x,y?A，都有
x 与 y 可比,则称 ≤为 A上的全序关系。
且称 < A,≤>为全序集。
(1) 可比,如果对任意 x,y?A，或者 x≤y 或者 y≤x成立，则称 x 与 y 可比。
(2) 盖住,如果 x < y且不存在 z?A，使 (x < z)? (z < y)，
则称 y 盖住 x 。
2009-7-29 离散数学 56
二、偏序关系（哈斯图）
偏序集 < A,≤>的 哈斯图,
特别地，全序集的哈斯图是一条直线。
(1) 用小圆圈分别表示 A的每一个元素 (称为结点 )。
(2) 按每个元素在偏序中的次序从底向上排列结点位置。
(3) 如果 y盖住 x，则在 x 和 y 之间连一条线。
2009-7-29 离散数学 57
二、偏序关系（ 哈斯图 ）
例 16：画出 <{1,2,…,12},R整除 >和 <P({a,b,c}),R?>
的哈斯图。
9
12
8
4 610
25
1
3 711
{a} {c}{b}
{a,b} {b,c}{a,c}
{a,b,c}
2009-7-29 离散数学 58
二、偏序关系（续）
设 < A,≤>为偏序集,B? A，
偏序集中的一些特殊元素：
(1) 若? y(y?B),使得? x(x?B?y≤x)成立，
则称 y是 B的 最小元 。 (小于 B中所有元 )
(2) 若? y(y?B),使得? x(x?B?x≤y)成立，
则称 y是 B的 最大元 。 (大于 B中所有元 )
(3) 若? y(y?B),使得x(x?B? x < y)成立，
则称 y是 B的 极小元 。 (B中没有比 y小的其他元 )
(4) 若?),使得 x(x?B? y < x)成立，
y(y?B 则称 y是 B的 极大元 。 (B中没有比 y大的其他元 )
2009-7-29 离散数学 59
二、偏序关系（续）
(5) 若? y(y?A),使得? x(x?B?x≤y)成立，
则称 y是 B的 上界 。
(6) 若? y(y?A),使得? x(x?B?y≤x)成立，
则称 y是 B的 下界 。
(7) 令 C = { y| y是 B的上界 }，则称 C的最小元为 B的最小上界或 上确界 。
(8) 令 C = { y| y是 B的下界 }，则称 C的最大元为 B的最大下界或 下确界 。
2009-7-29 离散数学 60
二、偏序关系（续）
9
12
8
4 610
25
1
3 711
图 1
最小元 1，无最大元；
极大元 7,8,9,10,11,12，极小元 1；
若 B={2,3,6}，则 B的最大元 6，无最小元，
极大元 6，极小元 2,3，上界为 6,12，最小上界为
6，下界是 1，最大下界是 1。
2009-7-29 离散数学 61
最小元?，最大元 {a,b,c}；
极大元 {a,b,c}，极小元?；
B={{b},{a,b},{a,c}}，无最大元和最小元，
极大元为 {a,b},{a,c},极小元 {b},{a,c}，
上界和最小上界都是 {a,b,c},下界和最大下界都是?。
二、偏序关系（续）
{a} {c}{b}
{a,b} {b,c}{a,c}
{a,b,c}
图 2
2009-7-29 离散数学 62
二、偏序关系（续）
dc
ba f h
图 3
g
e
无最小元，无最大元；
极大元 e,g,h，极小元 a,b,f,h；
B={c,d,g}，则 B的上界和最小上界 e，下界是 a,
b，没有最大上界；
2009-7-29 离散数学 63
一、函数的概念函数,设 f为二元关系,若对任意的 x?dom f都存在唯一的 y?ran f,使得 xfy成立，则称 f为函数，
并称 y 是 f在 x 的函数值。
如,f1 = {<x1,y1>,<x2,y1>,<x3,y2>}是函数，
但 f2 = {<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}不是函数
§ 4.6 函数的定义和性质若 < x,y >?函数 f，则记作 f (x) = y。
2009-7-29 离散数学 64
一、函数的概念（续）
从 A到 B的 函数：
从 A到 B的函数 f与从 A到 B的关系 R的区别,
(1) dom F = A，而 dom R? A。
(2) 函数 f中，对于一个 x满足 xfy的 y是 唯一的，
而关系 R中，对于一个 x满足 xRy的 y可能不唯一。
设 A,B是集合，如果函数 f 满足条件：
(1) dom f = A (2) ran f? B
则称 f是从 A到 B的 函数。记作 f,A? B
2009-7-29 离散数学 65
例如,A={0,1,2},B={a,b},则 BA={f1,f2,…f 8}
这 8个元素分别是 …？
设 A,B为集合，记 BA为所有从 A到 B的 函数构成的集合。,读作 B上 A” BA={f | f,A? B }
f1={<0,a>,<1,a>,<2,a>};
f2={<0,b>,<1,a>,<2,a>};
f3={<0,a>,<1,a>,<2,b>};
f4={<0,b>,<1,a>,<2,b>};
f5={<0,a>,<1,b>,<2,a>};
f6={<0,b>,<1,b>,<2,a>};
f7={<0,a>,<1,b>,<2,b>};
f8={<0,b>,<1,b>,<2,b>};
2009-7-29 离散数学 66
一、函数的概念（续）
集合 A'在函数 F下的象,
如 f,Z? Z,f (x) = x2，则 f ({ -1,0,1 }) = { 0,1 }
f,Z? R,f (x) = ex，则 f ({ -1,0,1 }) = { e-1,1,e }
设 f,A? B,A'? A，
则 f(A') = { f (x) | x?A'}称为 A'在 f下的象 。
当 A'= A时，称 f (A') = f (A) = ran f是函数的象 。
2009-7-29 离散数学 67
二、函数的性质设函数 F,A? B
1,满射,若 ran f = B，则称 F是满射的 (到上的 )。
2,单射,若对任意的 x1,x2?A,x1? x2,都有
f (x1)? f (x2),则称 f是单射的 (一一的 ) 。
3,双射,若 f 既是满射的又是单射的，
则称 f是双射的 (一一到上的 )。
2009-7-29 离散数学 68
二、函数的性质（续）
例 17：确定下列 F是否为 A到 B的 函数。若是则指出其是否为单射、满射或双射的。
(1) A = {1,2,3,4},B = {5,6,7,8,9}
f = { <1,6>,<3,5>,<4,7>,<2,8> }
(2) A,B 同上,f = { <1,6>,<3,5>,<4,7>,<2,6> }
(3) A,B 同上,f = { <1,6>,<3,5>,<4,7>,<1,8> }
(4) A,B为实数集,F (x)= x2 - x
(5) A,B为实数集,F (x)= 1/x
(6) A,B为实数集,F (x)= x/(x2 +1)
1 f是从 A到 B的函数，是单射的，不是满射的。
3 f不 是从 A到 B的函数。
2 f是从 A到 B的函数，不是单射的，不是满射的。
2009-7-29 离散数学 69
(4) f是从 A到 B的函数，不是单射的，不是满射的。
二、函数的性质（续）
例 17：确定下列 F是否为 A到 B的 函数。若是则指出其是否为单射、满射或双射的。
(5) f不 是从 A到 B的函数。
(6) f是从 A到 B的函数，不是单射的，不是满射的。
(4) A,B为实数集,f (x)= x2 - x
(5) A,B同上,f (x)= 1/x
(6) A,B同上,f (x)= x/(x2 +1)
2009-7-29 离散数学 70
(2) F,N? N? N,N为自然数集，
F (<x,y>) = | x2 – y2| 。
解：对任意 <x,y>,<u,v>?R? R,且 <x,y>? <u,v>,
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(1) f,R? R? R? R,R为实数集，
f (<x,y>) = < x + y,x – y > 。
假设有 < x + y,x – y > = < u + v,u – v >
因此一定有 < x + y,x – y >? < u + v,u – v >，
则有 x + y = u + v 和 x – y = u – v
联立两式解得,x = u且 y = v,
即函数具有单射性。
它与 <x,y>? <u,v>矛盾，
2009-7-29 离散数学 71
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(1) f,R? R? R? R,R为实数集，
f(<x,y>) = < x + y,x – y >。
又，对任意 <u,v>?R? R，假设存在 <x,y>?R? R，
满足 f(<x,y>) = <u,v>,
于是,ran f = R? R
即 x + y = u 且 x – y = v
联立两式解出,x = (u + v)/2 且 y = (u – v)/2,
即函数具有满射性。因此，该函数具有双射性。
则有 < x + y,x – y > = <u,v>
2009-7-29 离散数学 72
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(2) f,N? N? N,N为自然数集，
f (<x,y>) = |x2 – y2| 。
解：因为对任意 k?N，都有 f (<k,k>) = 0，
所以函数不具有单射性。
同时不存在 x,y?N，满足 |x2– y2| = 2，
即 2? ran f,则函数也不具有满射性。
因此函数也不具有双射性。
2009-7-29 离散数学 73
三、几类常见函数
1、常函数：
2、恒等函数：
A上的恒等关系 IA 就是一个恒等函数。
设 f,A? B,若?y( y?B),使得
x( x?A? f (x) = y)成立，则称 f是常函数。
设 f,A? A,若? x( x?A? f (x) = x)成立，
则称 F是恒等函数。
2009-7-29 离散数学 74
(4) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1) > f(x2))
成立，则称 F是严格单调递减函数。
三、几类常见函数（续）
3、单调函数,设 f,R? R，
(2) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1) < f(x2))
成立，则称 F是严格单调递增函数。
(3) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1)≥f(x2))
成立，则称 F是单调递减函数。
(1) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1)≤f(x2))
成立，则称 F是单调递增函数。
2009-7-29 离散数学 75
三、几类常见函数（续）
4、特征函数：
例如,A = {1,2,3,4},A' = {1,2}
设 A为集合，对任意 A'? A，令则 (1) = (2) = 1,(3) = (4) = 0
'A? 'A? 'A? 'A?
则称,A? {0,1}为 A'的特征函数。
'A?
=
1 若 a?A'
0 若 a?A – A')(' aA?
2009-7-29 离散数学 76
三、几类常见函数（续）
5、自然映射：
设 R是 A上的等价关系，定义一个从 A到 A?R
的函数 g,A? A?R且 g(a) = [a]，则称 g是从 A到商集 A?R的自然映射。
自然映射将 A中的元素 a 映射到 a 的等价类 [a]。
例如,A = { 1,2,3 }，
R = { <1,1>,<1,3>,<3,1>,<3,3>,<2,2> }
则,[1] = [3] = {1,3},[2] = {2}
g(1) = g(3) = {1,3},g(2) = {2}
2009-7-29 离散数学 77
一、函数的复合运算函数的复合：
设 f,g为函数，则 f? g也是函数，且满足条件,
(1) dom (f? g) = { x | x? dom f?f (x)? dom g }；
(2) 对任意的 x?dom (f? g)，有 f? g (x) = g (f (x))。
§ 4.7 函数的复合和反函数设 f,A? B,g,B? C,则 f? g,A? C，
且对任意的 x?A，有 f? g (x) = g (f (x))。
2009-7-29 离散数学 78
(3) 若 f,g是双射的,则 f? g,A? C也是 双射的。
一、函数的复合（续）
函数的复合运算的性质：
(1) 若 f,g是满射的,则 f? g,A? C也是 满射的。
(2) 若 f,g是单射的,则 f? g,A? C也是 单射的。
设 f,A? B,g,f? C,
2009-7-29 离散数学 79
二、函数的逆运算函数的逆：
设函数 f,A? B是双射 函数,则 f –1是函数，
并且是从 B到 A的双射函数。称 f –1是 F 的反函数。
函数的逆运算的性质：
f–1? f = IB,f? f–1 = IA
2009-7-29 离散数学 80
三、应用例 19,设 f,g,h?RR,且 f(x) = 2x + 5,g(x) = x – 7,
h(x) = x/3,求 f? g,g? f,g? g,g? h,f –1,g –1,h –1。
解,f? g(x) = g(f(x)) = g(2x+5) = 2x–2
g? f(x) = f(g(x)) = f(x-7) = 2(x-7) +5= 2x–9
g? g(x) = g(g(x)) = g(x -7) = x-7-7= x–14
g? h(x) = h(g(x)) = h(x-7) = (x-7)/3
f –1(x) = (x - 5)/2
g –1(x) = x + 7
h–1(x) = 3x
第四章 二元关系和函数
§ 4.1 集合的笛卡尔积与二元关系
§ 4.2 关系的运算
§ 4.3 关系的性质
§ 4.4 关系的闭包
§ 4.5 等价关系和偏序关系
§ 4.6 函数的定义和性质
§ 4.7 函数的复合和反函数
2009-7-29 离散数学 2
§ 4.1 集合的笛卡尔积与二元关系一、二元关系的概念有序对（序偶）,由两个元素 x 和 y 按一定顺序排成的二元组。记作,< x,y >。其中 x是它的第一元素,y是它的第二元素。
特点,(1)当 x?y 时,< x,y >? < y,x >
(2) < x,y > = < u,v > 当且仅当 x = u,y = v
(1)(2)说明有序对区别于集合。
如平面直角坐标系点的坐标。
2009-7-29 离散数学 3
一、二元关系的概念（续）
n 元有序对,第一元素是一个 n –1元 有序对的有序对。
记作,< x1,x2,…,xn >。
即 < x1,x2,…,xn > = << x1,…,xn-1 >,xn >
笛卡尔积,设 A,B为两集合,以 A中元素为第一元素,B中元素为第二元素构成的二元有序对的全体叫做 A和 B的笛卡儿积。
记作,A? B
符号化 A? B = { < x,y > | x?A? y?B }
2009-7-29 离散数学 4
一、二元关系的概念（续）
例 1：设 A = { a,b },B = { 0,1,2 },求 A? B,B? A。
解：由笛卡尔积的定义知
A? B = { < a,0 >,< a,1 >,< a,2 >,
< b,0 >,< b,1>,< b,2> }
B? A = { < 0,a >,< 0,b >,
< 1,a >,< 1,b >,
< 2,a >,< 2,b> }
一般地，若 |A| = m,|B| = n,则 |A? B| = |B? A| = mn
2009-7-29 离散数学 5
一、二元关系的概念（续）
笛卡尔积运算的性质：
(1)如果 A,B中有一个空集，则笛卡儿积是空集，
即, B = A =?
(3)当 A,B,C都不是空集时，有 (A? B)? C?
A? ( B? C)，即笛卡尔积不满足结合律。
(2)当 A? B,且 A,B都不是空集时，有 A? B? B? A,
即笛卡尔积不满足交换律。
2009-7-29 离散数学 6
一、二元关系的概念（续）
(4)笛卡尔积运算对 ∪ 或 ∩运算满足分配律，
即 A? (B∪ C) = (A? B)∪ (A? C)
(B∪ C)? A = (B? A)∪ (C? A)
A? (B∩C) = (A? B)∩(A? C)
(B∩C)? A = (B? A)∩(C? A)
证明,< x,y >? (B∪ C)? A? x?B∪ C? y?A
( x?B? x?C )? y?A
( x?B? y?A )? ( x?C? y?A )
( < x,y >? B? A )? ( < x,y >? C? A )
< x,y >?(B? A)∪ (C? A)
2009-7-29 离散数学 7
一、二元关系的概念（续）
例 2：设 A = {1,2},求 P (A)? A。
解,P (A)? A
推广,n阶笛卡尔积
A1? A2?…? An
= {<x1,x2,…,xn > | x1?A1? x2?A2?…? xn?An }
= {?,{1},{2},{1,2} }? {1,2}
= { <?,1>,<?,2>,<{1},1>,<{1},2>,<{2},1>,
<{2},2>,< {1,2},1>,< {1,2},2> }
2009-7-29 离散数学 8
一、二元关系的概念（续）
二元关系 是指在集合中两个元素之间的某种相关性,
例如,家庭成员集合 {a,b,c,d}上的父子关系,
R={<a,c>,<a,d>},
二元关系的数学定义,如果一个集合为空集或者它的元素都是二元有序对，则这个集合称为一个二元关系，记作,R
如果 < x,y >? R,记作 x R y
如果 < x,y >? R,记作 x R y
2009-7-29 离散数学 9
一、二元关系的概念（续）
从 A到 B的二元关系,设 A,B为集合,A? B的任何子集所定义的二元关系叫做从 A到 B的二元关系。
设 A={a,b,c}代表三个人的构成的集合
B={1,2,3,4}代表四项工作构成的集合若 a从事工作 1,b从事工作 2,c从事工作 3,则人从事工作之间的关系可以表示为,
R={<a,1>,<b,2>,<c,4>} 为 A到 B的二元关系之一
2009-7-29 离散数学 10
特别地，若 A = B，叫作 A上的二元关系 。
若 |A| = n，则 |A? A| = n2,A? A的所有子集有 个，
因此,A上有 个不同的二元关系。
22n
22n
例如,家庭成员集合 A={a,b,c,d}上的成员分别代表 父、母、兄、
弟,则该集合上的各种关系为：
父子关系,{ <a,c>,<a,d> },
母子关系,{ <b,c>,<b,d> },
兄弟关系,。。。夫妻关系。。。 都是 A上的二元关系
2009-7-29 离散数学 11
一、二元关系的概念（续）
例 3：设 A = {a,b}，写出 P(A)上的包含关系 R? 。
解,P(A) = {?,{a},{b},{a,b} }
R = { <?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}> <{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}> }
空关系 即空集?
恒等关系 IA = { < x,x >| x?A}
全域关系 EA = { < x,y >| x?A? y?A }= A? A
A的 3种特殊关系,空关系,全域关系 EA,恒等关系 IA
2009-7-29 离散数学 12
二、二元关系的表示方法
1,关系矩阵设 A = { x1,x2,…,xn },R是 A上的关系，
rij =
1 若 xi R xj
0 若 xi R xj
令 (i,j = 1,2,…,n)
则 ( rij )n× n = 是 R的关系矩阵
nnnn
n
n
rrr
rrr
rrr
...
............
...
...
21
22221
11211
2009-7-29 离散数学 13
二、二元关系的表示方法（续）
2,关系图以 V = A = { x1,x2,…,xn }为顶点的集合,以
E = { < xi,xj > | xi?A? xj?A? xi R xj}为有向边的集合,组成的有向图 G = < V,E >。
例如,{x1,x2,x3}上的关系 R={<x1,x2>,<x1,x3>}
x1 x2
x3
2009-7-29 离散数学 14
二、二元关系的表示方法（续）
例 4：设 A = {1,2,3,4},R = { <1,2>,<1,3>,<2,2>,
<2,4>,<3,4>,<4,2> }是 A上的关系，试写出 R的关系矩阵并画出关系图。
解,关系矩阵
0010
1000
1010
0110
关系图
12
43
思考：写出例 3的关系矩阵和关系图
2009-7-29 离散数学 15
关系 R的定义域 (domain),
dom R = { x |? y(< x,y >?R) },
即 R中所有有序对的第一元素构成的集合。
一、关系的定义域与值域
§ 4.2 关系的运算关系 R的值域 (range)：
ran R = { y |? x(< x,y >?R) },
即 R中所有有序对的第二元素构成的集合。
关系 R的域 (field),fld R = dom R∪ ran R
2009-7-29 离散数学 16
一、关系的定义域与值域（续）
例 5：分别求出下列关系的定义域和值域。
(1) R1 = { < x,y > | x,y?Z? x? y };
(2) R2 = { < x,y > | x,y?Z? x2 + y2 = 1 };
(3) R3 = { < x,y > | x,y?{1,2,3,4}? x > y }
解,(1) dom R1 = ran R1 = Z
(2) R2 = {<0,1>,<0,-1>,<1,0>,< -1,0>}
(3) R3 = {<2,1>,<3,1>,<4,1>,<3,2>,<4,2>,<4,3>}
dom R2 = ran R2 = { 0,1,-1 }
dom R3 = { 2,3,4 },ran R3 = { 1,2,3 }
2009-7-29 离散数学 17
1,逆：
2,合成：
3,限制：
4,象：
任意两个关系 F与 G的合成，记作,F? G
F? G = { < x,y > |? z( xFz? zGy ) } (右复合 )
二、关系的常用运算
F是任意关系,F 的逆 F -1 ={ < x,y > | yFx }
关系 F在集合 A上的限制，记作,F | A
F | A = { < x,y > | xFy? x?A }
集合 A在 F 下的象，记作,F [A]
F [A] = ran (F | A)
2009-7-29 离散数学 18
例,设 F＝ {<3,3>,<6,2>},G={<2,3>,<3,6>}，
则 F-1 ＝ {<3,3>,<2,6>},
F?G＝ {<3,6>,{<6,3>},G?F＝ {<2,3>,<3,2>}
例,设 R＝ {<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}
R | {1}＝ {<1,2>,<1,3>}
R | {2,3}＝ {<2,2>,<2,4>},<3,2>}
R[{1}]＝ {2,3}
R[{3}]＝ {2}
2009-7-29 离散数学 19
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解,G–1 = { < y,x > | x,y?N? y = x + 1 }
列出 G –1中的元素即为
G –1 = {<1,0>,<2,1>,<3,2>,…,< x + 1,x >,… }
2009-7-29 离散数学 20
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解：为了求 F? G可以先直观表示如下：
对任何 x?N
x x 2 = z z+1 = yGF
因此 F? G = {< x,y > | x,y?N? y = x 2+ 1}
即 y = x 2+ 1
2009-7-29 离散数学 21
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解：为了求 G? F可以先直观表示如下：
对任何 x?N
x x+1 = z z 2 = yG F
因此 G? F = {< x,y > | x,y?N? y = （ x + 1） 2}
即 y = （ x+ 1） 2
2009-7-29 离散数学 22
二、关系的常用运算（续）
例 6：设 F,G是 N上的关系，其定义为
F = { < x,y > | x,y?N? y = x2 }
G = { < x,y > | x,y?N? y = x + 1 }
求 G –1,F? G,G? F,F | {1,2},F [{1,2}]。
解,F | {1,2} = { <1,1>,<2,4> }
F [{1,2}] = ran (F | {1,2}) = { 1,4 }
2009-7-29 离散数学 23
三、关系运算的性质
1,(F –1)–1 = F
2,dom F –1 = ran F,ran F –1 = dom F
3,(F? G)? H = F? (G? H )
4,(F? G)–1 = G –1? F –1
5,F? (G∪ H) = (F? G)∪ (F? H)
6,F? (G∩H)? (F? G)∩(F? H)
8,(G∩H)? F? (G? F)∩(H? F)
7,(G∪ H)? F = (G? F)∪ (H? F)
2009-7-29 离散数学 24
三、关系运算的性质（续）
4,(F? G)–1 = G –1? F –1的证明。
对任意 < x,y >?(F? G)–1
< y,x >?F? G
z( < y,z >?F? < z,x >?G )
z( < z,y >?F –1? < x,z >?G–1 )
z( < x,z >?G –1?< z,y >?F –1 )
< x,y >?G –1? F –1
2009-7-29 离散数学 25
三、关系运算的性质（续）
6,F? (G∩H)? (F? G)∩(F? H)的证明。
对任意 < x,y >? F? (G∩H)
z(< x,z >?F? < z,y >? G∩H )
z(< x,z >?F? < z,y >?G? < z,y >?H )
z((<x,z>?F? <z,y>?G)? (<x,z>?F? <z,y>?H))
z(<x,z>?F?<z,y>?G) z(<x,z>?F?<z,y>?H)
< x,y >? F? G? < x,y >? F? H
< x,y >? (F? G)∩(F? H)
2009-7-29 离散数学 26
四、关系的幂运算设 R是 A上的关系,n为自然数，则：
(1) R0 = { < x,x > | x?A }
(2) Rn = Rn-1? R,n? 1
定理
(1) Rm? Rn = Rm + n
(2) (Rm)n = Rmn
其中 m,n为自然数。
2009-7-29 离散数学 27
求 R的各次幂的方法,
(1) 集合运算法 ;
R2 =R? R
(2) 关系图法 ;
根据 R的关系图求 R2
(3)关系矩阵法 ; | R n|= |R| n (逻辑加 )
x3x2x1 x
3x1
2009-7-29 离散数学 28
四、关系的幂运算（续）
例 7：设 A= { a,b,c,d },A上的一个关系
R = { < a,b >,< b,a >,< b,c >,< c,d > }
求 R0,R2,R3。
解,R0= { < a,a >,< b,b >,< c,c >,< d,d > }
由 R的关系图知
R2 = R? R = { < a,a >,< a,c >,
< b,b >,< b,d > }
ab
dc
R3 = { < a,b >,< a,d >,< b,a >,< b,c >}
2009-7-29 离散数学 29
R3 = R2? R = { <a,b>,<a,d>,<b,a>,<b,c>}
四、关系的幂运算（续）
例 7：设 A= { a,b,c,d },A上的一个关系
R = { < a,b >,< b,a >,< b,c >,< c,d > }
求 R0,R2,R3。
R2 = R? R = { <a,a>,<a,c>,<b,b>,<b,d> }
R的关系矩阵
,
0000
1000
0101
0010
M,
0000
0000
1010
0101
2
M
0000
0000
0101
1010
3M
2009-7-29 离散数学 30
§ 4.3 关系的性质
1、自反性,?x?A,有 <x,x>?R
设 R是 A上的关系
R的关系矩阵：主对角线元素全为 1
R的关系图：每个顶点都有环
2、反自反性,? x?A,有 <x,x>? R
R的关系矩阵：主对角线元素全为 0
R的关系图：每个顶点都没有环
2009-7-29 离散数学 31
3、对称性,若 <x,y>?R，则 <y,x>?R
R的关系矩阵：对称阵
R的关系图：若两个顶点间有边，则一定是一对方向相反的边。
4、反对称性,若 <x,y>?R且 x? y，则 <y,x>?R
R的关系矩阵：若 rij = 1，且 i? j，则 rji = 0
R的关系图：若两个顶点间有边，则一定是只有一条有向边。
关系的性质
2009-7-29 离散数学 32
5、传递性,若 <x,y>?R且 <y,z>?R，则 <x,z>?R
R的关系图：若顶点 xi 到 xj 有边,xj 到 xk 有边，
则 xi 到 xk 有边。
关系的性质
2009-7-29 离散数学 33
若 A中有三个元素 x,y,z,满足 xRy且 yRz，
即 (x? y)/3?Z且 (y? z)/3?Z,则有 (x? z)/3?Z，
于是 xRz,R是 传递的 。
例 8：设 A = { 1,2,…,10 },对于 A上的关系
R = {< x,y > | (x? y)/3?Z },R具有哪些性质？
关系的性质解,对 任意 x?A，有 (x? x)/3 = 0?Z，则 < x,x >?R，
R是 自反的 。
若 xRy，即 (x? y)/3?Z，则有 (y - x)/3?Z，
于是 yRx,R是 对称的 。
2009-7-29 离散数学 34
例 9：
关系的性质解,(1) 关系非自反的，非反自反的，是对称的，
非反对称的，非传递的。
判断图中关系 具有哪些性质？
a?
bc
a?
bc
a?
bc
(2) 关系非自反的，是反自反的，非对称的，
是反对称的，是传递的。
(3) 关系是自反的，非反自反的，非对称的，
是反对称的，是传递的。
2009-7-29 离散数学 35
§ 4.4 关系的闭包闭包,设 R是 A上的关系，则包含 R而使之具有自反性质（对称性质或传递性质）的最小关系，
称为 R的自反闭包（对称闭包或传递闭包）。
自反闭包记作,r (R)
一、定义对称闭包记作,s (R)
传递闭包记作,t (R)
2009-7-29 离散数学 36
设 R是 A上的关系，则二、求解方法
(1) r (R) = R∪ R0
(2) s (R) = R∪ R–1
(3) t (R) = R∪ R2 ∪ R3 ∪ …
2009-7-29 离散数学 37
(1) Mr = M + E
矩阵形式,设 M是 R的关系矩阵，则
(2) Ms = M + M'
二、求解方法（续）
(3) Mt = M + M2 + M3 + …
其中 +均表示矩阵中对应元素的逻辑加。
2009-7-29 离散数学 38
关系图表示：
二、求解方法（续）
(1) 使 R的关系图中所有顶点都有一个环，
便得到 r (R)的关系图。
(3) 使 R的关系图中所有顶点到从它出发长度不超过 n (n是图中顶点个数 )的所有终点都有边，便得到 t (R)的关系图。
(2) 将 R的关系图中所有的单向边改成双向边，
便得到 s (R)的关系图。
2009-7-29 离散数学 39
例 10：设 A = {a,b,c},A上的关系 R = { <a,b>,<a,c>,
<b,a>,<b,c> }，求 r (R),s (R),t (R)。
三、应用解,r (R) = R∪ R0
s (R) = R∪ R–1
= R∪ { <a,a>,<b,b>,<c,c> }
= {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>,<c,c>}
= R∪ {<b,a>,<c,a>,<a,b>,<c,b>}
= {<a,b>,<a,c>,<b,a>,<b,c>,<c,a>,<c,b>}
2009-7-29 离散数学 40
则 t (R) = {<a,a>,<a,b>,<a,c>,<b,a>,<b,b>,<b,c>}
例 10：设 A = {a,b,c},A上的关系 R = { <a,b>,<a,c>,
<b,a>,<b,c> }，求 r (R),s (R),t (R)。
三、应用（续）
解,t (R) = R∪ R2 ∪ R3 ∪ …
,
000
101
110
M,
000
110
101
2
M MM
000
101
110
3
000
111
111
2MMM
t
2009-7-29 离散数学 41
如例 8,设 A = { 1,2,…,10 },对于 A上的关系
R = { < x,y > | (x? y)/3?Z }
若 < x,y >?等价关系 R，则记作 x ~ y。
§ 4.5 等价关系和偏序关系一、等价关系等价关系,A上的关系 R是自反的、对称的和传递的，
则称 R为等价关系。
由 R具有自反性,对称性和传递性，知 R是等价关系，
且 1 ~ 4 ~ 7 ~ 10,2 ~ 5 ~ 8,3 ~ 6 ~ 9
2009-7-29 离散数学 42
一、等价关系例 11,设集合 A={1,2,3},下列关系中哪些不是等价的；
R1={<1,1>,<2,2>,<3,3> }
R2= { <1,1>,<2,2>,<3,3>,<3,2>,<2,3> }
R3= { <1,1>,<2,2>,<3,3>,<1,4}
R4= { <1,1>,<2,2>,<1,2>,<2,1>,<1,3>,
<3,1>,<3,3>,<2,3> <3,3>,<3,2> }
是是否是
2009-7-29 离散数学 43
一、等价关系（等价类）
等价类,设 R是 A上的等价关系，对任意 x?A，令
[x]R = { y | y?A? xRy },
则称 [x]R为 x关于 R的等价类。
简称为 x的等价类。简记为 [x]
于是例 8有 [1] = [4] = [7] = [10] = {1,4,7,10},
[2] = [5] = [8] = {2,5,8},
[3] = [6] = [9] = {3,6,9}
2009-7-29 离散数学 44
一、等价关系（性质）
等价类的性质,设 R是 A上的等价关系，
对任意 x,y?A，下列结论成立：
(1) [x]，且 [x]? A；
(2) 若 xRy 当且仅当 [x] = [y]；
(3) 若 x y,则 [x]∩[y] =?；
(4) 。
Ax
Ax
][?
R
2009-7-29 离散数学 45
(2) 若 xRy,则 [x] = [y]；
通过证明 [x]? [y]和 [y]? [x]来证明 [x]=[y] 。
证明,充分性：
z? [x],即 zRx，又 xRy，则 zRy，故 z? [y]，
即 [x]? [y]；
z? [y],即 zRy，又 xRy，即 yRx,则 zRx，故 z?[x]，
即 [y]? [x]；
所以 [x] = [y]；
必要性：
若 [x] = [y],由自反性,x? [x],则 x? [y],则 xRy。
一、等价关系（性质）
2009-7-29 离散数学 46
一、等价关系（商集）
集 A在等价关系 R下的商集：
设 R是 A上的等价关系，以 R的不交的等价类为元素的集合叫作 A在 R下的商集，记作 A?R，
即 A?R = { [x]R | x?A}
于是例 8中 A?R = { {1,4,7,10},{2,5,8},{3,6,9} }
2009-7-29 离散数学 47
一、等价关系（划分）
集合 A的划分：
设 A是非空集合，如果存在一个 A的子集族?( P(A)),满足以下条件：
(1)；
(2)? 中任意两个元素不交 ；
(3)? 中所有元素的并集等于 A；
则称?为 A的一个划分，且称?中的元素为划分块。
2009-7-29 离散数学 48
一、等价关系（续）
例 12：设 A = { a,b,c,d }，判断下列哪些集合是 A的划分。
(1) { {a},{b,c},{d} }
(2) { {a,b,c,d} }
(3) { {a,b},{c},{a,d} }
(4) {?,{a,b},{c,d} }
(5) { {a,b},{c} }
是是不是不是不是
2009-7-29 离散数学 49
一、等价关系（续）
等价关系与划分：
集合 A上的等价关系与 A的划分是一一对应的。
对于 A上给定的任意划分?，定义 A上二元关系 R为：对任何元素 x,y?A，若 x和 y在同一划分块中，则 xRy。于是 R是 A上的等价关系，称为由划分?所诱导的等价关系，且商集 A?R就等于?。
A在等价关系 R下的商集 A?R是 A的一个划分，
称为由 R所诱导的划分。
2009-7-29 离散数学 50
一、等价关系（续）
例 13：设 A = {1,2,3}，求出 A上所有的等价关系。
解：先求 A的各种划分：只有 1个划分块的划分?1，
具有 2个划分块的划分?2,?3,?4，
具有 3个划分块的划分?5。
于是?1= {{1,2,3}}，
2= {{1,2},{3}},? 3= {{1,3},{2}}，
4= {{1},{2,3}}，
5= {{1},{2},{3}}
2009-7-29 离散数学 51
一、等价关系（续）
例 13：设 A = {1,2,3}，求出 A上所有的等价关系。
R1= { <1,1>,<1,2>,<1,3>,<2,1>,<2,2>,
<2,3>,<3,1>,<3,2>,<3,3> }
设对应于划分?i 的等价关系为 Ri，则有
R2= { <1,1>,<1,2>,<2,1>,<2,2>,<3,3> }
R3= { <1,1>,<1,3>,<3,1>,<3,3>,<2,2> }
R4= { <2,2>,<2,3>,<3,2>,<3,3>,<1,1> }
R5= { <1,1>,<2,2>,<3,3> }
2009-7-29 离散数学 52
二、偏序关系偏序关系,A上的关系 R是自反的、反对称的和传递的，则称 R为偏序关系。记作 ≤
若 < x,y >?偏序关系 ≤，则可记作 x≤y。
偏 序 集,一个集合 A与 A上的偏序关系 R一起叫作偏序集。记作 < A,R > 。
2009-7-29 离散数学 53
(3) 对任意 <x,y>?R,<y,z>?R有 x≤y? y≤z，
则 x≤z，于是 <x,z>?R，所以 R是传递的。
二、偏序关系（续）
例 14,设 A = {1,2,3},A上关系 R是通常意义下的小于或等于关系，试写出 R并验证它是偏序关系。
解,R = { <1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3> }
(1) 因 <1,1>,<2,2>,<3,3>均属于 R，
所以 R是自反的。
(2) 对任意 <x,y>?R有 x≤y，当 x? y时 <y,x>?R
所以 R是反对称的。
2009-7-29 离散数学 54
对任意 <x,y>?R?且
<y,z>?R?有 x? y? y? z，则有 x? z，即 <x,z>?R?，
于是 R?是 传递的 。
二、偏序关系（续）
例 15,设 A = { a,b },证明 < P(A),R?>是偏序集。
解,R? = { <?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,
<{a},{a}>,<{a},{a,b}>,<{b},{b}>,
<{b},{a,b}>,<{a,b},{a,b}> }
由 <?,?>,<{a},{a}>,<{b},{b}>,<{a,b},{a,b}>均属于 R?，
则 R?是 自反的 ； 对任意 <x,y>? R?有 x? y，当 x? y时有 <y,x>?R?，则 R?是 反对称的 ；
因此 < P(A),R?>是偏序集。
2009-7-29 离散数学 55
二、偏序关系（全序关系）
对于偏序集 < A,≤>
全序关系,偏序集 < A,≤>，若对任意的 x,y?A，都有
x 与 y 可比,则称 ≤为 A上的全序关系。
且称 < A,≤>为全序集。
(1) 可比,如果对任意 x,y?A，或者 x≤y 或者 y≤x成立，则称 x 与 y 可比。
(2) 盖住,如果 x < y且不存在 z?A，使 (x < z)? (z < y)，
则称 y 盖住 x 。
2009-7-29 离散数学 56
二、偏序关系（哈斯图）
偏序集 < A,≤>的 哈斯图,
特别地，全序集的哈斯图是一条直线。
(1) 用小圆圈分别表示 A的每一个元素 (称为结点 )。
(2) 按每个元素在偏序中的次序从底向上排列结点位置。
(3) 如果 y盖住 x，则在 x 和 y 之间连一条线。
2009-7-29 离散数学 57
二、偏序关系（ 哈斯图 ）
例 16：画出 <{1,2,…,12},R整除 >和 <P({a,b,c}),R?>
的哈斯图。
9
12
8
4 610
25
1
3 711
{a} {c}{b}
{a,b} {b,c}{a,c}
{a,b,c}
2009-7-29 离散数学 58
二、偏序关系（续）
设 < A,≤>为偏序集,B? A，
偏序集中的一些特殊元素：
(1) 若? y(y?B),使得? x(x?B?y≤x)成立，
则称 y是 B的 最小元 。 (小于 B中所有元 )
(2) 若? y(y?B),使得? x(x?B?x≤y)成立，
则称 y是 B的 最大元 。 (大于 B中所有元 )
(3) 若? y(y?B),使得x(x?B? x < y)成立，
则称 y是 B的 极小元 。 (B中没有比 y小的其他元 )
(4) 若?),使得 x(x?B? y < x)成立，
y(y?B 则称 y是 B的 极大元 。 (B中没有比 y大的其他元 )
2009-7-29 离散数学 59
二、偏序关系（续）
(5) 若? y(y?A),使得? x(x?B?x≤y)成立，
则称 y是 B的 上界 。
(6) 若? y(y?A),使得? x(x?B?y≤x)成立，
则称 y是 B的 下界 。
(7) 令 C = { y| y是 B的上界 }，则称 C的最小元为 B的最小上界或 上确界 。
(8) 令 C = { y| y是 B的下界 }，则称 C的最大元为 B的最大下界或 下确界 。
2009-7-29 离散数学 60
二、偏序关系（续）
9
12
8
4 610
25
1
3 711
图 1
最小元 1，无最大元；
极大元 7,8,9,10,11,12，极小元 1；
若 B={2,3,6}，则 B的最大元 6，无最小元，
极大元 6，极小元 2,3，上界为 6,12，最小上界为
6，下界是 1，最大下界是 1。
2009-7-29 离散数学 61
最小元?，最大元 {a,b,c}；
极大元 {a,b,c}，极小元?；
B={{b},{a,b},{a,c}}，无最大元和最小元，
极大元为 {a,b},{a,c},极小元 {b},{a,c}，
上界和最小上界都是 {a,b,c},下界和最大下界都是?。
二、偏序关系（续）
{a} {c}{b}
{a,b} {b,c}{a,c}
{a,b,c}
图 2
2009-7-29 离散数学 62
二、偏序关系（续）
dc
ba f h
图 3
g
e
无最小元，无最大元；
极大元 e,g,h，极小元 a,b,f,h；
B={c,d,g}，则 B的上界和最小上界 e，下界是 a,
b，没有最大上界；
2009-7-29 离散数学 63
一、函数的概念函数,设 f为二元关系,若对任意的 x?dom f都存在唯一的 y?ran f,使得 xfy成立，则称 f为函数，
并称 y 是 f在 x 的函数值。
如,f1 = {<x1,y1>,<x2,y1>,<x3,y2>}是函数，
但 f2 = {<x1,y1>,<x1,y2>,<x2,y1>,<x3,y2>}不是函数
§ 4.6 函数的定义和性质若 < x,y >?函数 f，则记作 f (x) = y。
2009-7-29 离散数学 64
一、函数的概念（续）
从 A到 B的 函数：
从 A到 B的函数 f与从 A到 B的关系 R的区别,
(1) dom F = A，而 dom R? A。
(2) 函数 f中，对于一个 x满足 xfy的 y是 唯一的，
而关系 R中，对于一个 x满足 xRy的 y可能不唯一。
设 A,B是集合，如果函数 f 满足条件：
(1) dom f = A (2) ran f? B
则称 f是从 A到 B的 函数。记作 f,A? B
2009-7-29 离散数学 65
例如,A={0,1,2},B={a,b},则 BA={f1,f2,…f 8}
这 8个元素分别是 …？
设 A,B为集合，记 BA为所有从 A到 B的 函数构成的集合。,读作 B上 A” BA={f | f,A? B }
f1={<0,a>,<1,a>,<2,a>};
f2={<0,b>,<1,a>,<2,a>};
f3={<0,a>,<1,a>,<2,b>};
f4={<0,b>,<1,a>,<2,b>};
f5={<0,a>,<1,b>,<2,a>};
f6={<0,b>,<1,b>,<2,a>};
f7={<0,a>,<1,b>,<2,b>};
f8={<0,b>,<1,b>,<2,b>};
2009-7-29 离散数学 66
一、函数的概念（续）
集合 A'在函数 F下的象,
如 f,Z? Z,f (x) = x2，则 f ({ -1,0,1 }) = { 0,1 }
f,Z? R,f (x) = ex，则 f ({ -1,0,1 }) = { e-1,1,e }
设 f,A? B,A'? A，
则 f(A') = { f (x) | x?A'}称为 A'在 f下的象 。
当 A'= A时，称 f (A') = f (A) = ran f是函数的象 。
2009-7-29 离散数学 67
二、函数的性质设函数 F,A? B
1,满射,若 ran f = B，则称 F是满射的 (到上的 )。
2,单射,若对任意的 x1,x2?A,x1? x2,都有
f (x1)? f (x2),则称 f是单射的 (一一的 ) 。
3,双射,若 f 既是满射的又是单射的，
则称 f是双射的 (一一到上的 )。
2009-7-29 离散数学 68
二、函数的性质（续）
例 17：确定下列 F是否为 A到 B的 函数。若是则指出其是否为单射、满射或双射的。
(1) A = {1,2,3,4},B = {5,6,7,8,9}
f = { <1,6>,<3,5>,<4,7>,<2,8> }
(2) A,B 同上,f = { <1,6>,<3,5>,<4,7>,<2,6> }
(3) A,B 同上,f = { <1,6>,<3,5>,<4,7>,<1,8> }
(4) A,B为实数集,F (x)= x2 - x
(5) A,B为实数集,F (x)= 1/x
(6) A,B为实数集,F (x)= x/(x2 +1)
1 f是从 A到 B的函数，是单射的，不是满射的。
3 f不 是从 A到 B的函数。
2 f是从 A到 B的函数，不是单射的，不是满射的。
2009-7-29 离散数学 69
(4) f是从 A到 B的函数，不是单射的，不是满射的。
二、函数的性质（续）
例 17：确定下列 F是否为 A到 B的 函数。若是则指出其是否为单射、满射或双射的。
(5) f不 是从 A到 B的函数。
(6) f是从 A到 B的函数，不是单射的，不是满射的。
(4) A,B为实数集,f (x)= x2 - x
(5) A,B同上,f (x)= 1/x
(6) A,B同上,f (x)= x/(x2 +1)
2009-7-29 离散数学 70
(2) F,N? N? N,N为自然数集，
F (<x,y>) = | x2 – y2| 。
解：对任意 <x,y>,<u,v>?R? R,且 <x,y>? <u,v>,
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(1) f,R? R? R? R,R为实数集，
f (<x,y>) = < x + y,x – y > 。
假设有 < x + y,x – y > = < u + v,u – v >
因此一定有 < x + y,x – y >? < u + v,u – v >，
则有 x + y = u + v 和 x – y = u – v
联立两式解得,x = u且 y = v,
即函数具有单射性。
它与 <x,y>? <u,v>矛盾，
2009-7-29 离散数学 71
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(1) f,R? R? R? R,R为实数集，
f(<x,y>) = < x + y,x – y >。
又，对任意 <u,v>?R? R，假设存在 <x,y>?R? R，
满足 f(<x,y>) = <u,v>,
于是,ran f = R? R
即 x + y = u 且 x – y = v
联立两式解出,x = (u + v)/2 且 y = (u – v)/2,
即函数具有满射性。因此，该函数具有双射性。
则有 < x + y,x – y > = <u,v>
2009-7-29 离散数学 72
二、函数的性质（续）
例 18：判断下列函数的单射、满射和双射性。
(2) f,N? N? N,N为自然数集，
f (<x,y>) = |x2 – y2| 。
解：因为对任意 k?N，都有 f (<k,k>) = 0，
所以函数不具有单射性。
同时不存在 x,y?N，满足 |x2– y2| = 2，
即 2? ran f,则函数也不具有满射性。
因此函数也不具有双射性。
2009-7-29 离散数学 73
三、几类常见函数
1、常函数：
2、恒等函数：
A上的恒等关系 IA 就是一个恒等函数。
设 f,A? B,若?y( y?B),使得
x( x?A? f (x) = y)成立，则称 f是常函数。
设 f,A? A,若? x( x?A? f (x) = x)成立，
则称 F是恒等函数。
2009-7-29 离散数学 74
(4) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1) > f(x2))
成立，则称 F是严格单调递减函数。
三、几类常见函数（续）
3、单调函数,设 f,R? R，
(2) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1) < f(x2))
成立，则称 F是严格单调递增函数。
(3) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1)≥f(x2))
成立，则称 F是单调递减函数。
(1) 若? x1? x2(x1?R? x2?R? x1<x2? f(x1)≤f(x2))
成立，则称 F是单调递增函数。
2009-7-29 离散数学 75
三、几类常见函数（续）
4、特征函数：
例如,A = {1,2,3,4},A' = {1,2}
设 A为集合，对任意 A'? A，令则 (1) = (2) = 1,(3) = (4) = 0
'A? 'A? 'A? 'A?
则称,A? {0,1}为 A'的特征函数。
'A?
=
1 若 a?A'
0 若 a?A – A')(' aA?
2009-7-29 离散数学 76
三、几类常见函数（续）
5、自然映射：
设 R是 A上的等价关系，定义一个从 A到 A?R
的函数 g,A? A?R且 g(a) = [a]，则称 g是从 A到商集 A?R的自然映射。
自然映射将 A中的元素 a 映射到 a 的等价类 [a]。
例如,A = { 1,2,3 }，
R = { <1,1>,<1,3>,<3,1>,<3,3>,<2,2> }
则,[1] = [3] = {1,3},[2] = {2}
g(1) = g(3) = {1,3},g(2) = {2}
2009-7-29 离散数学 77
一、函数的复合运算函数的复合：
设 f,g为函数，则 f? g也是函数，且满足条件,
(1) dom (f? g) = { x | x? dom f?f (x)? dom g }；
(2) 对任意的 x?dom (f? g)，有 f? g (x) = g (f (x))。
§ 4.7 函数的复合和反函数设 f,A? B,g,B? C,则 f? g,A? C，
且对任意的 x?A，有 f? g (x) = g (f (x))。
2009-7-29 离散数学 78
(3) 若 f,g是双射的,则 f? g,A? C也是 双射的。
一、函数的复合（续）
函数的复合运算的性质：
(1) 若 f,g是满射的,则 f? g,A? C也是 满射的。
(2) 若 f,g是单射的,则 f? g,A? C也是 单射的。
设 f,A? B,g,f? C,
2009-7-29 离散数学 79
二、函数的逆运算函数的逆：
设函数 f,A? B是双射 函数,则 f –1是函数，
并且是从 B到 A的双射函数。称 f –1是 F 的反函数。
函数的逆运算的性质：
f–1? f = IB,f? f–1 = IA
2009-7-29 离散数学 80
三、应用例 19,设 f,g,h?RR,且 f(x) = 2x + 5,g(x) = x – 7,
h(x) = x/3,求 f? g,g? f,g? g,g? h,f –1,g –1,h –1。
解,f? g(x) = g(f(x)) = g(2x+5) = 2x–2
g? f(x) = f(g(x)) = f(x-7) = 2(x-7) +5= 2x–9
g? g(x) = g(g(x)) = g(x -7) = x-7-7= x–14
g? h(x) = h(g(x)) = h(x-7) = (x-7)/3
f –1(x) = (x - 5)/2
g –1(x) = x + 7
h–1(x) = 3x
