离散数学电子教材3b.doc

《离散数学电子教材3b.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.8关系的闭包运算关系作为集合,在其上已经定义了并、交、差、补、复合及逆运算。现在再来考虑一种新的关系运算－关系的闭包运算，它是由已知关系，通过增加最少的序偶生成满足某种指定性质的关系的运算。例如,设，上的二元关系，则上含且最小的自反关系是：；上含且最小的对称关系是：；上含且最小的传递关系是：。定义3.8.1设是上的二元关系，如果有另一个上的关系满足：（1）是自反的（对称的，传递的）；（2）；（3）对于任何上的自反的（对称的，传递的）关系，若，就有。则称关系为的自反（对称，传递）闭包(Reflexive(Symmetric，Transitive)Closure)，记作。显

2、然，自反（对称，传递）闭包是包含的最小自反（对称，传递）关系。定理3.8.1设是上的二元关系，那么（1）是自反的，当且仅当（2）是对称的，当且仅当（3）是传递的，当且仅当证明（1）若是自反的，，对任何包含的自反关系，有，故；若，根据闭包定义，必是自反的。（2）、（3）的证明完全类似。下面讨论由给定关系，求取的方法。定理3.8.2设是集合上的二元关系，则143（1）；（2）（3），通常也记作。证明（1）令，，因为，故，于是在上是自反的。又即。若有自反关系且，显然有，于是，所以。（2）令，因为所以是对称的。若是对称的且，，则。当时，；当时，，，。因此，故。（3）令，先证是传递的

3、。，，则存在自然数，有，，因此，所以，是传递的。显然，。若有传递关系且，，则存在自然数，有，则，使得，因此，由于是传递关系，则，所以。故143。例3.8.1设，是上的二元关系，，求。解为了求得，先写出即继续这个运算有：从以上例题中看到，若有限，譬如含有个元素，那么求取上二元关系143的传递闭包不必计算到对的无限大次复合，而最多不超过次复合。定理3.8.3设是含有个元素的集合，是上的二元关系，则存在一个正整数，使得证明设，记。若，则存在整数，使得成立，既存在序列，，有。设满足上述条件的最小大于，不妨，则序列中必有，使得或。不妨，此时序列就成为，这表明存在，其中，这与是最小的假

4、设矛盾，所以，不成立，即。所以（）一般地，取，式中的给出了复合次数的上限。例3.8.2设，给定上的关系，求。解所以143即为计算元素较多的有限集合上二元关系的传递闭包，Warshall在1962年提出了一个有效的算法（假定集合含有个元素）：（１）置新矩阵：；（２）置：；（３）对，若（），则置：，；（４）：；（５）如果，则转到步骤（3），否则停止。例3.8.3已知，求。解按照Warshall算法，从出发，只要遵循“置行查列遍寻真，见真行上析当今，行推列移下右再，行穷列尽闭包成”便可直接求得。对集合上关系，首先将其关系矩阵赋予：而后的每后一次循环重复操作，均在前一次操作结果的矩

5、阵上进行。置当今行为第1行，查看第1列中1，对有1的行进行改写，改写方法是：将当今行的元素与列中有1的行的元素分别做析取。对本例，时，第1列中只有，将第一行与第一行各对应元素进行逻辑加，仍记于第一行：；置当今行为第2行，查看第2列中1，对有1的行进行改写。对本例，时，第二列中，将第二行与第一行各对应元素进行逻辑加，仍记于第一行：143；置当今行为第3行，重复上述操作并结束。对本例，时，第三列中，将第三行分别与第一行、第二行、第三行各对应元素进行逻辑加，仍分别记于第一行、第二行、第三行：得。结果与例3.8.2一致。传递闭包在语法分析中有很多应用，先以下列说明/例3.8.4设有

6、一字母表并给定下面六条规则：为定义在上的二元关系且，即是从出发用一条规则推出一串字符，使其第一个字符恰为。说明每个字母连续应用上述规则可能推出的头字符。解则表示从出发，经过多次连续推导而得的字符串，其第一个字符恰为的关系，此关系即是。按照Warshall算法计算的过程中，时，由于第五行的元素都等于零，的赋值不变。时，由于第3、6、7列各元素均为零，的赋值不变。经计算得143因此。这说明应用给定的六条规则，从出发推导的头字符有三种可能，而从出发推导的头字符有两种可能，而从推出的头字符有两种可能，从出发推导的头字符只可能为。从一种性质的闭包关系出发，求取另一种性质的闭包关系，具

7、有以下运算律：定理3.8.4设是集合上的二元关系，则（1）（2）（3）证明（1）这里，。（2）这里，，（）。（3）留作练习请读者自证。习题3.81．设是上的二元关系，证明或反驳下列命题：（1）若，则；143(2)若，则；(3)若，则；(4)；（5）)；(6)；(7)；(8)，其中；(9)；(10)对称关系的传递闭包是对称的；（11）反对称关系的传递闭包是反对称的。2．试找出个元素的集合和上的关系，使都是不相交的，以表明定理3.8.3给出的界限是不可改善的。3．试找出个元素的集合X和X上的二元关系，使都是有区别的，并