交大数理逻辑课件10-3关系

《交大数理逻辑课件10-3关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章关系10.1二元关系10.2关系矩阵和关系图10.3关系的逆、合成、限制和象10.4关系的性质10.5关系的闭包10.6等价关系和划分10.7相容关系和覆盖10.8偏序关系关系性质的充要条件设R为A上的二元关系,则R在A上自反当且仅当IARR在A上反自反当且仅当R∩IA=R在A上对称当且仅当R=R1R在A上反对称当且仅当R∩R1IAR在A上传递当且仅当RRR证：必要性：R是传递RRR∈RR(z)(x,zR∧z,yR)R∴RRR充分性：RRRR是传递

2、x,zR∧z,yRRRR∴R是传递的∵R是传递的∵RRR10.5.2关系闭包的定义闭包的定义包含R的最小自反关系是R的自反闭包包含R的最小对称关系是R的对称闭包包含R的最小传递关系是R的传递闭包一般地，将R的自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R).10.5.3闭包的性质定理10.5.4对非空集合A上的关系R，有若R是自反的r(R)=R;若R是对称的s(R)=R;若R是传递的t(R)=R.定理10.5.5对非空集合A上的关系R1、R2,若R1R2则r(R

3、1)r(R2)s(R1)s(R2)t(R1)t(R2)定理10.5.5对非空集合A上的关系R1、R2，则r(R1)∪r(R1)=r(R1∪R2)s(R1)∪r(R1)=s(R1∪R2)t(R1)∪r(R1)=t(R1∪R2)10.5.4闭包的构造方法设R为A上的关系,则有定理10.5.7:r(R)=R∪R0=R∪IA定理10.5.8:s(R)=R∪R-1定理10.5.9:t(R)=R∪R2∪R3∪…定理10.5.10:设A为非空集合，

4、A

5、=n，则存在一个正整数k≤n，使得t(R)=R∪R2∪R3∪…∪Rk(k≤n)t(R

6、)=R∪R2∪R3∪…∪Rn以上分别是自反闭包r(R)、对称闭包s(R)和传递闭包t(R)的构造方法证明:t(R)=R∪R2∪R3∪…先证R∪R2∪R3∪…t(R)①当n=1时，R1=Rt(R)。②设n=k时，Rkt(R)。下证Rk+1t(R)x,yRk+1x,yRk∘R(z)(x,zR∧z,yRk)(z)(x,zt(R)∧z,yt(R))x,yt(R)即Rk+1t(R)(k≥0)故R∪R2∪R3∪…t(R)证明:t(R)=R∪R2∪R3∪…再证t(R)R∪R2

7、∪R3∪…显然RR∪R2∪R3∪…下证明R∪R2∪R3∪…是传递的。x,zR∪R2∪R3∪…∧z,yR∪R2∪R3∪…(t)(x,zRt)∧(s)(z,yRs)(s,t≥0的自然数)x,yRt∘Rs=Rt+sR∪R2∪R3∪…x,yR∪R2∪R3∪…根据传递关系的定义，有R∪R2∪R3∪…是传递的。闭包的构造方法举例设A={a,b,c}，定义A上的二元关系R为：R={a,b,b,c,c,a}试用关系合成运算方法求：r(R)，s(R)，t(R)解:r(R)=R∪IA={

8、a,b,b,c,c,a,a,a,b,b,c,c}s(R)=R∪R-1={a,b,b,c,c,a,b,a,c,b,a,c}t(R)=R∪R2∪R3：R2=R∘R={a,c,b,a,c,b}R3=R2∘R={a,a,b,b,c,c}=IAt(R)={a,a,a,b,a,c,b,a>,b,b,b,c,c,a,c,b,c,c}=EA闭包的构造方法（矩阵法）设关系R,r(R),s(R),t(R)的关系矩阵分别为M,Mr,Ms和Mt,则

9、Mr=M+IMs=M+M’Mt=M+M2+M3+…说明:I是和M同阶的单位矩阵,M’是M的转置矩阵.注意:在上述等式中矩阵的元素相加时使用逻辑加.闭包的矩阵构造方法举例设A={a,b,c}，定义A上的二元关系R为：R={a,b,b,c,c,a}试求：t(R)解：用关系矩阵求t(R)的方法如下：闭包的矩阵构造方法举例其中，∨表示矩阵的对应元素进行逻辑加运算。闭包同时具有的多种性质定理10.5.11对非空集合A上的关系R，有若R是自反的s(R)、t(R)是自反的;若R是对称的r(R)、t(R)是对称的;若R是传递的

10、r(R)是传递的.证：∵R是传递RRR，而r(R)=R∪IAr(R)r(R)=(R∪IA)(R∪IA)=R(R∪IA)∪IA(R∪IA)=RR∪RIA∪IA(R∪IA)=R∪R∪(R∪IA)=R∪IA=r(R)注意：若R是传递的，s(R)是不