关系的闭包.ppt

* * * * * * * * * * * * * * * * * * DSPST DSPST research 宁波大学数字技术与软件应用研究所 * DSPST DSPST research 宁波大学数字技术与软件应用研究所 * * 5.1 Relations and Their Properties 5.2 n-ary Relations and Their Application 5.3 Representing Relations 5.4 Closures of Relations 关系的闭包 5.5 Equivalence Relations 5.6 Partial Orderings Chapter 5 Relations * * 5.4 Closures of Relations 闭包关系 Reflexive Closure 自反闭包 Symmetric Closure 对称闭包 Transitive Closure 传递闭包 【Definition】The closure of a relation R with respect to property P is the relation S with property P containing R such that S is a subset of every relation with property P containing R. R关于性质P的闭包是包含R的具有性质P的关系S ，并且S是每个包含R的具有性质P的关系的子集。 The smallest relation with property P containing R * * 5.4 Closures of Relations Reflexive Closure自反闭包 【 Theorem 】 Let R be a relation on A. The reflexive closure of R, denoted by r(R), is Proof: The diagonal relation（对角关系） on A ? containing R 包含R ? is a reflexive relation 是自反关系 ? is the smallest reflexive relation which contains R Suppose that R’ is a reflexive relation containing R, then * * 5.4 Closures of Relations 【 Corollary 】 ? R is a reflexive relation R是自反关系. Proof: ? The reflexive closure is a reflexive relation 自反闭包是自反关系 ? Since R is a reflexive relation, * * 5.4 Closures of Relations Question: Given R, how to obtain its reflexive closure? 给定关系R，怎样获得自反闭包？ Add to R all ordered pairs of the form (a,a) with a?A, not already in R 在关系R中添加未在R中的形如(a,a) 的有序偶，a?A Add loops to all vertices on the digraph representation of R.在表示关系R的图中的每个顶点加上环路 Put 1’s on the diagonal of the connection matrix of R.将1添加到关系矩阵中的 主对角线上 * * 5.4 Closures of Relations 〖Example 1〗 , What is r(R)? Solution: * * 5.4 Closures of Relations Symmetric