(第12讲)二元关系.ppt

没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ * 定义　设R是集合A上的二元关系，则可 定义R的n次幂Rn,该Rn也是A上的二元关系，定义 如下： 1.R0＝IA＝{a,a|a∈A}； 2.R1＝Ｒ； 3. R2＝ R?R 3.Rn+1＝Rn?R＝R?Rn。 四、关系的幂 显然，Rm+n＝Rm?Rn,(Rm)n＝Rmn。 * 例：设A＝{a,b,c,d,e,f},定义在A上的关系 R＝{a,a,a,b,b,c,c,d,d,e,e,f}，求Rn。 解　 R0 ＝ IA＝{a,a, b,b, c,c,……. f,f} R1＝R， R2＝R?R＝{a,a,a,b,a,c,b,d,c,e,d,f}， 　R3＝R?R?R＝R2?R ＝{a,a,a,b,a,c,a,d,b,e,c,f}， 　R4＝R3?R＝{a,a,a,b,a,c,a,d,a,e,b,f}， 　R5＝R4?R＝{a,a,a,b,a,c,a,d,a,e,a,f}， 　R6＝R5?R＝{a,a,a,b,a,c,a,d,a,e,a,f} ＝R5， 　R7＝R6?R＝R5，…，Rn＝R5　(n＞5)。 * 定理3.2.4 令R?A?A，且|A|=n，则存在i和j，使得Ri=Rj，其中0≤ij≤2n2。 定理3.2.5 令R?A?A，若存在i和j，ij，使得Ri=Rj。且d=j-i，则 (1) 对任意k≥0,Ri+k=Rj+k。 (2) 对任意k,m≥0，Ri+md+k=Ri+k。 (3) 设S={R0,R1,R2,···,Rj+1}，对?n?N，有Rn?S。 * 定义 R是非空集合A上的二元关系，若A另外有一个关系R?满足如下三条： (1）R?是自反的 (2）R?R? (3）对A上任何一个满足以上两条的关系R?? ，均有R?? R?? 则称关系R?为R的自反闭包，记作r(R) 。 五、关系的闭包 (对称的，传递的） (对称、传递)闭包 (s(R) 、t(R)) * 定义的有关说明: (1). 由(2)知，R?是在R的基础上添加元素(序偶)； (2). 由(1)知，R添加元素其目标是使R?具有自反性(对称性，传递性)； (3). 由(3)知，在添加后使之具有自反性的所有关系中R?是最小的一个，即要在保证其具有自反性的前提下，应尽量少添加元素，多余的元素就不要加入。 * 例 设集合A={a,b,c}，A上的关系 R={a,a,a,b,b,c}。 则R的自反闭包为： 对称闭包： 传递闭包： r(R)={a,a,a,b,b,c,b,b,c,c} s(R)={a,a,a,b,b,a,b,c,c,b} t(R)={a,a,a,b,b,c,a,c} * 例 定义在N上的“＝”关系， 其自反闭包r(R)为“＝”； 其对称闭包s(R)为“＝”； 其传递闭包t(R)为“＝”。 40--* 设集合A＝{a,b,c},R＝{a,b,b,b,b,c}是定义在A上的二元关系，求r(R),s(R),t(R),并画出R，r(R),s(R),t(R)的关系图和求出相应的关系矩阵。 例 解： r(R)＝{a,b,b,b,b,c,a,a,c,c}； s(R)＝{a,b,b,b,b,c,b,a,c,b}； t(R)＝{a,b,b,b,b,c,a,c}。 * 例 (续) * 求一个关系的自反闭包，即将图中的所有无环的节点加上环；关系矩阵中对角线上的值rij全变为“1”。 求一个关系的对称闭包，则在图中，任何一对节点之间，若仅存在一条边，则加一条方向相反的另一条边；关系矩阵中则为：若有rij＝1(i≠j)，则令rji＝1(若rji≠1) 。 求一个关系的传递闭包，则在图中，对任意节点a,b,c,若a到b有一条边，同时b到c也有一条边，则从a到c必增加一条边(当a到c无边时)；在关系矩阵中，若rij＝1，rjk＝1,则令rik＝1(若rik≠1)。 利用关系图和关系矩阵求闭包 * 定理 设R是非空集A的关系，则 (1). R是自反的充要条件是R=r(R) (2). R是对称的充要条件是R=s(R) (3). R是传递的充要条件是R=t(R) * 定理 设R是非空集A的二元关系，则r(R)=R??A 证明：R?R??A , R??A是自反的，满足定义中的前两条。 设R??满足R?R?? ，R??是自反的。 ?a,b?R??A，则a,b?R或a,b??A。 如果a,b?R，由R?R?? ，则a,b? R?? ； 如a,b??A。则必有a=b，即a,a??A，由于R ??是自反的，则a,b?R ?? ，总之均有a,b?R ?? ? R??A?R?? ，满足定义第3条。 ? r(R)=R??A * 定