《第三章 二元关系》由会员分享，可在线阅读，更多相关《第三章 二元关系（8页珍藏版）》请在金锄头文库上搜索。
1、第三章 二元关系 教学重点：关系的概念及表示方法 ；关系的性质；关系的运算，关系的复合,求逆关系, 关 系的闭包。教学难点：等价关系，等价类 教学要求：1.熟练掌握关系的概念及相应的关系图、序偶、矩阵表示方法 ；关系的性质及 其证明；熟练求解关系的复合，求逆关系，关系的闭包，掌握warshell算法。2. 掌握覆盖、划分、等价关系、等价类定义使用，相关定理的证明。3-1 序偶与集合的笛卡尔积一. 序偶与有序n元组定义：由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记你x,y；称X、 y分别为序偶x,y的第一，第二元素。二. 集合的笛卡尔积1定义:设A、B是集合，由A的元素为第一元素，
2、B的元素为第二元素组成序偶的集合, 称为A和B的笛卡尔积，记作AXB，即AxB=|xeAAyeB例 1 设 A=O,1, B=a,b，求 AxB， BxA， AxA。2. 性质3. 应用1)令A1=x|x是学号A2=x|x是姓名A3=男，女A4=x|x 是出生日期A5=x|x 是班级A6 =x|x 是籍贯则 A1xA2xA3 xA4xA5 xA6 中一个元素：001，王强，男， 1981:02:16，计2001-1，辽宁这就是学生档案数据库的一条信息，所以学生的档案就是A1xA2xA3 xA4xA5 xA6的一个子 集。3-2 关系及其表示法一. 例子二. 基本概念1. 关系的定义定义1:设A
3、、B是集合，如果RcAXB，则称R是一个从A到B的二元关系。如果RcA XA，则称R是A上的二元关系。二元关系简称为关系。定义2:任何序偶的集合，都称之为一个二元关系。如:R=1,a,书，车,人，树2. 关系的定义域与值域定义域(domain):设RcAXB，由所有x,ywR的第一个元素组成的集合，称为R的定 义域，记作dom R,即dom R=x|3y(eR)值域(range):设RcAXB，由所有x,ywR的第二个元素组成的集合，称为R的值域,三. 关系的表示方法1. 枚举法:即将关系中所有序偶一一列举出，写在大括号内。如前的 R2=1,1，1,2，1,3，1,4，2,2，2,3，2,4，
4、3,3，3,4，4,4。2. 谓词公式法： 即用谓词公式表示序偶的第一元素与第二元素间的关系。例如 R=x,y|xy3. 有向图法：RcAXB,用两组小圆圈(称为 结点)分别表示A和B的元素，当x,ywR时，从x到y 引一条有向弧(边)。这样得到的图形称为R的关系图。4.矩阵表示法： 有限集合之间的关系也可以用矩阵来表示，这种表示法便于用计算机来处理关系。设 A二al, a2,，am, B=bl, b2,bn是个有限集，RcAXB,定义 R 的 mXn阶矩阵四. 三个特殊关系1. 空关系：2. 完全关系(全域关系)3. A上的恒等关系IA：IAcAXA,且IA =x,x|xUA称之为A上的恒等
5、关系。3-3 关系的性质关系的性质主要有：自反性、反自反性、对称性、反对称性和传递性。一. 自反性定义:设R是集合A中的关系，如果对于任意xUA都有x,xUR (xRx),则称R是A 中自反关系。即R是A中自反的oVx(xgAtxRx)例如在实数集合中，y”是自反关系，因为，对任意实数x,有x x.二. 反自反性定义：设R是集合A中的关系，如果对于任意的xUA都有x,x笑R，则称R为A中的 反自反关系。即R是A中反自反的oVx(xgAtx,x笑R)。从关系有向图看反自反性:每个结点都无环。从关系矩阵看反自反性：主对角线都为0。 如实数的大于关系，父子关系是反自反的。三. 对称性定义:R是集合A
6、中关系，若对任何x, yUA,如果有xRy,必有yRx,则称R为A中的对称 关系。R 是 A 上对称的 oVxVy(xeAygAxRy) TyRx) 从关系有向图看对称性:在两个不同的结点之间，若有边的话，则有方向相反的两条边 从关系矩阵看对称性：以主对角线为对称的矩阵。邻居关系是对称关系，朋友关系是对称关系。四. 反对称性定义:设R为集合A中关系，若对任何x, yUA,如果有xRy,和yRx,就有x=y,则称R为A 中反对称关系 。 R 是 A 上反对称的 oVxVy(xeAAyeAAxRyAyRx) tx二y) oVxVy(xeAAy eAAxyAxRy) yx) (P112)由R的关系图
7、看反对称性：两个不同的结点之间最多有一条边。 从关系矩阵看反对称性：以主对角线为对称的两个元素中最多有一个1。另外对称与反对称不是完全对立的，有些关系它既是对称也是反对称的，如空关系和恒 等关系。五. 传递性定义:R是A中关系，对任何x,y,zUA,如果有xRy,和yRz,就有xRz,则称R为A中传递 关系。即 R 在 A 上传递 oVxVyVz(xGAAywAAZGAAxRyAyRz)TxRz)实数集中的W、V,集合匸、 u是传递的。从关系关系图和关系矩阵中不易看清是否有传递性。有时,必须直接根据传递的定义来 检查。检查时要特别注意使得传递定义表达式的前件为F的时候此表达式为T,即是传递的。
8、即 若x,yUR与y,zUR有一个是F时(即定义的前件为假),R是传递的。3-4 关系的复合1定义:设是R从X到Y的关系，S是从Y到Z的关系，则R和S的复合关系记作RoS。 定义为：RoS =|xGXAzeZ3Ay(yGY AeRAeS)显然，RoS 是从 X 到 Z 的关系。2.复合关系的计算方法(俗称过河拆桥法)A=1,2,3B=1,2,3.4C=1,2,3,4,5RcA X B ScB X C枚举法 R=1,2,2,3,2,4,3,1 S=1,2,2,1,2,3,3,4,4,2,4,5 则RoS=1,1,1,3,2,4,2,2,2,5,3,2有向图法关系矩阵法3-5 逆关系逆关系(反关系
9、)也是我们经常遇到的概念，例如W与三就是互为逆关系。一. 定义R是从A到B的关系，如果将R中的所有序偶的两个元素的位置互换，得到一个从B到 A的关系，称之为R的逆关系，记作Rj或RT。RC二y,x|x,ywRy,xURC ox,ywR、 I A-A- _ 、亠二. 计算方法1. R=1,2,2,3,3,4,4,5Rc =2,1,3,2,4,3,5,42. RC的有向图：是将R的有向图的所有边的方向颠倒一下即可。3. Rc的矩阵M =(M)t 即为R矩阵的转置。如R三. 性质令 R、 S 都是从 X 到 Y 的关系，则1. (RC)C = R2. (RUS)c = RcUSc。3. (RHS)c
10、 = RcGSc。4. (RS)C = RCSC 。证明 1.：任取y,xw (RUS)c,贝ly,xw (RUS)cox,ywRUS ox,ywRVx, ywS Oy,XGRcVy,xGScOy,xG RcUSc所以 (RUS)c = RcUSc，其它类似可证。5. RcS o Rec Sc。证明：充分性，已知RCc SC，则任取x,yURoy, xwRCn y, xwSc ox,ywSRcS必要性，已知Rc S,则任取y,xURe ox,yGRnx,ywS oy,xwScRCcSe6. (R)c=Rc证明：任取y,xu (R)c ox,yu Rox,y笑 R oy,x笑Rc oy,xu R
11、c .(R) c=Rc7. R是A上关系，则(1) R是对称的，当且仅当Rc =RR是反对称的，当且仅当RHRc cIAo证明： 充分性，已知Rc=R (证出R对称)任取x,yeA设x,ywR，贝ly,xGRc，而Rc =R 所以有y,xwR，所以R对称。3-6 关系的闭包运算关系的闭包是个很有用的概念，特别是传递闭包。关系的闭包是通过关系的复合和求逆 构成的一个新的关系。这里要介绍关系的自反闭包、对称闭包和传递闭包。一.例子给定A中关系R,如图所示，分别求A上另一个关系R使得它是包含R的“最小的” (序偶尽量少)分别具有自反(对称、传递)性的关系。这个R就分别是R的自反(对称、传 递)闭包。
12、二定义：给定A中关系R,若A上另一个关系R, 满足：(l)RcR；(2) R 是自反的(对称的、传递的)；R是“最小的”，即对于任何A上自反(对称、传递)的关系R”，如果RcR”，就 有 R cR”。则称 R是 R 的自反(对称、传递)闭包。记作 r(R)、(s(R)、t (R) (reflexive、symmetrie、 transi tive)实际上r(R)、(s(R)、t (R)就是包含R的“最小”的自反(对称、传递)关系。、I ZrA- * 、亠三. 计算方法定理1给定A中关系R,则r(R)=RUIAo 证明：令R=RUIA,显然R是自反的和RcR，下 面证明R是“最小的”：如果有A上
13、自反关系R”且RcR”，又IAcR”，所以RUIAcR”， 即R cR”。所以R就是R的自反闭包。即r(R)=RUIA。定理2给定A中关系R,则s(R)=RU RC。证明方法与1.类似。定理3给定A中关系R,则t(R)=RUR2UR3U.。证明：令 R= RUR2UR3U.,显然有 RcR ；定理4给定A中关系R,如果A是有限集合，|A|=n则t(R)=RUR2U. URn 求 t(R)的矩阵 Warshall 算法：| X|=n, RcXXX,令MR=A R2的矩阵为A2,Rk的矩阵为Ak .于是t(R)的矩阵记作MR+=A+A2+Ak +(+ 是逻辑加)置新矩阵 A ：=MR ;置 i=1
14、;对所有j，如果Aj,i =1 ,则对k=l，2，,nAj,k:=Aj,k+Ai,k;/*第 j 行+第 i 行,送回第 j 行*/i加1；如果iWn,则转到步骤，否则停止。下面举例，令X=1,2,3,4,X 中关系 R 图如右图所示。运行该算法求t(R)的矩阵：四. 性质定理5. R是A上关系，则(1)R是自反的，当且仅当r(R)=R.R是对称的，当且仅当s(R)=R. R是传递的，当且仅当t (R)=R. 定理6. R是A上关系，则(1)R是自反的，则s(R)和t(R)也自反。R是对称的，则r(R)和t(R)也对称。R是传递的，则r(R)也传递。 定理7：设R是A上关系，则 sr(R)=rs(R)(2) tr(R)=rt(R) st (R)匸ts(R)证明：(1) sr(R)=r(R) U (r(R)c=(RUIA) U (RUIA)c=(RU IA) U (Rc U IAc) =RU IA U Rc U IA= (RURc)UIA= s(R)UIA=rs(R) 的证明用前边证明的结论： (RU IA)k= IAU RU R2U . U
