离散数学-集合论-关系的概念、表示和运算(7)

这篇具有很好参考价值的文章主要介绍了离散数学-集合论-关系的概念、表示和运算(7)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

离散数学-关系的概念、表示和运算

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} 2m2n=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=domRranR
R − 1 R^{-1} R1={ < x , y > ∣ < x , y > ∈ R <x,y>|<x,y>∈R <x,y><x,y>∈R}
R ∘ S R\circ S RS={ < 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} R1={<2,1>,< 3,1>,<4,2>,< 3,4>}     有序对的第一个值和第二个值颠倒
设S={<2,5>,< 3,4>}
R ∘ S R\circ S RS={<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} F1)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 domF1=ranF,ranF1=domF
证:(1)任取<x,y>,由逆的定义有:
<x,y>∈ ( F − 1 ) − 1 (F^{-1})^{-1} (F1)1 ⇔ \Harr <y,x>∈ F − 1 F^{-1} F1 ⇔ \Harr <x,y>∈ F F F
所以有( F − 1 ) − 1 F^{-1})^{-1} F1)1= F F F
(2)任取 x x x
x x x d o m F − 1 domF^{-1} domF1 ⇔ \Harr ∃ \exists y(<x,y>∈ F − 1 F^{-1} F1) ⇔ \Harr ∃ \exists y(<y,x>∈ F F F) ⇔ \Harr x ∈ r a n F x∈ranF xranF
所以有 r a n F − 1 = d o m F ranF^{-1}=domF ranF1=domF

⧫ \blacklozenge F , G , H F,G,H F,G,H是任意的关系,则:
(3) ( F ∘ G ) ∘ H (F\circ G)\circ H (FG)H= F ∘ ( G ∘ H ) F\circ (G\circ H) F(GH)
(4) ( F ∘ G ) − 1 (F\circ G)^{-1} (FG)1= G − 1 ∘ F − 1 G^{-1}\circ F^{-1} G1F1
证:(3)任取<x,y>,
    <x,y>∈ ( F ∘ G ) ∘ H (F\circ G)\circ H (FG)H
⇔ \Harr ∃ t ( < x , t > ∈ F ∘ G ∧ < t , y > ∈ H ) \exists t(<x,t>∈F\circ G\land<t,y>∈H) t(<x,t>∈FG<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) ts(<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>∈Ft(<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>∈GH)
⇔ \Harr <x,y>∈ F ∘ ( G ∘ H ) F\circ (G\circ H) F(GH)
所以 ( F ∘ G ) ∘ H (F\circ G)\circ H (FG)H= F ∘ ( G ∘ H ) F\circ (G\circ H) F(GH)
(4)任取<x,y>,
    <x,y>∈ ( F ∘ G ) − 1 (F\circ G)^{-1} (FG)1
⇔ \Harr <y,x>∈ ( F ∘ G ) (F\circ G) (FG)
⇔ \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>∈G1<t,y>∈F1)
⇔ \Harr <x,y>∈ G − 1 ∘ F − 1 G^{-1}\circ F^{-1} G1F1
所以: ( F ∘ G ) − 1 (F\circ G)^{-1} (FG)1= G − 1 ∘ F − 1 G^{-1}\circ F^{-1} G1F1

⧫ \blacklozenge 设R为A上的关系则:
(5) R ∘ I A R\circ I_A RIA= I A ∘ R I_A\circ R IAR= R R R
证: 任取<x,y>
    <x,y>∈ R ∘ I A R\circ I_A RIA
⇔ \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>∈Rt=yyA)
⇔ \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(GH)=FGFH
(7) ( G ∪ H ) ∘ F = G ∘ F ∪ H ∘ F (G∪H)\circ F=G\circ F∪H\circ F (GH)F=GFHF
(8) F ∘ ( G ∩ H ) ⊆ F ∘ G ∩ F ∘ H F\circ (G∩H)\sube F\circ G∩F\circ H F(GH)FGFH
(9) ( G ∩ H ) ∘ F ⊆ G ∘ F ∩ H ∘ F (G∩H)\circ F \sube G\circ F∩H\circ F (GH)FGFHF
证: (8)任取<x,y>,
    <x,y>∈ F ∘ ( G ∩ H ) F\circ (G∩H) F(GH)
⇔ \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>∈GH)
⇔ \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 FG<x,y>∈FH
⇔ \Harr <x,y>∈ F ∘ G ∩ F ∘ H F\circ G∩F\circ H FGFH
所以有 F ∘ ( G ∩ H ) ⊆ F ∘ G ∩ F ∘ H F\circ (G∩H)\sube F\circ G∩F\circ H F(GH)FGFH

⧫ \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 FxAB
⇔ \Harr <x,y>∈ F ∧ ( x ∈ A ∨ x ∈ B ) F\land (x∈A\lor x∈B) F(xAxB)
⇔ \Harr (<x,y>∈ F ∧ x ∈ A ) ∨ F\land x∈A)\lor FxA) ( < x , y > ∈ F ∧ x ∈ B ) (<x,y>∈F\land x∈B) (<x,y>∈FxB)
⇔ \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>∈FxAB)
⇔ \Harr ∃ x ( < x , y > ∈ F ∧ x ∈ A ∧ x ∈ B ) \exists x(<x,y>∈F\land x∈A\land x∈B) x(<x,y>∈FxAxB)
⇔ \Harr ∃ x ( ( < x , y > ∈ F ∧ x ∈ A ) ∧ \exists x((<x,y>∈F\land x∈A)\land x((<x,y>∈FxA) ( < x , y > ∈ F ∧ x ∈ B ) ) (<x,y>∈F\land x∈B)) (<x,y>∈FxB))
⇔ \Harr ∃ x ( ( < x , y > ∈ F ∧ x ∈ A ) ∧ \exists x((<x,y>∈F\land x∈A)\land x((<x,y>∈FxA) ∃ x ( < x , y > ∈ F ∧ x ∈ B ) ) \exists x(<x,y>∈F\land x∈B)) x(<x,y>∈FxB))
⇔ \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 RnR
注意:
对于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=R0R=IAR=R

例如,设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} RmRn=Rm+n
    ( R m ) n = R m n (R^m)^n=R^{mn} (Rm)n=Rmn

到了这里,关于离散数学-集合论-关系的概念、表示和运算(7)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 离散数学(十二):关系的幂运算与关系的性质

    1)幂运算的定义  2)幂运算的求法   幂运算有两种求法,基于矩阵的方法和基于关系图的方法。我们之前学过关系的表示方法有三种:集合、矩阵、关系图。那么同样,这些方式也可以运用于关系的计算中。 需要的注意的是,基于关系图的运算是具有物理意义的,以R2为例

    2024年02月08日
    浏览(44)
  • 【Java实现】离散数学计算 关系的幂运算

    (前排提示,代码内容在文章中间,末尾是闲聊)  离散数学在在“右复合”的基础上提出了“幂运算”的概念。 设R为A上的关系,n为自然数,则R的n次幂如下: (1)为恒等关系。 (2) =o。  咳咳,用上面两个定义可以干很多事情,比如我们知道任意集合上关系的0次幂都

    2024年02月11日
    浏览(38)
  • 离散数学·图的矩阵表示、平面图

    无环 , 有向 (可以表示平行边) M(D)【direction】 每一列的和都是0,每一行中所有元素的绝对值是点的度数 所有列相加一定是0(每一列都是0) 第i行第j列是1的情况的和是出度数 同1 平行边的表示就是再加一条一样的列 无向 , 无环 M( G ) 看一下(3)吧🎱🎱🎱 简而言之—

    2024年02月01日
    浏览(43)
  • 【离散数学】九章:关系 - 关系及其性质

    设A和B是集合,一个从 A 到 B 的二元关系是A×B的子集。 (序偶集合的子集) 🐳换句话说,一个从A到B的二元关系是集合R,其中每个有序对的第一个元素取自A而第二个元素取自B。 我们使用记号 aRb表示(a, b)∈R,a R b表示(a, b)∉R。当(a, b)属于R时,称 a与b有关系R 。 📘例:设

    2024年02月04日
    浏览(45)
  • 离散数学_九章:关系(5)

    定义1: 定义在集合 A 上的关系叫做等价关系,如果它们是 自反的、对称的和传递的。 定义2: 如果两个元素 a 和 b 由于等价关系而相关联,则称它们是等价的。记法 a~b 通常用来表示对于某个特定的等价关系来说,a 和 b 是等价的元素。 设 m 是大于 1 的整数。证明以下关系

    2024年02月02日
    浏览(354)
  • 离散数学_九章:关系(1)

    设A和B是集合,一个从 A 到 B 的二元关系是A×B的子集。 (序偶集合的子集) 🐳换句话说,一个从A到B的二元关系是集合R,其中每个有序对的第一个元素取自A而第二个元素取自B。 我们使用记号 aRb表示(a, b)∈R,a R b表示(a, b)∉R。当(a, b)属于R时,称 a与b有关系R 。 📘例:设

    2024年02月08日
    浏览(49)
  • 离散数学_九章:关系(2)

    n元关系:两个以上集合的元素间的关系 设A 1 ,A 2 ,……,A n 是集合。定义在这些集合上的n元关系是A1×A2×……×An 的子集。这些集合A 1 ,A 2 ,……,A n 称为关系的域,n称为关系的阶。 📘例1:设R是N × N × N上的三元组(a, b, c)构成的关系,是个3阶关系,其中a, b, c是满

    2023年04月19日
    浏览(37)
  • 离散数学_九章:关系(3)

    本节及本章的剩余部分研究的所有关系均为二元关系,因此,在这些内容中出现的“关系〞一词都表示二元关系 关系是序偶的集合,所以描述集合能用的方法一般都可以描述关系,比如枚举满足关系的所有序偶,比如叙述满足关系的性质。 前面的例子都是用集合表示关系,

    2024年02月02日
    浏览(38)
  • 【Educoder离散数学实训】关系基础

    题有点多,能聊的不多。有些题还是比较有价值的 就单独说几个题,代码放在最后。所有函数都改成自己写的了,没准比答案给的好读一点? T1 求给定集合的对角线关系(diagonal relation) 我觉得如果卡住的话,第一关会是一个大坎。 因为我们并不知道他到底在说啥,于是我

    2024年02月07日
    浏览(52)
  • 离散数学 --- 特殊关系 --- 偏序关系,哈斯图和特殊元素以及其它次序关系

    1.当我们用 ≤ 符号来表示偏序关系的时候,这个符号就不再局限于它本来的含义了,此时的它表示的是元素之间的先后顺序,如下图:   1.这里的可比的意思是可比较元素在偏序关系中的先后顺序   1.哈斯图其实就是简化版的偏序关系的关系图 2.什么叫做由于传递关系必须出

    2024年01月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包