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

分手后的思念是犯贱 2024-03-30 17:01 151阅读 0赞

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

### 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>\}矩阵是:  
![在这里插入图片描述][f702354b340240feb638a13d4d721cfe.png]  
关系图： 若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的关系矩阵和关系图。  
![在这里插入图片描述][e03c6b1bbb9e4ae4b0e4a5e569a39333.png]

### 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

例如，设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=01001000010000100100100001000010=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=10000100100001000100100001000010=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=01001000010010000100100001000010=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等的关系图。  
![在这里插入图片描述][4e83f736a0fe4b0dba89aabd3515b305.png]  
性质：

*  设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

[f702354b340240feb638a13d4d721cfe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/3c6d4cfb278b40d3b9a1051ec6373af9.png
[e03c6b1bbb9e4ae4b0e4a5e569a39333.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9e48e00bfdea412fb54e1f1eae0d1a09.png
[4e83f736a0fe4b0dba89aabd3515b305.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8bd1021a262d4b6b87363681b4f7ad09.png