1
第 4章 二元关系与函数
? 4.1 集合的笛卡儿积与二元关系
? 4.2 关系的运算
? 4.3 关系的性质
? 4.4 关系的闭包
? 4.5 等价关系和偏序关系
? 4.6 函数的定义和性质
? 4.7 函数的复合和反函数
2
4.1 集合的笛卡儿积和二元关系
? 有序对
? 笛卡儿积及其性质
? 二元关系的定义
? 二元关系的表示
3
有序对
定义 由两个客体 x 和 y，按照一定的顺序组成的
二元组称为 有序对,记作 <x,y>
实例：点的直角坐标 (3,?4)
有序对性质
有序性 <x,y>?<y,x> （当 x? y时）
<x,y> 与 <u,v> 相等的充分必要条件是
<x,y>=<u,v> ? x=u ? y=v
例 1 <2,x+5> = <3y? 4,y>，求 x,y,
解 3y? 4 = 2,x+5 = y ? y = 2,x = ? 3
4
有序 n 元组
定义 一个 有序 n (n?3) 元组 <x1,x2,…,xn> 是一个
有序对，其中第一个元素是一个有序 n-1元组，即
<x1,x2,…,xn> = < <x1,x2,…,xn-1>,xn>
当 n=1时,<x> 形式上可以看成有序 1 元组,
实例 n 维向量是有序 n元组,
5
笛卡儿积
定义 设 A,B为集合,A与 B 的 笛卡儿积 记作 A?B,
即 A?B ={ <x,y> | x?A ? y?B }
例 2 A={1,2,3},B={a,b,c}
A?B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,
<3,a>,<3,b>,<3,c>}
B?A ={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,
<a,3>,<b,3>,<c,3>}
A={?},P(A)?A={<?,?>,<{?},?>}
6
笛卡儿积的性质
不适合交换律 A?B?B?A (A?B,A??,B??)
不适合结合律 (A?B)?C?A?(B?C) (A??,B??)
对于并或交运算满足分配律
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)
若 A或 B中有一个为空集，则 A?B就是空集,
A??=??B=?
若 |A|=m,|B|=n,则 |A?B|=mn
7
性质的证明
证明 A?(B?C)=(A?B)?(A?C)
证 任取 <x,y>
<x,y>∈ A× (B∪ C)
? x∈ A∧ y∈ B∪ C
? x∈ A∧ (y∈ B∨ y∈ C)
? (x∈ A∧ y∈ B)∨ (x∈ A∧ y∈ C)
? <x,y>∈ A× B∨ <x,y>∈ A× C
? <x,y>∈ (A× B)∪ (A× C)
所以有 A× (B∪ C) = (A× B)∪ (A× C),
8
例题
解 (1) 任取 <x,y>
<x,y>?A?C ? x?A ? y?C
? x?B ? y?D ? <x,y>?B?D
例 3 (1) 证明 A=B ? C=D ? A?C=B?D
(2) A?C=B?D是否推出 A=B ? C=D? 为什么？
(2) 不一定, 反例如下,
A={1},B={2},C=D=?,则 A?C=B?D 但是 A?B,
9
二元关系的定义
定义 如果一个集合满足以下条件之一,
（ 1）集合非空,且它的元素都是有序对
（ 2）集合是空集
则称该集合为一个 二元关系,简称为 关系,记作 R,
如 <x,y>∈ R,可记作 xRy；如果 <x,y>?R,则记作 x y
实例,R={<1,2>,<a,b>},S={<1,2>,a,b},
R是二元关系,当 a,b不是有序对时,S不是二元关系
根据上面的记法，可以写 1R2,aRb,a c 等,
10
从 A到 B的关系与 A上 的关系
定义 设 A,B为集合,A× B的任何子集所定义的二元
关系叫做 从 A到 B的二元关系,当 A=B时则叫做 A上
的二元关系,
例 4 A={0,1},B={1,2,3},R1={<0,2>},R2=A× B,
R3=?,R4={<0,1>},那么 R1,R2,R3,R4是从 A 到 B
的二元关系,R3和 R4同时也是 A上的二元关系,
计数
|A|=n,|A× A|=n2,A× A的子集有 个, 所以 A上有
个不同的二元关系,
例如 |A|=3,则 A上有 =512个不同的二元关系,
22n
22n
11
A上重要关系的实例
设 A 为任意集合,
?是 A 上的关系，称为 空关系
EA,IA 分别称为 全域关系 与 恒等关系,定义如下,
EA={<x,y>|x∈ A∧ y∈ A}=A× A
IA={<x,x>|x∈ A}
例如,A={1,2},则
EA={<1,1>,<1,2>,<2,1>,<2,2>}
IA={<1,1>,<2,2>}
12
A上重要关系的实例（续）
小于等于关系 LA,整除关系 DA,包含关系 R?定义,
LA={<x,y>| x,y∈ A∧ x≤y},A?R,R为实数集合
DB={<x,y>| x,y∈ B∧ x整除 y},
B?Z*,Z*为非 0整数集
R?={<x,y>| x,y∈ A∧ x?y},A是集合族,
类似的还可以定义大于等于关系,小于关系,大于
关系,真包含关系等等,
13
实例
例如 A = {1,2,3},B ={a,b},则
LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}
DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
A=P(B)={?,{a},{b},{a,b}},则 A上的包含关系是
R?={<?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,<{a},{a}>,
<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}
14
关系的表示
表示方式：关系的集合表达式、关系矩阵、关系图
关系矩阵,若 A={x1,x2,…,xm},B={y1,y2,…,yn}，
R是从 A到 B的关系,R的关系矩阵是布尔矩阵 MR =
[ rij ] m?n,其中 rij = 1? < xi,yj> ?R,
关系图,若 A= {x1,x2,…,xm},R是从 A上的关系,R
的关系图是 GR=<A,R>,其中 A为结点集,R为边集,
如果 <xi,xj>属于关系 R，在图中就有一条从 xi 到 xj
的有向边,
注意,A,B为有穷集，关系矩阵适于表示从 A到 B的
关系或者 A上的关系，关系图适于表示 A上的关系
15
实例
A={1,2,3,4},
R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},
R的关系矩阵 MR和关系图 GR如下,
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
0000
1100
0011
R
M
16
? 基本运算定义
?定义域、值域、域
?逆、合成、限制、像
? 基本运算的性质
? 幂运算
?定义
?求法
?性质
4.2 关系的运算
17
关系的基本运算定义
定义域, 值域 和 域
domR = { x | ?y (<x,y>?R) }
ranR = { y | ?x (<x,y>?R) }
fldR = domR ? ranR
例 1 R={<1,2>,<1,3>,<2,4>,<4,3>},则
domR={1,2,4}
ranR={2,3,4}
fldR={1,2,3,4}
18
关系的基本运算定义（续）
逆 与 合成
R?1 = {<y,x> | <x,y>?R}
R°S = |<x,z> | ? y (<x,y>?R?<y,z>?S) }
例 2 R={<1,2>,<2,3>,<1,4>,<2,2>}
S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}
R?1={<2,1>,<3,2>,<4,1>,<2,2>}
R°S ={<1,3>,<2,2>,<2,3>}
S°R ={<1,2>,<1,4>,<3,2>,<3,3>}
19
合成运算的图示方法
利用图示（不是关系图）方法求合成
R°S ={<1,3>,<2,2>,<2,3>}
S°R ={<1,2>,<1,4>,<3,2>,<3,3>}
20
限制与像
定义 F 在 A上的 限制
F?A = {<x,y> | xFy ? x?A}
A 在 F下的 像
F[A] = ran(F?A)
实例 R={<1,2>,<2,3>,<1,4>,<2,2>}
R?{1}={<1,2>,<1,4>}
R[{1}]={2,4}
R??=?
R[{1,2}]={2,3,4}
注意,F?A?F,F[A] ?ranF
21
关系基本运算的性质
定理 1 设 F是任意的关系,则
(1) (F?1)?1=F
(2) domF?1=ranF,ranF?1=domF
证 (1) 任取 <x,y>,由逆的定义有
<x,y>∈ (F ? 1)?1 ? <y,x>∈ F?1 ? <x,y>∈ F
所以有 (F?1)?1=F
(2) 任取 x,
x∈ domF?1 ? ?y(<x,y>∈ F?1)
? ?y(<y,x>∈ F) ? x∈ ranF
所以有 domF?1= ranF,同理可证 ranF?1 = domF,
22
定理 2 设 F,G,H是任意的关系,则
(1) (F°G)°H=F°(G°H)
(2) (F°G)?1= G?1°F?1
证 (1) 任取 <x,y>,
<x,y>?(F°G)°H ??t(<x,t>∈ F°G∧ <t,y>∈ H)
? ?t (?s(<x,s>∈ F∧ <s,t>∈ G)∧ <t,y>∈ H)
? ?t ?s (<x,s>∈ F∧ <s,t>∈ G∧ <t,y>∈ H)
? ?s (<x,s>∈ F∧ ?t (<s,t>∈ G∧ <t,y>∈ H))
? ?s (<x,s>∈ F∧ <s,y>∈ G°H)
? <x,y>∈ F°(G°H)
所以 (F°G)°H = F°(G°H)
关系基本运算的性质（续）
23
(2) 任取 <x,y>,
<x,y>∈ (F°G)?1
? <y,x>∈ F°G
? ?t (<y,t>∈ F∧ (t,x)∈ G)
? ?t (<x,t>∈ G?1∧ (t,y)∈ F?1)
? <x,y>∈ G?1°F?1
所以 (F°G)?1 = G?1°F?1
关系基本运算的性质（续）
24
A上关系的幂运算
设 R为 A上的关系,n为自然数,则 R 的 n次幂 定义为,
(1) R0={<x,x> | x∈ A }=IA
(2) Rn+1 = Rn°R
注意,
对于 A上的任何关系 R1和 R2都有
R10 = R20 = IA
对于 A上的任何关系 R 都有
R1 = R
25
幂的求法
对于集合表示的关系 R，计算 Rn 就是 n个 R右复合,
矩阵表示就是 n个矩阵相乘,其中相加采用逻辑加,
例 3 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},
求 R的各次幂,分别用矩阵和关系图表示,
解 R与 R2的关系矩阵分别为
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
1000
0101
0010
M
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
1010
0101
0000
1000
0101
0010
0000
1000
0101
0010
2
M
26
同理,R0=IA,R3和 R4的矩阵分别是,
因此 M4=M2,即 R4=R2,因此可以得到
R2=R4=R6=…,R3=R5=R7=…
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
1010
0101
,
0000
0000
0101
1010
43
MM
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0100
0010
0001
0
M
幂的求法（续）
27
R0,R1,R2,R3,… 的关系图如下图所示
幂的求法（续）
28
幂运算的性质
定理 3 设 A为 n元集,R是 A上的关系,则存在自然
数 s 和 t,使得 Rs = Rt,
证 R为 A上的关系,由于 |A|=n,A上的不同关系只
有 个,
当列出 R 的各次幂
R0,R1,R2,…,,…,
必存在自然数 s 和 t 使得 Rs=Rt,
22n
29
定理 4 设 R 是 A 上的关系,m,n∈ N,则
(1) Rm°Rn=Rm+n
(2) (Rm)n=Rmn
证 用归纳法
(1) 对于任意给定的 m∈ N,施归纳于 n,
若 n=0,则有
Rm°R0=Rm°IA=Rm=Rm+0
假设 Rm°Rn=Rm+n,则有
Rm°Rn+1=Rm°(Rn°R)=(Rm°Rn)°R=Rm+n+1,
所以对一切 m,n∈ N有 Rm°Rn=Rm+n,
幂运算的性质（续）
30
(接上页证明 )
(2) 对于任意给定的 m∈ N,施归纳于 n,
若 n=0,则有
(Rm)0=IA=R0=Rm× 0
假设 (Rm)n=Rmn,则有
(Rm)n+1=(Rm)n°Rm=(Rmn)°Rm=Rmn+m=Rm(n+1)
所以对一切 m,n∈ N 有 (Rm)n=Rmn,
幂运算的性质（续）
第 4章 二元关系与函数
? 4.1 集合的笛卡儿积与二元关系
? 4.2 关系的运算
? 4.3 关系的性质
? 4.4 关系的闭包
? 4.5 等价关系和偏序关系
? 4.6 函数的定义和性质
? 4.7 函数的复合和反函数
2
4.1 集合的笛卡儿积和二元关系
? 有序对
? 笛卡儿积及其性质
? 二元关系的定义
? 二元关系的表示
3
有序对
定义 由两个客体 x 和 y，按照一定的顺序组成的
二元组称为 有序对,记作 <x,y>
实例：点的直角坐标 (3,?4)
有序对性质
有序性 <x,y>?<y,x> （当 x? y时）
<x,y> 与 <u,v> 相等的充分必要条件是
<x,y>=<u,v> ? x=u ? y=v
例 1 <2,x+5> = <3y? 4,y>，求 x,y,
解 3y? 4 = 2,x+5 = y ? y = 2,x = ? 3
4
有序 n 元组
定义 一个 有序 n (n?3) 元组 <x1,x2,…,xn> 是一个
有序对，其中第一个元素是一个有序 n-1元组，即
<x1,x2,…,xn> = < <x1,x2,…,xn-1>,xn>
当 n=1时,<x> 形式上可以看成有序 1 元组,
实例 n 维向量是有序 n元组,
5
笛卡儿积
定义 设 A,B为集合,A与 B 的 笛卡儿积 记作 A?B,
即 A?B ={ <x,y> | x?A ? y?B }
例 2 A={1,2,3},B={a,b,c}
A?B ={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,
<3,a>,<3,b>,<3,c>}
B?A ={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,
<a,3>,<b,3>,<c,3>}
A={?},P(A)?A={<?,?>,<{?},?>}
6
笛卡儿积的性质
不适合交换律 A?B?B?A (A?B,A??,B??)
不适合结合律 (A?B)?C?A?(B?C) (A??,B??)
对于并或交运算满足分配律
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)
若 A或 B中有一个为空集，则 A?B就是空集,
A??=??B=?
若 |A|=m,|B|=n,则 |A?B|=mn
7
性质的证明
证明 A?(B?C)=(A?B)?(A?C)
证 任取 <x,y>
<x,y>∈ A× (B∪ C)
? x∈ A∧ y∈ B∪ C
? x∈ A∧ (y∈ B∨ y∈ C)
? (x∈ A∧ y∈ B)∨ (x∈ A∧ y∈ C)
? <x,y>∈ A× B∨ <x,y>∈ A× C
? <x,y>∈ (A× B)∪ (A× C)
所以有 A× (B∪ C) = (A× B)∪ (A× C),
8
例题
解 (1) 任取 <x,y>
<x,y>?A?C ? x?A ? y?C
? x?B ? y?D ? <x,y>?B?D
例 3 (1) 证明 A=B ? C=D ? A?C=B?D
(2) A?C=B?D是否推出 A=B ? C=D? 为什么？
(2) 不一定, 反例如下,
A={1},B={2},C=D=?,则 A?C=B?D 但是 A?B,
9
二元关系的定义
定义 如果一个集合满足以下条件之一,
（ 1）集合非空,且它的元素都是有序对
（ 2）集合是空集
则称该集合为一个 二元关系,简称为 关系,记作 R,
如 <x,y>∈ R,可记作 xRy；如果 <x,y>?R,则记作 x y
实例,R={<1,2>,<a,b>},S={<1,2>,a,b},
R是二元关系,当 a,b不是有序对时,S不是二元关系
根据上面的记法，可以写 1R2,aRb,a c 等,
10
从 A到 B的关系与 A上 的关系
定义 设 A,B为集合,A× B的任何子集所定义的二元
关系叫做 从 A到 B的二元关系,当 A=B时则叫做 A上
的二元关系,
例 4 A={0,1},B={1,2,3},R1={<0,2>},R2=A× B,
R3=?,R4={<0,1>},那么 R1,R2,R3,R4是从 A 到 B
的二元关系,R3和 R4同时也是 A上的二元关系,
计数
|A|=n,|A× A|=n2,A× A的子集有 个, 所以 A上有
个不同的二元关系,
例如 |A|=3,则 A上有 =512个不同的二元关系,
22n
22n
11
A上重要关系的实例
设 A 为任意集合,
?是 A 上的关系，称为 空关系
EA,IA 分别称为 全域关系 与 恒等关系,定义如下,
EA={<x,y>|x∈ A∧ y∈ A}=A× A
IA={<x,x>|x∈ A}
例如,A={1,2},则
EA={<1,1>,<1,2>,<2,1>,<2,2>}
IA={<1,1>,<2,2>}
12
A上重要关系的实例（续）
小于等于关系 LA,整除关系 DA,包含关系 R?定义,
LA={<x,y>| x,y∈ A∧ x≤y},A?R,R为实数集合
DB={<x,y>| x,y∈ B∧ x整除 y},
B?Z*,Z*为非 0整数集
R?={<x,y>| x,y∈ A∧ x?y},A是集合族,
类似的还可以定义大于等于关系,小于关系,大于
关系,真包含关系等等,
13
实例
例如 A = {1,2,3},B ={a,b},则
LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}
DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}
A=P(B)={?,{a},{b},{a,b}},则 A上的包含关系是
R?={<?,?>,<?,{a}>,<?,{b}>,<?,{a,b}>,<{a},{a}>,
<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}
14
关系的表示
表示方式：关系的集合表达式、关系矩阵、关系图
关系矩阵,若 A={x1,x2,…,xm},B={y1,y2,…,yn}，
R是从 A到 B的关系,R的关系矩阵是布尔矩阵 MR =
[ rij ] m?n,其中 rij = 1? < xi,yj> ?R,
关系图,若 A= {x1,x2,…,xm},R是从 A上的关系,R
的关系图是 GR=<A,R>,其中 A为结点集,R为边集,
如果 <xi,xj>属于关系 R，在图中就有一条从 xi 到 xj
的有向边,
注意,A,B为有穷集，关系矩阵适于表示从 A到 B的
关系或者 A上的关系，关系图适于表示 A上的关系
15
实例
A={1,2,3,4},
R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},
R的关系矩阵 MR和关系图 GR如下,
?
?
?
?
?
?
?
?
?
?
?
?
?
0010
0000
1100
0011
R
M
16
? 基本运算定义
?定义域、值域、域
?逆、合成、限制、像
? 基本运算的性质
? 幂运算
?定义
?求法
?性质
4.2 关系的运算
17
关系的基本运算定义
定义域, 值域 和 域
domR = { x | ?y (<x,y>?R) }
ranR = { y | ?x (<x,y>?R) }
fldR = domR ? ranR
例 1 R={<1,2>,<1,3>,<2,4>,<4,3>},则
domR={1,2,4}
ranR={2,3,4}
fldR={1,2,3,4}
18
关系的基本运算定义（续）
逆 与 合成
R?1 = {<y,x> | <x,y>?R}
R°S = |<x,z> | ? y (<x,y>?R?<y,z>?S) }
例 2 R={<1,2>,<2,3>,<1,4>,<2,2>}
S={<1,1>,<1,3>,<2,3>,<3,2>,<3,3>}
R?1={<2,1>,<3,2>,<4,1>,<2,2>}
R°S ={<1,3>,<2,2>,<2,3>}
S°R ={<1,2>,<1,4>,<3,2>,<3,3>}
19
合成运算的图示方法
利用图示（不是关系图）方法求合成
R°S ={<1,3>,<2,2>,<2,3>}
S°R ={<1,2>,<1,4>,<3,2>,<3,3>}
20
限制与像
定义 F 在 A上的 限制
F?A = {<x,y> | xFy ? x?A}
A 在 F下的 像
F[A] = ran(F?A)
实例 R={<1,2>,<2,3>,<1,4>,<2,2>}
R?{1}={<1,2>,<1,4>}
R[{1}]={2,4}
R??=?
R[{1,2}]={2,3,4}
注意,F?A?F,F[A] ?ranF
21
关系基本运算的性质
定理 1 设 F是任意的关系,则
(1) (F?1)?1=F
(2) domF?1=ranF,ranF?1=domF
证 (1) 任取 <x,y>,由逆的定义有
<x,y>∈ (F ? 1)?1 ? <y,x>∈ F?1 ? <x,y>∈ F
所以有 (F?1)?1=F
(2) 任取 x,
x∈ domF?1 ? ?y(<x,y>∈ F?1)
? ?y(<y,x>∈ F) ? x∈ ranF
所以有 domF?1= ranF,同理可证 ranF?1 = domF,
22
定理 2 设 F,G,H是任意的关系,则
(1) (F°G)°H=F°(G°H)
(2) (F°G)?1= G?1°F?1
证 (1) 任取 <x,y>,
<x,y>?(F°G)°H ??t(<x,t>∈ F°G∧ <t,y>∈ H)
? ?t (?s(<x,s>∈ F∧ <s,t>∈ G)∧ <t,y>∈ H)
? ?t ?s (<x,s>∈ F∧ <s,t>∈ G∧ <t,y>∈ H)
? ?s (<x,s>∈ F∧ ?t (<s,t>∈ G∧ <t,y>∈ H))
? ?s (<x,s>∈ F∧ <s,y>∈ G°H)
? <x,y>∈ F°(G°H)
所以 (F°G)°H = F°(G°H)
关系基本运算的性质（续）
23
(2) 任取 <x,y>,
<x,y>∈ (F°G)?1
? <y,x>∈ F°G
? ?t (<y,t>∈ F∧ (t,x)∈ G)
? ?t (<x,t>∈ G?1∧ (t,y)∈ F?1)
? <x,y>∈ G?1°F?1
所以 (F°G)?1 = G?1°F?1
关系基本运算的性质（续）
24
A上关系的幂运算
设 R为 A上的关系,n为自然数,则 R 的 n次幂 定义为,
(1) R0={<x,x> | x∈ A }=IA
(2) Rn+1 = Rn°R
注意,
对于 A上的任何关系 R1和 R2都有
R10 = R20 = IA
对于 A上的任何关系 R 都有
R1 = R
25
幂的求法
对于集合表示的关系 R，计算 Rn 就是 n个 R右复合,
矩阵表示就是 n个矩阵相乘,其中相加采用逻辑加,
例 3 设 A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},
求 R的各次幂,分别用矩阵和关系图表示,
解 R与 R2的关系矩阵分别为
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
1000
0101
0010
M
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
1010
0101
0000
1000
0101
0010
0000
1000
0101
0010
2
M
26
同理,R0=IA,R3和 R4的矩阵分别是,
因此 M4=M2,即 R4=R2,因此可以得到
R2=R4=R6=…,R3=R5=R7=…
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0000
0000
1010
0101
,
0000
0000
0101
1010
43
MM
?
?
?
?
?
?
?
?
?
?
?
?
?
1000
0100
0010
0001
0
M
幂的求法（续）
27
R0,R1,R2,R3,… 的关系图如下图所示
幂的求法（续）
28
幂运算的性质
定理 3 设 A为 n元集,R是 A上的关系,则存在自然
数 s 和 t,使得 Rs = Rt,
证 R为 A上的关系,由于 |A|=n,A上的不同关系只
有 个,
当列出 R 的各次幂
R0,R1,R2,…,,…,
必存在自然数 s 和 t 使得 Rs=Rt,
22n
29
定理 4 设 R 是 A 上的关系,m,n∈ N,则
(1) Rm°Rn=Rm+n
(2) (Rm)n=Rmn
证 用归纳法
(1) 对于任意给定的 m∈ N,施归纳于 n,
若 n=0,则有
Rm°R0=Rm°IA=Rm=Rm+0
假设 Rm°Rn=Rm+n,则有
Rm°Rn+1=Rm°(Rn°R)=(Rm°Rn)°R=Rm+n+1,
所以对一切 m,n∈ N有 Rm°Rn=Rm+n,
幂运算的性质（续）
30
(接上页证明 )
(2) 对于任意给定的 m∈ N,施归纳于 n,
若 n=0,则有
(Rm)0=IA=R0=Rm× 0
假设 (Rm)n=Rmn,则有
(Rm)n+1=(Rm)n°Rm=(Rmn)°Rm=Rmn+m=Rm(n+1)
所以对一切 m,n∈ N 有 (Rm)n=Rmn,
幂运算的性质（续）
