离散数学-关系的概念、表示和运算
0前言
函数是x 到y 的映射,这种映射反就是一种关系。因为定义域x 是一个集合、值域y 也是一个集合所以函数就是一个<x, y> 有序对的集合。因此,我们可以通过二元关系来定义函数的概念,利用有序对的集合来表示函数。
1 有序对与笛卡尔积
1.1 有序对
定义: 由两个元素 x 和 y,按照一定的顺序组成的二元组称为 有序对 ,记作<x,y>。
性质: 1.当x≠y时, 有序性 <x,y>≠<y,x>;
2.<x,y>=<u,v>的充分必要条件是x=u且y=v。
例1 <x+2,4> = <5,2x+y>,求 x和 y.
解:由有序对相等的充要条件有:
{
x
+
2
=
5
2
x
+
y
=
4
\begin{cases} x+2=5\\ 2x+y=4 \end{cases}
{x+2=52x+y=4
解得:x=3,y=-2.
1.2 笛卡尔积
定义 设A,B为集合,A与B 的笛卡儿积记作AXB, 即 A X B ={ <x,y> | x
∈
\in
∈A
∧
\wedge
∧ y
∈
\in
∈B }
例2 A={a,b},B={0,1,2}则:
AXB={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}
BXA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>}
例3 A={
Ø
\text{\O}
Ø},P(A)XA
P(A)={{
Ø
\text{\O}
Ø}}
P(A)XA={<
Ø
\text{\O}
Ø,
Ø
\text{\O}
Ø>,<{
Ø
\text{\O}
Ø},
Ø
\text{\O}
Ø>}
1.3 笛卡尔积得性质
(1)不满足交换律 AXB≠BXA (A≠B,A≠
Ø
\text{\O}
Ø,B≠
Ø
\text{\O}
Ø)
(2)不满足结合律 (AXB)XC≠AX(BXC) (A≠
Ø
\text{\O}
Ø,B≠
Ø
\text{\O}
Ø)
(3)对于并或交运算满足分配律
AX(B∪C)=(AXB)∪(AXC)
(B∪C)XA=(BXA)∪(CXA)
AX(B∩C)=(AXB)∩(AXC)
(B∩C)XA=(BXA)∩(CXA)
(4) A
⊆
\sube
⊆C
∧
\land
∧B
⊆
\sube
⊆D
⇒
\rArr
⇒AXB
⊆
\sube
⊆CXD
证明:
(1)由定义可得:AX
Ø
\text{\O}
Ø=
Ø
\text{\O}
Ø,
Ø
\text{\O}
ØXA=
Ø
\text{\O}
Ø
设A=B
⇒
\rArr
⇒A=
Ø
\text{\O}
Ø
∨
\lor
∨B=
Ø
\text{\O}
Ø
可推出满足交换律
(2)当A=
Ø
\text{\O}
Ø
∨
\lor
∨B=
Ø
\text{\O}
Ø
∨
\lor
∨C=
Ø
\text{\O}
Ø时,结果等于
Ø
\text{\O}
Ø,满足结合律。
(3)任取<x,y>
<x,y>∈AX(B∪C)
⇔
\Harr
⇔x∈A
∧
\land
∧y∈B∪C
⇔
\Harr
⇔x∈A
∧
\land
∧(y∈B
∨
\lor
∨y∈C)
⇔
\Harr
⇔(x∈A
∧
\land
∧y∈B)
∨
\lor
∨(x∈A
∧
\land
∧y∈C)
⇔
\Harr
⇔<x,y>∈AXB
∨
\lor
∨<x,y>∈AXC
⇔
\Harr
⇔<x,y>∈(AXB)∪(AXC)
所以有AX(B∪C)=(AXB)∪(AXC)
2 关系的定义
2.1 二元关系
定义 如果一个集合满足以下条件之一, 则称该集合为一个二元关系, 简称为关系,记作R.
(1)集合非空, 且它的元素都是有序对
(2)集合是空集
如<x,y>∈R, 可记作 xRy;
实例:R={<1,2>,<a,b>}, S={<1,2>,a,b}.
R是二元关系, 当a, b不是有序对时,S不是二元关系。
2.2 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={<0,1>}. 那么 R1, R2, R3 是从 A 到 B的二元关系, R3 也是 A上的二元关系.
集合A上的二元关系的数目依赖于A中的元素个数,如果|A|=n, |A×A|=
n
2
n^2
n2, A×A的子集有
2
n
2
2^{n^2}
2n2个. 每一个子集代表一个A上的二元关系,所以 A上有
2
n
2
2^{n^2}
2n2个不同的二元关系.
例如 |A|=3, 则 A上有
2
3
2
2^{3^2}
232=512个不同的二元关系.
|A|=m,|B|=n则AXB的元素数|AXB|=mn,AXB有
2
m
⋅
2
n
=
2
m
n
2^m·2^n=2^{mn}
2m⋅2n=2mn不同的二元关系。
2.3 关系的类型
空关系:设 A 为任意集合,空集
Ø
\text{\O}
Ø是 AXA的子集,称为空关系.
全域关系
E
A
E_A
EA:
E
A
E_A
EA={<x,y>|x∈A
∧
\land
∧y∈A}=AXA
恒等关系
I
A
I_A
IA:
I
A
I_A
IA={<x,x>|x∈A}
小于等于关系
L
A
L_A
LA:
L
A
L_A
LA={<x,y>|x,y∈A
∧
\land
∧x≤y},A
⊆
\sube
⊆R,R为实数集
整除关系
D
A
D_A
DA:
D
A
D_A
DA={<x,y>|x,y∈B
∧
\land
∧x整除y},B
⊆
\sube
⊆Z*,Z*为非0整数
包含关系
R
⊆
R_\sube
R⊆:
R
⊆
R_\sube
R⊆={<x,y>|x,y∈A
∧
\land
∧x
⊆
\sube
⊆y},A是集合族
例如, A={1,2}, 则
E
A
E_A
EA={<1,1>,<1,2>,<2,1>,<2,2>}
I
A
I_A
IA={<1,1>,<2,2>}
例如A={1,2,3},B={a,b},则
L
A
L_A
LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,< 3,3>}
D
A
D_A
DA={<1,1>,<1,2>,<1,3>,<2,2>,< 3,3>}
A=P(B)={
Ø
\text{\O}
Ø,{a},{b},{a,b}}
R
⊆
R_\sube
R⊆={<
Ø
\text{\O}
Ø,
Ø
\text{\O}
Ø>,<
Ø
\text{\O}
Ø,{a}>,<
Ø
\text{\O}
Ø,{b}>,<
Ø
\text{\O}
Ø,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}
2.4 关系表示
关系的表示方式有三种:关系的集合表达式、关系矩阵、关系图。
关系集合表达式:A X B ={ <x,y> | x
∈
\in
∈A
∧
\wedge
∧ y
∈
\in
∈B }
关系矩阵:若A={
a
1
,
a
2
,
a
3
.
.
.
.
.
.
a
m
a_1,a_2,a_3......a_m
a1,a2,a3......am},B={
b
1
,
b
2
,
b
3
.
.
.
.
.
.
.
b
n
b_1,b_2,b_3.......b_n
b1,b2,b3.......bn}R是从A到B的关系,R的关系是R={
<
a
1
,
b
1
>
,
<
a
2
,
b
2
>
,
.
.
.
.
.
,
<
a
m
,
b
n
>
<a_1,b_1>,<a_2,b_2>,.....,<a_m,b_n>
<a1,b1>,<a2,b2>,.....,<am,bn>}矩阵是:
关系图: 若A= {
x
1
,
x
2
,
…
,
x
m
x_1, x_2, …, x_m
x1,x2,…,xm},R是从A上的关系,R的关系图是
G
R
G_R
GR=<A, R>, 其中A为结点集,R为边集.如果<
x
i
,
x
j
x_i,x_j
xi,xj>属于关系R,在图中就有一条从
x
i
x_i
xi 到
x
j
x_j
xj的有向边.
注意:A, B为有穷集,关系矩阵适于表示从A到B的关系或者A上的关系,关系图适于表示A上的关系。
例如:A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},则R的关系矩阵和关系图。
3 关系的运算
3.1 定义域、 值域和 域,逆,复合
d
o
m
R
domR
domR={
x
∣
∃
y
(
<
x
,
y
>
∈
R
)
x|\exists y(<x,y>∈R)
x∣∃y(<x,y>∈R)}
r
a
n
R
ranR
ranR={
y
∣
∃
y
(
<
x
,
y
>
∈
R
)
y|\exists y(<x,y>∈R)
y∣∃y(<x,y>∈R)}
f
l
d
R
=
d
o
m
R
∪
r
a
n
R
fldR=domR∪ranR
fldR=domR∪ranR
R
−
1
R^{-1}
R−1={
<
x
,
y
>
∣
<
x
,
y
>
∈
R
<x,y>|<x,y>∈R
<x,y>∣<x,y>∈R}
R
∘
S
R\circ S
R∘S={
<
x
,
z
>
∣
∃
y
(
<
x
,
y
>
∈
R
∧
<
y
,
z
>
∈
S
)
<x,z>|\exists y(<x,y>∈R\land<y,z>∈S)
<x,z>∣∃y(<x,y>∈R∧<y,z>∈S)}
例如:R={<1,2>,<1,3>,<2,4>,<4,3>}
d
o
m
R
domR
domR={1,2,4} 每个有序对的第一个值
r
a
n
R
ranR
ranR={2,3,4} 每个有序对的第二个值
f
l
d
R
fldR
fldR={1,2,3,4}
R
−
1
R^{-1}
R−1={<2,1>,< 3,1>,<4,2>,< 3,4>} 有序对的第一个值和第二个值颠倒
设S={<2,5>,< 3,4>}
R
∘
S
R\circ S
R∘S={<1,5>,<1,4>,<4,4>} 即R中的<1,2>和S中的<2,5>复合可得<1,5>; <1,3><3,4 >复合<1,4>
3.2 限制与像
(1)R在A上的限制记作R
↾
\upharpoonright
↾A,其中:R
↾
\upharpoonright
↾A={<x,y>|xRy
∧
\land
∧x∈A}
(2)A在R下的像记作R[A],其中R[A]=ran(R
↾
\upharpoonright
↾A)
例如:R={<1,2>,<1,3>,<2,2>,<2,4>,< 3,2>}则
R
↾
\upharpoonright
↾{1}={<1,2>,<1,3>} x值为1的有序对
R
↾
\upharpoonright
↾
Ø
\text{\O}
Ø=
Ø
\text{\O}
Ø
R
↾
\upharpoonright
↾{2,3}={<2,2>,<2,4>,< 3,2>} x值为2或3的有序对
R[{1}]=ran(R
↾
\upharpoonright
↾{1})={2,3} R
↾
\upharpoonright
↾{1}中有序对的值域
R[
Ø
\text{\O}
Ø]=
Ø
\text{\O}
Ø
R[{3}]={2} 其中R
↾
\upharpoonright
↾{3}={< 3,2>},结果为其值域
3.2 关系中的恒等式
⧫
\blacklozenge
⧫设
F
F
F是任意的关系,则:
(1)(
F
−
1
)
−
1
F^{-1})^{-1}
F−1)−1=
F
F
F
(2)
d
o
m
F
−
1
=
r
a
n
F
,
r
a
n
F
−
1
=
d
o
m
F
domF^{-1}=ranF,ranF^{-1}=domF
domF−1=ranF,ranF−1=domF
证:(1)任取<x,y>,由逆的定义有:
<x,y>∈
(
F
−
1
)
−
1
(F^{-1})^{-1}
(F−1)−1
⇔
\Harr
⇔<y,x>∈
F
−
1
F^{-1}
F−1
⇔
\Harr
⇔<x,y>∈
F
F
F
所以有(
F
−
1
)
−
1
F^{-1})^{-1}
F−1)−1=
F
F
F。
(2)任取
x
x
x
x
x
x∈
d
o
m
F
−
1
domF^{-1}
domF−1
⇔
\Harr
⇔
∃
\exists
∃y(<x,y>∈
F
−
1
F^{-1}
F−1)
⇔
\Harr
⇔
∃
\exists
∃y(<y,x>∈
F
F
F)
⇔
\Harr
⇔
x
∈
r
a
n
F
x∈ranF
x∈ranF
所以有
r
a
n
F
−
1
=
d
o
m
F
ranF^{-1}=domF
ranF−1=domF
⧫
\blacklozenge
⧫设
F
,
G
,
H
F,G,H
F,G,H是任意的关系,则:
(3)
(
F
∘
G
)
∘
H
(F\circ G)\circ H
(F∘G)∘H=
F
∘
(
G
∘
H
)
F\circ (G\circ H)
F∘(G∘H)
(4)
(
F
∘
G
)
−
1
(F\circ G)^{-1}
(F∘G)−1=
G
−
1
∘
F
−
1
G^{-1}\circ F^{-1}
G−1∘F−1
证:(3)任取<x,y>,
<x,y>∈
(
F
∘
G
)
∘
H
(F\circ G)\circ H
(F∘G)∘H
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
F
∘
G
∧
<
t
,
y
>
∈
H
)
\exists t(<x,t>∈F\circ G\land<t,y>∈H)
∃t(<x,t>∈F∘G∧<t,y>∈H)
⇔
\Harr
⇔
∃
t
(
∃
s
(
<
x
,
s
>
∈
F
∧
<
s
,
t
>
∈
G
)
∧
<
t
,
y
>
∈
H
)
\exists t(\exists s(<x,s>∈F\land<s,t>∈ G)\land<t,y>∈H)
∃t(∃s(<x,s>∈F∧<s,t>∈G)∧<t,y>∈H)
⇔
\Harr
⇔
∃
t
∃
s
(
<
x
,
s
>
∈
F
∧
<
s
,
t
>
∈
G
∧
<
t
,
y
>
∈
H
)
\exists t\exists s(<x,s>∈F\land<s,t>∈ G\land<t,y>∈H)
∃t∃s(<x,s>∈F∧<s,t>∈G∧<t,y>∈H)
⇔
\Harr
⇔
∃
s
(
<
x
,
s
>
∈
F
∧
∃
t
(
<
s
,
t
>
∈
G
∧
<
t
,
y
>
∈
H
)
\exists s(<x,s>∈F\land\exists t(<s,t>∈ G\land<t,y>∈H)
∃s(<x,s>∈F∧∃t(<s,t>∈G∧<t,y>∈H)
⇔
\Harr
⇔
∃
s
(
<
x
,
s
>
∈
F
∧
<
s
,
y
>
∈
G
∘
H
)
\exists s(<x,s>∈F\land<s,y>∈G\circ H)
∃s(<x,s>∈F∧<s,y>∈G∘H)
⇔
\Harr
⇔<x,y>∈
F
∘
(
G
∘
H
)
F\circ (G\circ H)
F∘(G∘H)
所以
(
F
∘
G
)
∘
H
(F\circ G)\circ H
(F∘G)∘H=
F
∘
(
G
∘
H
)
F\circ (G\circ H)
F∘(G∘H)
(4)任取<x,y>,
<x,y>∈
(
F
∘
G
)
−
1
(F\circ G)^{-1}
(F∘G)−1
⇔
\Harr
⇔<y,x>∈
(
F
∘
G
)
(F\circ G)
(F∘G)
⇔
\Harr
⇔
∃
t
(
<
y
,
t
>
∈
F
∧
<
t
,
x
>
∈
G
)
\exists t(<y,t>∈F\land<t,x>∈G)
∃t(<y,t>∈F∧<t,x>∈G)
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
G
−
1
∧
<
t
,
y
>
∈
F
−
1
)
\exists t(<x,t>∈G^{-1}\land<t,y>∈F^{-1})
∃t(<x,t>∈G−1∧<t,y>∈F−1)
⇔
\Harr
⇔<x,y>∈
G
−
1
∘
F
−
1
G^{-1}\circ F^{-1}
G−1∘F−1
所以:
(
F
∘
G
)
−
1
(F\circ G)^{-1}
(F∘G)−1=
G
−
1
∘
F
−
1
G^{-1}\circ F^{-1}
G−1∘F−1
⧫
\blacklozenge
⧫设R为A上的关系则:
(5)
R
∘
I
A
R\circ I_A
R∘IA=
I
A
∘
R
I_A\circ R
IA∘R=
R
R
R
证: 任取<x,y>
<x,y>∈
R
∘
I
A
R\circ I_A
R∘IA
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
R
∧
<
t
,
y
>
∈
I
A
)
\exists t(<x,t>∈R\land<t,y>∈I_A)
∃t(<x,t>∈R∧<t,y>∈IA)
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
R
∧
t
=
y
∧
y
∈
A
)
\exists t(<x,t>∈R\land t=y\land y∈A)
∃t(<x,t>∈R∧t=y∧y∈A)
⇔
\Harr
⇔<x,y>∈
R
R
R
⧫
\blacklozenge
⧫设
F
,
G
,
H
F,G,H
F,G,H的任意关系,则:
(6)
F
∘
(
G
∪
H
)
=
F
∘
G
∪
F
∘
H
F\circ (G∪H)=F\circ G∪F\circ H
F∘(G∪H)=F∘G∪F∘H
(7)
(
G
∪
H
)
∘
F
=
G
∘
F
∪
H
∘
F
(G∪H)\circ F=G\circ F∪H\circ F
(G∪H)∘F=G∘F∪H∘F
(8)
F
∘
(
G
∩
H
)
⊆
F
∘
G
∩
F
∘
H
F\circ (G∩H)\sube F\circ G∩F\circ H
F∘(G∩H)⊆F∘G∩F∘H
(9)
(
G
∩
H
)
∘
F
⊆
G
∘
F
∩
H
∘
F
(G∩H)\circ F \sube G\circ F∩H\circ F
(G∩H)∘F⊆G∘F∩H∘F
证: (8)任取<x,y>,
<x,y>∈
F
∘
(
G
∩
H
)
F\circ (G∩H)
F∘(G∩H)
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
G
∩
H
)
\exists t(<x,t>∈F\land<t,y>∈G∩H)
∃t(<x,t>∈F∧<t,y>∈G∩H)
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
G
∧
<
t
,
y
>
∈
H
)
\exists t(<x,t>∈F\land<t,y>∈G\land <t,y>∈H)
∃t(<x,t>∈F∧<t,y>∈G∧<t,y>∈H)
⇔
\Harr
⇔
∃
t
(
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
G
)
∧
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
H
)
)
\exists t((<x,t>∈F\land<t,y>∈G)\land (<x,t>∈F\land<t,y>∈H))
∃t((<x,t>∈F∧<t,y>∈G)∧(<x,t>∈F∧<t,y>∈H))
⇔
\Harr
⇔
∃
t
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
G
)
∧
∃
t
(
<
x
,
t
>
∈
F
∧
<
t
,
y
>
∈
H
)
\exists t(<x,t>∈F\land<t,y>∈G)\land \exists t(<x,t>∈F\land<t,y>∈H)
∃t(<x,t>∈F∧<t,y>∈G)∧∃t(<x,t>∈F∧<t,y>∈H)
⇔
\Harr
⇔<x,y>∈
F
∘
G
∧
<
x
,
y
>
∈
F
∘
H
F\circ G\land<x,y>∈F\circ H
F∘G∧<x,y>∈F∘H
⇔
\Harr
⇔<x,y>∈
F
∘
G
∩
F
∘
H
F\circ G∩F\circ H
F∘G∩F∘H
所以有
F
∘
(
G
∩
H
)
⊆
F
∘
G
∩
F
∘
H
F\circ (G∩H)\sube F\circ G∩F\circ H
F∘(G∩H)⊆F∘G∩F∘H
⧫
\blacklozenge
⧫设F为关系,A,B为集合,则:
(10)F
↾
\upharpoonright
↾(A∪B)=F
↾
\upharpoonright
↾A∪F
↾
\upharpoonright
↾B
(11)F[A∪B]=F[A]∪F[B]
(12)F
↾
\upharpoonright
↾(A∩B)=F
↾
\upharpoonright
↾A∩F
↾
\upharpoonright
↾B
(13)F[A∩B]=F[A]∩F[B]
证:(11)任取<x,y>
<x,y>∈F
↾
\upharpoonright
↾(A∪B)
⇔
\Harr
⇔<x,y>∈
F
∧
x
∈
A
∪
B
F\land x∈A∪B
F∧x∈A∪B
⇔
\Harr
⇔<x,y>∈
F
∧
(
x
∈
A
∨
x
∈
B
)
F\land (x∈A\lor x∈B)
F∧(x∈A∨x∈B)
⇔
\Harr
⇔(<x,y>∈
F
∧
x
∈
A
)
∨
F\land x∈A)\lor
F∧x∈A)∨
(
<
x
,
y
>
∈
F
∧
x
∈
B
)
(<x,y>∈F\land x∈B)
(<x,y>∈F∧x∈B)
⇔
\Harr
⇔(<x,y>∈F
↾
\upharpoonright
↾A)
∨
\lor
∨(<x,y>∈F
↾
\upharpoonright
↾B)
⇔
\Harr
⇔(<x,y>∈F
↾
\upharpoonright
↾A∪F
↾
\upharpoonright
↾B
所以有F
↾
\upharpoonright
↾(A∪B)=F
↾
\upharpoonright
↾A∪F
↾
\upharpoonright
↾B
(13)任取y,
y∈F[A∩B]
⇔
\Harr
⇔
∃
x
(
<
x
,
y
>
∈
F
∧
x
∈
A
∩
B
)
\exists x(<x,y>∈F\land x∈A∩B)
∃x(<x,y>∈F∧x∈A∩B)
⇔
\Harr
⇔
∃
x
(
<
x
,
y
>
∈
F
∧
x
∈
A
∧
x
∈
B
)
\exists x(<x,y>∈F\land x∈A\land x∈B)
∃x(<x,y>∈F∧x∈A∧x∈B)
⇔
\Harr
⇔
∃
x
(
(
<
x
,
y
>
∈
F
∧
x
∈
A
)
∧
\exists x((<x,y>∈F\land x∈A)\land
∃x((<x,y>∈F∧x∈A)∧
(
<
x
,
y
>
∈
F
∧
x
∈
B
)
)
(<x,y>∈F\land x∈B))
(<x,y>∈F∧x∈B))
⇔
\Harr
⇔
∃
x
(
(
<
x
,
y
>
∈
F
∧
x
∈
A
)
∧
\exists x((<x,y>∈F\land x∈A)\land
∃x((<x,y>∈F∧x∈A)∧
∃
x
(
<
x
,
y
>
∈
F
∧
x
∈
B
)
)
\exists x(<x,y>∈F\land x∈B))
∃x(<x,y>∈F∧x∈B))
⇔
\Harr
⇔y∈F[A]
∧
\land
∧y∈F[B]
⇔
\Harr
⇔y∈F[A]∩F[B]
所以有F[A∩B]=F[A]∩F[B]
3.3 关系的幂运算
定义:
设R为A上的关系,n为自然数,则R的n次幂定义为:
(1)
R
0
R^0
R0={<x,x>|x∈A}=
I
A
I_A
IA
(2)
R
n
+
1
R^{n+1}
Rn+1=
R
n
∘
R
R^n\circ R
Rn∘R
注意:
对于A上的任何关系
R
1
R_1
R1和
R
2
R_2
R2都有
R
1
0
=
R
2
0
=
I
A
R^0_1=R^0_2=I_A
R10=R20=IA
对于A上的任何关系R都有
R
1
=
R
0
∘
R
=
I
A
∘
R
=
R
R^1=R^0\circ R=I_A\circ R=R
R1=R0∘R=IA∘R=R文章来源:https://www.toymoban.com/news/detail-741175.html
例如,设A={a,b,c,d},R={<a,b>,<b,a>,<b,c>,<c,d>},求R的各次幂,分别用关系矩阵和关系图表示。
解:R的关系矩阵为:
M
=
[
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
]
M= \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix}
M=
0100100001000010
则
R
2
,
R
3
,
R
4
R^2,R^3,R^4
R2,R3,R4的关系矩阵分别是:
M
2
=
[
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
]
[
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
]
=
[
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
]
M^2= \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}
M2=
0100100001000010
0100100001000010
=
1000010010000100
M
3
=
M
2
M
=
[
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
]
[
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
]
=
[
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
]
M^3=M^2M= \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}
M3=M2M=
1000010010000100
0100100001000010
=
0100100001001000
M
4
=
M
3
M
=
[
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
]
[
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
]
=
[
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
]
M^4=M^3M= \begin{bmatrix} 0 & 1 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{bmatrix}
M4=M3M=
0100100001001000
0100100001000010
=
1000010010000100
因此
M
4
=
M
2
M^4=M^2
M4=M2,即
R
4
=
R
2
R^4=R^2
R4=R2,由此可以得到:
R
2
=
R
4
=
R
6
=
⋅
⋅
⋅
⋅
⋅
R2=R4=R6=·····
R2=R4=R6=⋅⋅⋅⋅⋅
R
3
=
R
5
=
R
7
=
⋅
⋅
⋅
⋅
⋅
R3=R5=R7=·····
R3=R5=R7=⋅⋅⋅⋅⋅
而R^0,即IA的关系矩阵是
M
0
=
[
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
]
M^0= \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix}
M0=
1000010000100001
用关系图的方法得到
R
0
,
R
1
,
R
2
,
R
3
R^0,R^1,R^2,R^3
R0,R1,R2,R3等的关系图。
性质:文章来源地址https://www.toymoban.com/news/detail-741175.html
- 设A为n元集,R是A上的关系,则存在自然数s和t,使得 R s = R t R^s=R^t Rs=Rt
- 设R是A上的关系,m,n∈N,则
R m ∘ R n = R m + n R^m\circ R^n=R^{m+n} Rm∘Rn=Rm+n
( R m ) n = R m n (R^m)^n=R^{mn} (Rm)n=Rmn
到了这里,关于离散数学-集合论-关系的概念、表示和运算(7)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!