离散数学 关系的闭包ppt课件

1、.1，4.4关系的闭包，定义闭包的构造方法集合是表示闭包特性的矩阵表示，2，1，闭包定义，非空集a的R的关系定义，R的自反转(对称或传递)闭包与a的关系R，R满足以下条件：(1) r表示包含自身反转(对称或传递)(2) RR (3) a中的r的所有自身反转(对称或传递)关系r的RR。通常，将R的自反转闭包记录为r(R)，将对称闭包记录为s(R)，将传输闭包记录为t (r)，(3，从闭包的定义中可以看出，R的自反射(对称，传递)闭包包含R，具有自反射(对称，传递)特性如果R已经是反射二进制关系，则R=r(R)。同样，如果r是对称的二进制关系，则r=s(r)；如果R是传递的二进制关系，则R=t(R

2、)，反之亦然。4，2，关系的闭包运算，(1)如果知道集的二进制关系R，则r(R)，s(R)，t(R)是唯一且包含R的最小自反转(对称，传递)关系。(2) r为反射(对称，传递)时，r(R)、s(R)、t(R)为R本身。(3)如果r不是自反转(对称，传递)，则可以补充最小顺序对，使其成为自动、对称、传递关系，从而得到r、s (r)、t (r)。5，例如，设置a=a，b，c，r=，r(R)，s(R)，t(R)。解决方案：r(R)=，s (r)=，t (r)=，例如a=a，6，r设置为a的二进制关系，x-a，将所有(x，x) r的排序对添加到r，以扩展到其自身的二进制关系，例如，a=a，b，c，d，

3、r=(a，x)r的自反转闭包r (r)=(a，a)，(b，d)，(c，c)，(b，b)，(d，d)。可以得到：定理： R是a的二进制关系，R的自闭包R(R)=Ria。1 .构造r的自闭包的方法。第三，闭包的构成方法，7，2。构造r的对称闭包的方法。只要R成为(a，b)，例如，a=a，b，c，d，e，r=(a，a)，(a，b)，(b，a)，(b，c)，r的镜像闭包s (r)=(a，a)，(a，b)，(b，a)，(b，c)，(c，b)，(d，e)，定理3360 R是a的二进制关系，如果是反向关系，则R的对称闭包s (r)=r 。可以通过反向关系的定义知道：8、3。配置r的传递闭包的方法。将R设置为

4、a的二进制关系，将(a，b)R和(b，c)R和(a，c) r添加到R以扩展到R1，R1称为R的传递扩展，如果R1是传递关系，则R1是R的传递闭包。如果R1不是传播关系，则继续查找R1的传播扩展R2，如果R2是传播关系，则R2是r的传播闭包。R2的传播扩展R3(如果R2不是传播关系).如果a是限制集，那么r在限制扩展后可以得到r的传递闭包。扩展的传递关系是R的传递闭包t(R)。，定理3360将r设置为a的关系，t(r)=rR2R3.说明：关于穷集A (|A|=n)的关系，常识是Rn .9，事故：a=a，b，c，d，r=，r(R)，s(R)，t(R)，解决方案3330R1=，t(r)=r-R2-R

5、3-R4，R2=，R3=，R3=，。10，构造闭包的方法(续)，关系r，r，s (r)，t (r)的关系矩阵分别为M，Mr，Ms，Mt时Mr=m e ms=m mt.e是与M相同的单位矩阵，M 是M的转换矩阵。在上述方程中，矩阵的元素相加时的逻辑相加。11，注意闭包的构造方法(续)，关系设置R、R、s、t(R)的关系图分别与g、gr、gt、g、gt的顶点集相同。除了g的角外，使用以下方法添加新边：检查g的每个顶点，如果没有环，则添加环，最终搜索Gr. g的每个边，如果存在从Xi到XJ的单向边，则将I-j添加到g的XJ到Xi的相反方向，然后检查gs.g的每个顶点Xi，以查找从Xi出发的每个路径。

6、如果从Xi到路径中的节点XJ没有边，请添加此边。检查所有顶点后，图形gt。12，示例1显示了A=a，b，c，d，R=，R与r(R)、s(R)、t(R)的关系图，如下图所示r、r、s (r)、t (r)和南宁空调回收南宁空调。用户可以在投影仪或计算机上进行演示，打印演示文稿，将其制作成胶片，并应用于更广泛的领域。使用Microsoft Office PowerPoint，您不仅可以创建演示文稿，还可以直接在internet上举行面对面会议、远程会议或向观众演示演示文稿。Microsoft Office PowerPoint支持PPT、pptx以等格式创建的演示文稿。或pdf、图片格式等。14，如

7、果清理R为a相关系，则930；R是反射的，仅r (r)=R. r (r)是对称的，并且仅传递s (r)=r. r (r)，则和t (r)=R. r (r)如果定理R是a相关系，则930；R是磁反，s(R)和t(R)也是磁反。如果R是对称的，则r(R)和t(R)也是对称的。如果传递了R，则r(R)也将传递。证明： 93360 93360；R(R)=R，即R-ia=R，R(s)=s(R)-ia=(R-R-R-)r-1=r(r)8746；r-1=r-1=s(r)-s(r)相反。15一样，可以在t(R)中反向证明。证明t(R)对称：(t(R)-1=(RR2rn.)-1=r-1=r-1-1(rn)-1.

8、=r-1；(r-1) 2.(r-1)n；=r-R2-rn.(R对称，R对称一样，可以证明r(R)也是对称的。证明(r)证明(r)传递(r):首先用归纳法证明以下结论.riI=1点ria=iar结论。Ik是(ria)k=iarR2rk，16，I=k 1:00(ria)k 1=(ria)k(ria)=(iarR2K6；rk(ia r)=(ia r 2 8746；rk)rR2rR2rk 1因此得出结论。t(r)ia(22(r)ia)3.=(ia r R2)(ia r R2 R3).=ia-R(R)=ia-R(R)=R(R)。17，定理将R1，R2设置为a相关系，对于R1 R2，则为r(R1)r(R2)s(R2)s(R1)t(R2)证明清理将r称为a相关系，然后 33；Sr(r)=RS(r) tr(r)=rt(r)ts(r)证明： 33；Sr(r)=r，18，原因RS (r)，t(r)t