数理逻辑精品教学（华南理工大学）10-2 关系.pptx

复习思考题8;复习思考题8;复习思考题8;第10章 关 系;10.4.2 运算与性质的关系;自反性证明;对称性证明;反对称性证明;;关系性质的充要条件;10.5 关系的闭包;10.5.1 多个关系合成的运算;多个关系合成的运算;多个关系合成的运算;多个关系合成的运算;同理， R4 = R3°R =R2， R5=R4 ° R=R3 还可以得到——R2=R4=R6=…, R3=R5=R7=…;R0, R1, R2, R3,…的关系图如下图所示;定理 设A是有限集, R是A上的关系, m, n∈N, 则 (1) Rm°Rn=Rm+n (2) (Rm)n=Rmn 证(1) 用归纳法  对?m∈N, 施归纳于n. 若n=0, 则有 Rm°R0=Rm°IA=Rm=Rm+0 假设Rm°Rn=Rm+n, 则有 Rm°Rn+1 =Rm°(Rn°R) =(Rm°Rn)°R =Rm+n+1 , 所以, 对?m, n∈N有Rm°Rn=Rm+n. ;10.5.2 关系闭包的定义;10.5.3 闭包的性质;10.5.3 闭包的性质;10.5.3 闭包的性质;10.5.4 闭包的构造方法;证明: t(R) = R?R2 ? R3 ? …;证??: t(R) = R?R2 ? R3 ? …;闭包的构造方法举例;;闭包的矩阵构造方法举例;闭包的矩阵构造方法举例;传递闭包的计算——Warshall算法;Warshall算法求传递闭包;1: B ? M(R) 2: for i =1 to n do 3: for j =1 to n do 4: if B[j, i ] =1 5: for k =1 to n do 6: B[j, k] ?B[j, k] ? B[i,k];作业13