(第10讲)二元关系.pptVIP

* 表现在关系图上：关系R是传递的当且仅当其关系图中，任何三个结点x,y,z（可以相同）之间，若从x到y有一条边存在，从y到z有一条边存在，则从x到z一定有一条边存在。 表现在关系矩阵上：关系R是传递的当且仅当其关系矩阵中，对任意i,j,k{1,2,3,…,n}，若rij=1且rjk=1，必有rik=1。 结论 * 例 整除关系DN是N上的传递关系。 证明：?x,y,z∈N，如x,y∈DN，y,z∈DN，即x能整除y，且y能整除z，则必有x能整除z，即x,z∈DN，所以整除关系具有传递性。 例 ρ(A)上的包含关系?，具有传递性。 因为若u?v，v?w，则必有u?w。 例 实数集上的≤关系也具有传递性。 因为若x≤y，y≤z，必有x≤z。 其它如全域关系UA，空关系?，恒关系?A均是传递的。 关系性质的逻辑表示 设R是集合A上的二元关系， R是自反的? 是永真的 R不是自反的? 是永真的 R是反自反的? 是永真的 R不是反自反的? 是永真的 R是对称的? 是永真的 R不是对称的? 是永真的 * 关系性质的逻辑表示(续) R是反对称的? R是传递的? 是永真的 R不是传递的? 是永真的 是永真的 R不是反对称的? 是永真的 * 设A＝{1,2,3},试判断如下图所示A上关系的性质： 图a)的关系是自反的、对称的、反对称的、传递的关系； 图b)的关系是具备反自反的、对称的、反对称的、传递的关系； 图c)的关系是具备对称的、反对称的、传递的关系； 图d)的关系是不具备任何的性质关系； * 图e)的关系是具备自反的、对称的、传递的关系； 图f)的关系是具备反自反的、反对称的、传递的关系； 图g)的关系是具备反自反的、反对称的关系； 图h)的关系是具备反自反的、反对称的、传递的关系。 例 * 设A是任意的集合， A上的全关系A×A是自反的、对称的、传递的关系； A上的空关系Φ是反自反的、反对称的、对称的、传递的关系； A上的恒等关系IA是自反的、对称的、反对称的、传递的关系。 例 例 朋友关系是自反的、对称的、而非传递的关系； 父子关系是反自反的、反对称的、而非传递的关系. * * * * * * * * * * * 图a)的关系是自反的、对称的、反对称的、传递的关系； 图b)的关系是具备反自反的、对称的、反对称的、传递的关系； 图c)的关系是具备对称的、反对称的、传递的关系； 图d)的关系是不具备任何的性质关系； 图e)的关系是具备自反的、对称的、传递的关系； 图f)的关系是具备反自反的、反对称的、传递的关系； 图g)的关系是具备反自反的、反对称的关系； 图h)的关系是具备反自反的、反对称的、传递的关系。 * 图a)的关系是自反的、对称的、反对称的、传递的关系； 图b)的关系是具备反自反的、对称的、反对称的、传递的关系； 图c)的关系是具备对称的、反对称的、传递的关系； 图d)的关系是不具备任何的性质关系； 图e)的关系是具备自反的、对称的、传递的关系； 图f)的关系是具备反自反的、反对称的、传递的关系； 图g)的关系是具备反自反的、反对称的关系； 图h)的关系是具备反自反的、反对称的、传递的关系。 * 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ C S | S W U S T XDC 没有问题，就是最大的问题！ * 4.1.4 关系的性质 一、自反性和反自反性 定义 设A是一个集合， R是A上的二元关系， （1）若?a∈A，都有a,a∈R，则称R是自反的，或称R具有自反性。 （2）若?a∈A，都有a,a?R，则称R是反自反的，或称R具有反自反性。 * 设A={a,b,c,d}， 例 R={a,a,a,d,b,b,b,d,c,c,d,d}。 因为A中每个元素x，都有x,x∈R，所以R是自反的。 R的关系图 R的关系矩阵 * S={a,b,a,d,b,c,b,d,c,a,d,c}。 例 (续1)