当前位置：文档之家 › 离散数学关系的闭包

离散数学关系的闭包

  • 格式：ppt
  • 大小：280.00 KB
  • 文档页数：25

下载文档原格式

  / 25

合集下载

离散数学关系-PPT

离散数学关系-PPT
离散数学关系
基本要求和重难点:
• 基本要求
了解序偶与笛卡尔积,掌握关系得性质和运算,重 点掌握关系闭包运算得求法和偏序关系及哈斯图 得正确画法。
• 重难点
关系5种性质得判断,关系得闭包运算和偏序关系 得性质及特殊元素得判断。
引言
日常生活中,大家熟知一些常见关系, 例:家庭集合,有父子关系、夫妻关系等。 全校同学作为一个集合,有同班关系,同组关系。 在计算机科学中,在计算机逻辑设计中,应用了等 价关系,相容关系。 在编译原理、关系数据库、数据结构、数学中也有 关系。
例题
返回第5、3节目录
五、传递性例题
例: A={1,2,3,4} R={<1,4>,<4,3>,<1,3>,<3,1>,<1,2>,<3,2>,<2,3>, <4,2>,<1,1>,<3,3>} R不就是传递得
返回传递性
返回第5、3节目录
六、举 例
自反性 反自反性 对称性 反对称性 传递性
任何集合上得
返回总目录
一、自反性
自反性
定义: 若xA,均有xRx,那么称R就是自反得。
A上关系R就是自反得x(xA xRx)
在关系矩阵中,反映为主对角线元素均为1 在关系图中,反映为每结点都有自回路 例1: A＝{1,2,3},R={<1,1>,<2,2>,<3,3>,<1,2>}
1 23
例2:“＝”关系和“≤”关系就是自反得吗？
S={<4,2>,<2,5>,<3,1>,<1,3>}

3.3关系上的闭包运算

3.3关系上的闭包运算
1 3 1 3 1 3
2 r(R)s(R)t(R)
4
2
4
2
4
构造自反闭包r(R)的方法
定理3.3―5设R是集合A上的二元关系.那么, r(R)=R∪E(这里E是A上相等关系,在本节中均如此.) 证 设R′=R∪E.显然,R′是自反的且 是自反的 R⊆R′. 余下只需证明R′最小性, 现假设R″是A上的自反关系且R⊆R″. 因R″是自反的,所以E⊆R″, 所以R′=R∪E⊆R″. 这样,定义3.3―2都满足.所以,R′=r(R).证毕
2011-1-10
离散数学
14
例
设集合A={1,2,3,4}，R={<1,2>,<2,2>,<2,3>,<3,4>}是定义在A 上的二元关系。 上的二元关系。 （1）画出R的关系图； 的关系图； （2）求出r(R),s(R),t(R),并画出其相应的关系图。 并画出其相应的关系图。 解（1）R的关系图见下图； 的关系图见下图；
离散数学
4
性质
1. xRy⇔yR-1x 2. 将R的关系图中有向边的方向改变成相反方 有向边的方向改变成相反方 向即得R-1的关系图，反之亦然； 3. 将R的关系矩阵转置即得R-1的关系矩阵， 即R和R-1的关系矩阵互为转置矩阵。 的关系矩阵互为转置矩阵。 4. R-1的前域与后域正好是R的后域和前域， 即domR=ranR-1，domR-1=ranR； 5. (RoS)-1=S-1oR-1。
2011-1-10 离散数学 18
构造对称闭包t(R)的方法
定理3.3―7设R∞ 是集合A上的二元关系,那么 t ( R ) = U R i = R U R 2 U R 3 UL 证明分两部分

离散数学第七章二元关系

离散数学第七章二元关系

19
证明
(2) 任取<x,y>, <x,y>∈(FG)1 <y,x>∈FG t (<y,t>∈F∧<t,x>∈G) t (<x,t>∈G1∧<t,y>∈F1) <x,y>∈G1 F1 所以 (F G)1 = G1 F1
20
关系运算的性质
定理7.3 设R为A上的关系, 则 RIA= IAR=R <x,y> <x,y>∈RIA t (<x,t>∈R∧<t,y>∈IA) t (<x,t>∈R∧t=y∧y∈A) <x,y>∈R
例如 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}>} 类似的还可以定义： 大于等于关系, 小于关系, 大于关系, 真包含关系等.
注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有 穷集） 关系图适合表示有穷集A上的关系
11
实例
例4 A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>}, R的关系矩阵MR和关系图GR如下：
1 1 0 0 0 0 1 1 MR 0 0 0 0 0 1 0 0
10
关系的表示

离散数学-第四章 关系-内容提要

离散数学-第四章 关系-内容提要

{}
传递。
(5)如 果 VJ
:IT{∶ ∶ ∶ ∶ 蚕 ⒈11∶⒈ ∶ Ll ;, 翕 罐 ∶ ∶ ∶ 置 R在 A上
:I∶
:: 1∷
Vj V石
(Π
、 、 y,z)∈ R→ 〈 R∧ 〈 J,z〉 ∈ R),则 称 Π ,y,z∈ A∧ 〈 ,j〉 ∈
1亠
判别法
:
利用关系表达式判别 (1)R在 A上 白反 ㈡rA∈ R。
,
系:简 称全胛 蜮 线序 曳
柙
\宀
:'艹
° Γ ˉ叽
抖 ¨ ‰ 艹 渺 冖妒 ”
^讷
p¨ ¨
¨
i
∶
^¨
Ⅱ… ¨
=艹
)。
`呻
/
‘ :° f耷
一
^A’
工 < ′
工 < ′
Ι ⒕
,
、
\′
I纟
:
轱
/廴
跃
:
h,如 果 J≤ y∨ y※ J,贝 刂 ∈ 称
J与 j可 比。
称 y覆 盖 J。
偏序集中的特殊元素
得 ⒎ 则
:
y,z〉 ∈ S))。 ∈ R∧ 〈
有关基本运算的定理 ・ 定理 4.1 设 F是 任意的关系 ,则
(1)(Fˉ l)ˉ ^l=F。
・
(2)domFˉ ˉ ∴ =ranF,ranF~l=domF。
定理 4.2 设 F,G,Ⅳ 是任意的关系 ,则 (1)(F° G)° H=Fo(G° H), (2)(FoG)ˉ l=G^loF_ˉ
:
(2)R在 (3)R在 (4)R在 (5)R在 (1)R在 (2)R在 (3)R在 (4)R在
A上 反 自反 ⑶R∩ rA=¤ 。 A上 对称 山R=Rl。 ; A上 反对称 ㈡R∩ R~l∈ A上 传递 ㈡R。 R∈ R。

离散数学关系的运算

离散数学关系的运算
例2.37 求集合A={1,2,3}上的关系R = {<1,1>, <1,2>, <2,1>, <1,3>}的自反闭包。
关系的对称闭包
定义2.18 设R和R是集合A上的关系，如果满足： （1）R是对称的； （2）R R； （3）对A上任何包含R的自反关系R都有RR。
则将R称为R的对称闭包，记作s(R)。
逆运算的性质
定理2.5 对于任意集合A和B，设R是集合A到B的关系，则有： (R-1)-1 = R。
逆运算的性质
定理2.6 对于任意集合A、B和C， 设R和S分别是集合A到B和集合B到C的关系，那么 (R◦S)-1 = S-1◦R-1。
逆运算的性质
定理2.7 对于任意集合A、B和C， 设R和S分别是集合A到B和集合B到C的关系，那么：
①计算R-1、S-1、(R-1)-1、(S-1)-1、(R◦S) -1和S-1◦R-1；
解 ① 根据逆运算和复合运算的定义，有 R-1 = {<a, 1>, <c, 2>, <b, 3>, <b, 4>, <d, 4>} S-1 = {<2, a>, <4, b>, <3, c>, <5, c>, <5, d>} (R-1)-1 = {<1, a>, <2, c>, <3, b>, <4, b>, <4, d>} (S-1)-1 = {<a, 2>, <b, 4>, <c, 3>, <c, 5>, <d, 5>} R◦S = {<1, 2>, <2, 3>, <2, 5>, <3, 4>, <4, 4>, <4, 5>} (R◦S) -1= {<2, 1>, <3, 2>, <5, 2>, <4, 3>, <4, 4>, <5, 4>} S-1◦R-1 = {<2, 1>, <3, 2>, <5, 2>, <4, 3>, <4, 4>, <5, 4>}

离散数学第4章-二元关系

离散数学第4章-二元关系

4.6 等价关系与划分
• 三 性质 • 定理4.13 设R是A上的等价关系，则 （1）对任一a∈A，有a∈[a]； （2）对a, b∈A，如果aRb，则[a]=[b]; （3）对a, b∈A，如果(a, b)∉R，则[a]∩[b]=∅; （4）∪a∈A[a]=A。
4.6 等价关系与划分
• 定理4.14 集合A上的任一划分可以确定A上 的一个等价关系R。 • 定理4.15 设R1和R2是A上的等价关系， R1=R2⇔ A/R1=A/R2 。 • 定理4.16 设R1和R2是A上的等价关系，则 R1∩R2是A上的等价关系。
4 .3 关系的运算
• 一 逆运算 • 定义4.7（逆关系） 设R是从A到B的二元关系， 则从B到A的二元关系记为R-1，定义为R-1 ={(b,a)|(a,b)∈R}，称为R的逆关系。 • 定理2.1 （1）(R-1)-1=R; （2）(R1∪R2)-1= R1-1∪ R2-1; （3）(R1∩R2)-1= R1-1 ∩R2-1; （4） (A×B)-1= B×A；
4 .5 关系的闭包
•
• (1) (2) (3) • (1) (2) (3)
二 基本性质
定理4.5 设R是A上的二元关系，则 R是自反的 ⇔ r( R )=R； R是对称的 ⇔ s( R )=R； R是传递的 ⇔ t( R )=R； 定理4.6 设R1和R2是A上的二元关系，若R1⊆R2则 r(R1)⊆ r(R2)； s(R1)⊆ s(R2)； t(R1)⊆ t(R2)。
第四章 关系
4.1 二元关系 4.2 关系的性质 4 .3 关系的运算 4 .5 关系的闭包 4.6 等价关系与划分
4.1 二元关系
• 一 定义4.1（二元关系）
设A和B是任意两个集合，A×B的子集R称为从A到 B的二元关系。当A=B时，称R为A上的二元关系。若 (a, b)∈R，则称a与b有关系R，记为aRb。 (a, b)∉R：a与b没有关系R R=∅：空关系 R=A×B：全关系

离散数学知识点

离散数学知识点摘要：离散数学是计算机科学和数学的一个分支，它专注于非连续结构的研究。

本文旨在概述离散数学的核心知识点，包括集合论、逻辑、关系、函数、图论、组合数学和递归等。

1. 集合论- 集合的基本概念：集合是离散数学的基础，它是一组明确的、无重复的对象的集合。

- 集合运算：包括并集、交集、差集、补集等。

- 幂集：一个集合所有子集的集合。

- 笛卡尔积：两个集合所有可能的有序对的集合。

2. 逻辑- 命题逻辑：研究命题（声明的真值）和它们之间的关系，如合取、析取、否定等。

- 谓词逻辑：使用量词（如全称量词和存在量词）来表达更复杂的逻辑关系。

- 逻辑推理：包括直接证明、间接证明和归谬法等。

3. 关系- 关系的定义：一个集合到另一个集合的有序对的集合。

- 关系的类型：自反性、对称性和传递性等。

- 关系的闭包：在给定关系下，集合的最小闭包。

4. 函数- 函数的定义：一个集合到另一个集合的映射，每个元素有唯一的像。

- 函数的类型：单射、满射和双射。

- 复合函数：两个函数可以组合成一个新的函数。

5. 图论- 图的基本概念：由顶点（节点）和边组成的结构。

- 图的类型：无向图、有向图、连通图、树等。

- 图的算法：如最短路径、最小生成树、图的着色等。

6. 组合数学- 排列和组合：从n个不同元素中取出r个元素的不同排列和组合的数量。

- 二项式定理：描述了二项式的幂展开的系数。

- 生成函数：一种编码序列的方法，用于解决复杂的计数问题。

7. 递归- 递归定义：一个对象通过引用比自己更小的版本来定义。

- 递归函数：在计算机程序中，一个函数调用自身来解决问题。

结论：离散数学为理解和设计计算机系统提供了基础工具和理论。

它的知识点广泛应用于算法设计、数据结构、编程语言理论和数据库等领域。

掌握离散数学对于任何希望在计算机科学领域取得进展的人来说都是至关重要的。

本文提供了一个简洁的离散数学知识点概述，每个部分都直接针对一个主题，避免了不必要的背景信息和解释。

离散数学 ch2.二元关系(3,4节)


下边R3、R4、 R6 、 R8均是对称关系。
1
。

1
。
2
。 。 3
R1
1
。 。 3
R2
1
。 。 2。 。 3 3
R3
1
R4
1
。
2
。
2
。
。
2
。 。 3
R5
。 。 3
R6
。 。 2。 。 3 3
R7 R8
四.反对称性
定义:设R为集合X中关系,若对任何x, y∈X,如果有 （x,y)∈ R,和(y ,x)∈ R,就有x=y,则称R为A中反对称关系 。 如实数的小于关系<，≤ ，均是反对称的。父子关系是反 对称的。
R 3 {(1,2), (3,0), (3,2)}
性质 判定 自反性
从关系的有向图 每个结点都有环
从关系的矩阵 主对角线全是1
反自反性
对称性 反对称性
每个结点都无环
主对角线全是0
不同结点间如果有边, 是以对角线为对称 则有方向相反的两条 的矩阵 边. 不同结点间,最多有一 以主对角线为对称 条边. 的位置不会同时为1
实际上r(R)、(s(R) 、t(R)) 就是包含R的“最小” 的自反(对称、传递)关系。 三.计算方法 定理1.给定 A中关系R,则 r(R)=R∪IA。 证明：令R’=R∪IA,显然R’是自反的和RR’，下 面证明R’是“最小的”：如果有A上自反关系 R”且RR”,又IAR”,所以 R∪IAR”,即R’R”。 所以R’就是R的自反闭包。即r(R)=R∪IA 。 ~ R 定理2.给定 A中关系R,则 s(R)=R∪ 。 证明方法与1.类似。（集合法） 定理3.给定 A中关系R,则 t(R)=R∪R2∪R3∪... 。 证明：令R’= R∪R2∪R3∪..., ⑴显然有 RR’ ；

离散数学各章要点7

主要内容1.有序对与笛卡儿积2.二元关系（包括空关系, 恒等关系, 全域关系等）及其表示（关系矩阵, 关系图）3.关系的五种性质（自反性, 反自反性, 对称性, 反对称性, 传递性）4.二元关系的运算（定义域、值域、域、逆、合成、限制、像、幂）5.关系的三种闭包（自反闭包, 对称闭包, 传递闭包）6.等价关系和划分（包括等价类, 商集, 划分块等）7.偏序关系（包括哈斯图, 最大元, 最小元, 极大元, 极小元, 上界, 下界, 最小上界, 最大下界等）学习要求1.掌握：有序对及卡氏积的概念及卡氏积的性质2.掌握：二元关系, A到B的二元关系, A上的二元关系, 关系的定义域和值域, 关系的逆, 关系的合成, 关系在集合上的限制, 集合在关系下的象等概念, 掌握关系的定义域、值域、逆、合成、限制、像等的主要性质3.掌握：关系矩阵与关系图的概念及求法4.掌握：集合A上的二元关系的主要性质（自反性, 反自反性, 对称性, 反对称性, 传递性）的定义及判别法, 对某些关系证明它们有或没有其中的性质5.掌握：A上二元关系的n次幂的定义及主要性质6.掌握A上二元关系的自反闭包、对称闭包、传递闭包的定义及求法7.掌握：等价关系、等价类、商集、划分等概念, 以及等价关系与划分之间的对应8.掌握：偏序关系、偏序集、哈斯图、最大元、最小元、极大元、极小元、上界、下界、上确界、下确界等概念典型习题1.下列等式中哪些成立？哪些不成立？为什么？2.设A={1,2,3}, R={<x,y>|x,y∈A且x+3y<8}, S={<2,3>,<4,2>}, 求下列各式：3.说明下列关系是否是自反的、对称的、传递的或反对称的.4.设R是二元关系, 设S={<a,b>|存在某个c, 使得<a,c>∈R且<c,b>∈R}. 证明如果R是等价关系, 则S也是等价关系.5.设R是Z上的模n等价关系, 即x～y当且仅当x≡y(mod n), 试给出由R确定的Z的划分π.6.设A={2,3,4,5,6,7,8,9,10,12,20}, R为整除关系, 求下列各题：。

离散数学及其应用重要名词中英对应以及重要概念解释与举例

离散数学及其应用重要名词中英对应以及重要概念解释与举例1 The Foundations: Logic and Proofs（逻辑与证明）1.1 Propositional Logic（命题逻辑）Propositions（命题）——declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。

Truth Table（真值表）Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if）Translating English Sentences1.2 Propositional Equivalences（命题等价）Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式）Logical Equivalences（逻辑等价）——Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，p<->q是重言式）Logical Equivalences——Page24Disjunctive normal form(DNF，析取范式)Conjunctive normal form(CNF，合取范式) 见Page27～291.3 Predicates and Quantifiers（谓词和量词）Predicates——谓词，说明关系、特征的修饰词Quantifiers——量词Ø Universal Quantifier(全称量词) "全部满足Ø Existential Quantifier(存在量词) $至少有一个Binding Variables(变量绑定，量词作用域与重名的问题)Logical Equivalence Involving QuantifiersNegating Quantified Expressions(量词否定表达：否定全称=存在否定，否定存在=全程否定) Translating from English into Logical Expressions(自然语句转化为逻辑表达)Using Quantifiers in System SpecificationsExamples from Lewis Carrol——全称量词与条件式(p->q)搭配，存在量词与合取式搭配。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例 15
例15 设A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>, <d,b>}，则R和r(R)，s(R)，t(R)的关系图如下图所示。其 中r(R)，s(R)，t(R)的关系图就是使用上述方法直接从R的 关系图得到的。
c
a
b
d
c
a
b
d
c
a
b
d
c
a
b
d
Warshall 算法
③设R″是包含R的对称关系， 任取<x,y>，有 <x,y>∈R∪R-1 <x,y>∈R∨<x,y>∈R-1 <x,y>∈R∨<y,x>∈R <x,y>∈R″∨<y,x>∈R″ <x,y>∈R″∨<x,y>∈R″ <x,y>∈R″ 所以 R∪R-1 R″.
定理10 (3)的证明
（3）t(R)＝R∪R2∪R3∪… 证明 先证R∪R2∪… t(R)成立，为此只需证对任意的正整数n有 Rn
定理10 (3)的证明
（3）t(R)＝R∪R2∪R3∪… 证明 要证t(R)R∪R2∪…成立,只须证明R∪R2∪…是传递的。
任取<x,y>,<y,z>，则 <x,y>∈R∪R2∪… ∧ <y,z>∈R∪R2∪…
t(<x,y>∈Rt) ∧ s(<y,z>∈Rs) ts(<x,y>∈Rt ∧ <y,z>∈Rs) ts(<x,z>∈Rt Rs) ts(<x,z>∈Rt+s) <x,z>∈R∪R2∪… 从而证明了R∪R2∪…是传递的。
§1.4 关系的闭包运算
闭包（closure）的定义 闭包的构造方法 闭包的性质 闭包的相互关系
闭包的定义
定义14 R是非空集合A上的关系,R的自反（对称或传递）闭 包是A上的关系R′，使得 R′满足以下条件： （1）R′是自反的（对称的或传递的） （2）RR′ （3）对A上任何包含R的自反（对称或传递）关系R″有 R′ R″. 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递 闭包记作t(R).
定理10 (2)的证明
证明 （2）s(R)＝R∪R-1 .
① RR∪R-1. ②证明R∪R-1是对称的，
任取<x,y>，有 <x,y>∈R∪R-1
<x,y>∈R∨<x,y>∈R-1 <y,x>∈R-1∨<y,x>∈R <y,x>∈R∪R-1 所以 R∪R-1 是对称的。
定理10 (2)的证明
闭包的构造方法
定理10 设R为A上的关系，则有 （1）r(R)＝R∪R0 （2）s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪…
证明思路 (1)和(2)：证明右边的集合满足闭包定义的三个条件。
(3)采用集合相等的证明方法。 证明左边包含右边，即t(R)包含每个Rn . 证明右边包含左边，即R∪R2∪…具有传递的性质。
输入：M（R的关系矩阵）
输出：MT（t(R)的关系矩阵） 1.MT←M 2.for k ← 1 to n do
3. for i ← 1 to n do
4.
for j ← 1 to n do
5.
MT[i,j]←MT[i,j]+MT[i,k]*MT[k,j]
注意：算法中矩阵加法和乘法中元素相加都使用逻辑加。
推论
推论 设R为有穷集A上的关系，则存在正整数r使得 t(R)=R∪R2∪…∪Rr .
证明 由定理7.6和7.10(3)得证。 例题 求整数集合Z上的关系R＝{<a,b> | a<b}的自反闭包
和对称闭包。 解答 r(R)＝R∪R0＝{<a,b>|a<b}∪{<a,b>|a＝b}
＝{<a,b>|a≤b} s(R)＝R∪R-1＝{<a,b>|a<b}∪{<b,a>|a<b}
Warshall 算法 举例
例 设A={a,b,c,d}，R={<a,b>,<b,a>,<b,c>,<c,d>,<d,b>}，
求t(R).
0 1 0 0
M0

1 0
0 0
1 0
0 1
0 1 0 0
0 1 0 0
M1

1 0
1 0
1 0
0 1
0 1 0 0
＝{<a,b>|a≠b}
通过关系矩阵求闭包的方法
设关系R，r(R)，s(R)，t(R)的关系矩阵分别为M，Mr，Ms 和Mt，则
Mr ＝ M＋E
对角线上的值都改为1
Ms ＝ M＋M′
若aij＝1，则令aji＝1
Mt ＝ M＋M2＋M3＋…
沃舍尔算法
其中E是和M同阶的单位矩阵，M′是M的转置矩阵。
注意在上述等式中矩阵的元素相加时使用逻辑加。
Warshall 算法 举例
牡丹江师范学院本科生课程
1.4 关系的闭包运算
理学院 季丹丹
问题
波士顿 芝加哥
圣地亚哥
丹佛
Байду номын сангаас
纽约 底特律 如果存在一条从数据中心a到b的电话线，<a,b>就属于关 系R.
如何确定从一个中心是否有一条电话线(可能不直接)链 接到另一个中心？
通过构造包含R的最小的传递关系来找出每一对有着联系 的数据中心，这个关系叫做R的传递闭包。
定理10 (1)的证明
（1）r(R)＝R∪R0 .
证明 ①由IA＝R0 R∪R0，可知R∪R0是自反的， ②R R∪R0 . ③设R″是A上包含R的自反关系，则有RR″和IAR″. 任取<x,y>，必有 <x,y>∈R∪R0 <x,y>∈R∪IA <x,y>∈R″∪R″＝R″ 所以 R∪R0 R″. 综上所述，r(R)＝R∪R0.
分析 k＝1 时，MT[i,j]←MT[i,j]+MT[i,1]*MT[1,j]
MT[1,j]←MT[1,j]+MT[1,1]*MT[1,j]
MT[2,j]←MT[2,j]+MT[2,1]*MT[1,j] 将第1行加到第2行上
MT[3,j]←MT[3,j]+MT[3,1]*MT[1,j]
MT[4,j]←MT[4,j]+MT[4,1]*MT[1,j]得到M1.
t(R).用归纳法。 n＝1时，有 R1＝R t(R). 假设Rnt(R)成立，那么对任意的<x,y>有
<x,y>∈Rn+1＝Rn R t(<x,t>∈Rn∧<t,y>∈R) t(<x,t>∈t(R)∧<t,y>∈t(R)) <x,y>∈t(R) （因为t(R)是传递的） 这就证明了Rn+1 t(R). 由归纳法命题得证。