离散数学第4.4陈瑜.ppt

计算机科学与工程学院 陈瑜 Email：chenyu.inbox@ * §4.4二元关系的闭包 设R是A上的关系，我们希望R具有某些有用的性质，比如自反性、对称性、传递性等。如果R不具有这些性质，可以通过在R中添加一些有序对来改造R，得到新关系R′，使R′具有上述性质，但又不希望R′与R相差太多，即添加的有序对要尽可能的少，满足这些要求的R′就称为R的闭包。 例4.14 例4.14 例4.14 例4.14 例4.14（续） 利用关系图和关系矩阵求闭包 利用关系图和关系矩阵求闭包 利用关系图和关系矩阵求闭包 定理4.5(p62) 定理4.5(p62) 例4.15 设R={(1,1),(1,2),(2,3),(3,2),(3,4)} i:=1; ∵i=1时,A的第一列中只有A(1,1)=1,将A的第一行上元素与本身作逻辑加,结果送该行,A不变。 i:=i+1; i=2,A的第二列有两个1,即A(1,2)=A(3,2)=1 例4.15（续1） 分别将A的第1行和第3行与第二行对应元素作逻辑加,将结果分别送1,3行得: (注：i=2) 例4.15（续2） i:=i+1; i=3,A的第3列有3个1,即A(1,3)=A(2,3)=A(3,3)=1, 分别将A的第1,2,3行与第3行对应元素作逻辑加,将结果分别送1,2,3行得: i:=i+1; i=4,A的第4行全为0,A不变。 i:=i+1; i=5)4=n,停止,即得: i:=i+1; i=4,A的第4行全为0,A不变。 i:=i+1; i=5)4=n,停止,即得: 习题 P66 16（1）（3） 在关系矩阵中，每列（结点）的每个等于1的元素反映的是该元素所在行（结点）到该结点有一条有向边；每行（结点）的每个等于1的元素反映的是该结点到该元素所在列（结点）有一条有向边。 在关系矩阵中，每列（结点）的每个等于1的元素反映的是该元素所在行（结点）到该结点有一条有向边；每行（结点）的每个等于1的元素反映的是该结点到该元素所在列（结点）有一条有向边。 闭包运算的性质 定理4.7 设R1，R2是集合A上的关系，且R1?R2，则： 1)r(R1)?r(R2) 2)s(R1)?s(R2) 3)t(R1)?t(R2) 定理4.8 设R是集合A上的关系，则： 1)若R是自反的，则s(R),t(R)也是自反的 2)若R是对称的，则r(R),t(R)也是对称的 3)若R是传递的，则r(R)也是传递的 闭包运算的性质 定理4.7 设R1，R2是集合A上的关系，且R1?R2，则： 1)r(R1)?r(R2) 2)s(R1)?s(R2) 3)t(R1)?t(R2) 定理4.8 设R是集合A上的关系，则： 1)若R是自反的，则s(R),t(R)也是自反的 2)若R是对称的，则r(R),t(R)也是对称的 3)若R是传递的，则r(R)也是传递的 多重闭包 定义4.8 1）集合A上的关系的自反对称闭包定义为: rs(R)＝r(s(R)) 2）集合A上的关系的自反传递闭包定义为: rt(R)＝r(t(R)) 3）集合A上的关系的对称传递闭包定义为: st(R)＝s(t(R)) 同理，我们还可定义sr(R),tr(R),ts(R),… 多重闭包 定理4.9 设R是集合A上的关系，则： 1)rs(R)＝sr(R) 2)rt(R)＝tr(R) 3)st(R)?ts(R) 证明： 1)sr(R)=s(R∪IA)=(R∪IA)∪(R∪IA)-1 = R∪IA∪R-1∪IA = (R∪R-1)∪IA =s(R)∪IA=rs(R) 多重闭包 定理4.9 设R是集合A上的关系，则： 1)rs(R)＝sr(R) 2)rt(R)＝tr(R) 3)st(R)?ts(R) 证明： 1)sr(R)=s(R∪IA)=(R∪IA)∪(R∪IA)-1 = R∪IA∪R-1∪IA = (R∪R-1)∪IA =s(R)∪IA=rs(R) 多重闭包 定理4.9 设R是集合A上的关系，则： 1)rs(R)＝sr(R) 2)rt(R)＝tr(R) 3)st(R)?ts(R) 证明： 2)tr(R)=t(R∪IA) =(R∪IA)∪(R∪IA)2 ∪… =IA∪R∪R2∪ … =IA∪t(R)=rt(R) 。 多重闭包 定理4.9 设R是集合A上的关系，则： 1)rs(R)＝sr(