离散数学 ch2.二元关系(3,4节)

1、2-3关系的性质，本节研究关系的性质，它们在关系研究中起着重要作用。这是本章最重要的部分。本节中介绍的关系是集合a的关系。关系的性质主要是反射性、反反射性、对称性、反对称性和传递性。1.反射性(反射性)定义：设置R是集合A的关系，如果所有X都有(X，x)R(即xRx)，则R称为A的反射性关系。示例：在实数集合中，“”是自身的反比例，因为任意实数x有x。它不是磁反，反磁的充分要求：R是从A到磁反A R，在关系导向图中，磁反3360每个节点都有一个环。关系矩阵中的反射性：主对角线全部为1。A=1，2，3给定的A的8个关系如下：2 .定义反射性：如果R是集合A的关系，并且所有xA都有(x，x)R，则

2、R称为A的非反射性关系。(逆推说)充分的先决条件：R是A中非自愿的A R F在关系流向图中的非自愿性：每个节点上没有环。关系矩阵中的郑智薰反射性：主对角线全部为零。事实上比关系小，父子关系是对是错。注：1)磁盘和非磁盘反射不是互补的，不磁盘的关系不一定是非自愿的。例如，前面的R6，R7不是子班，也不是子班。2)在矩阵中，如果rii同时具有0和1，则R既不是反射也不是反反射。下面的R2，R5，R8，都是半反关系。设置示例1，R是A中的非一半A R F，R是A中的一半A R，(1)。磁盘，磁盘，磁盘，磁盘，磁盘，磁盘，磁盘。对称定义的：R是集合X中的关系。充分必要条件：R对A对称。=RC在关系方向

3、图中查看对称。徐璐位于其他两个节点之间。如果存在边，则相反方向的两条边将在关系矩阵中看到对称。主对角线对称的矩阵。邻里关系、朋友关系、同学关系是对称关系。下面的R3、R4、R6、R8是对称关系。4 .反对称定义：将R设置为集合X中的关系，如果对于任何X，yX，有(X，y) R和(y，x) R，那么如果x=y，那么R就称为A中的反对称关系。按事实计数比关系小，都是反称。父子关系是反称。充分必要条件：R是X的不对称RC A。在r的关系图中查看不对称。徐璐在其他两个节点之间最多有一条边。关系矩阵中的不对称：对称主对角线的两个元素中最多有一个。1)相关矩阵是对称矩阵的前置2)如果是rij，则rji=，

4、如果是rij，则不需要rji。也就是说，允许rijrji。3)此外，对称和反称不是完全相反的，有些关系是对称和反称(例如，共关系和恒等关系)。下面的R1、R2、R4、R5和R8都是不对称关系。R4、R8是对称和相反的名称。(2)对称和不对称，R在X对称RC A，R在A对称=RC，5。传递性定义：R具有X中的关系，所有X，Y，zX的(X，y) R和(Y实数集的，集合，传递)。*不容易知道关系图和关系矩阵中是否有可传递性。在某些情况下，必须根据传播的定义直接检查。检查时要特别注意。没有传递的条件，也不需要传递的结果。即使定义表达式的前面是f，此表达式也是t。也就是说，如果(x，y)R和(y，z)R

5、之一是f(即，定义的前部分是false)，则传递R。例如，如果(，)，(，)之一不属于R，那么讨论(a，c)是否属于R就没有意义了。传递了a、b、c、d、(，)、(，)。问题：对称性和传递性是否能引入反射性，下面的R1，R3，R4，R5，R8都是传递的关系。，或者，定义的前面部分为false。aij=1且ajk=1时，aik=1；关系矩阵中关系方向图中的aik=1不对称；(1，2)R1；(2，1) R1对称；传递。注意事项：如果将变更为，则没有反射性，是半反射性的。示例：2(，)，磁相反，不对称，对称，传递。例如3 (1，2) 1 2，1，2()，其中()是功率集。磁反、不对称、对称、传递。注

6、意：更改后，没有反射性。例如：4(，)偶数、磁相反、对称、传播：偶数、偶数、偶数：()(c)偶数和偶数的差别偶数。例如5(，) (，)(，)、(互元素)、对称，但不是磁性的，也没有传递性。此部分要求：1.正确把握这五种性格的定义。善于判断和证明5种性格。注意：在确定关系R特性时，当特性定义表达式的前面部分为F时，必须特别注意此表达式T，即R满足此特性。(除了磁反和郑智薰磁反)，希望2-4关系的封闭运算，给定的a中关系r，有时r有磁反(对称，传递)性等有用的特性。为此，我需要在r中添加一些序列，有时r具有我想要的特性，但我不希望r“太大”。关闭关系是一个很有用的概念，尤其是传递关闭。关系的封闭是

7、通过关系的复杂性和倒退而构成的新关系。介绍关系的磁反闭，对称闭包，过渡闭包。介绍关系的磁半闭，对称闭包，传输闭包。1 .例如，在给定的A中，关系R求出了A的另一个关系R，如图所示，使包含R的“最小”(顺序尽可能少)具有各自的反方向(对称，传递)性。此R分别是R的反射(对称，传输)闭合。这三个图分别是R的自反转、对称、传输闭包。2.定义：如果给定A中的关系R，A有其他关系R，则满足：RR；r是磁反方向(对称，传递)。r是“最小”。也就是说，在所有A中，对于自身反转(对称，传递)关系R，如果存在RR，则存在RR。R称为R的反射(对称，传输)闭包。r(R)、(s(R)、t(R)(reflexive、

8、symmetric、transitive)，实际上是R(R)、(s(R)清理计算方法1。给定a中的关系R，r(R)=RIA。证明：R=RIA，很明显，R是反射和RR，R是“最小值”。a有反射关系r 和RR ，IAR 所以是RIAR ，也就是RR 。R是R的磁反闭。R(R)=RIA。整理2。给定a中的关系R，s(R)=R .证明方法为1 .中所述。(集合法)定理3。给定a中的关系R，t(R)=RR2R3.证明：R=RR2R3.显然有RR。证明R被传递：随机x，y，zA，(x，y)R (y，z)R，R定义的整数I，j，y为(x，y) ri，(y，r)；证明R为“最小值”。如果a具有关系R 和RR

9、，(证明RR)随机(x，y)R，则必须具有由R定义的整数I，因为(x，y)Ri根据关系RR ，所以(x，E1) r (E1，E1).r 。R 传递导致(x，y)R 。RR”。摘要R是R的传输闭包，即t(R)=RR2R3=Ri。使用上面的公式计算t(R)，就像无法计算R的无限平方一样。否则，在以下范例： A=1，2，3 A中，关系R1，R2为R1=(1，2)，(1，3)，(3，2) R2=(1，R24=R2).t(R2)=R2 R23 R24，清理4。给定A中的关系R，A是有限集|A|=n，t(R)=RR2.Rn .证明：R=RR2R3.Rn，t(R) R R2.如果Rn R只有R=t(R)所有K的Rk R，那么当k