《离散数学》中二元关系传递性的判定

张振荣

摘 要 《离散数学》中二元关系性质中传递性的判定是教学难点，本文列出传递性的真值表，利用真值表判断传递性直观有效，只有一种情形不满足传递性，其余情形都满足传递性。

关键词 《离散数学》 二元关系

0引言

在《离散数学中》，二元关系的性质包括自反性、反自反性、对称性、反对称性和传递性。其中前四个性质可以由定义和关系图直观地表达，但是否满足传递性仅从定义很难观察出来。二元关系传递性的定义如下：

如果从定义来看，只能发现一种情形是满足传递性的，即如，，，是传递的，但是，怎么用定义来判断是否满足传递性呢？

1利用真值表判断传递性

我们不妨用真值表来分析这个定义，列出真值表如下：

真值表的第一种情形是我们熟悉的，从定义直接能判断出来的。比如，为真，为真，为真，则满足传递性。

从真值表判断，第二种情形真值为假，即不满足传递性。比如，没有出现有序对，则为真，为真，为假，由真值表知，这是不满足传递性的。

第三种情形和第五种情形看似不传递，但满足传递性的定义。如，为真，为假，为真，由真值表知，这是满足传递性的。再如，为假，为真，为真，满足定义，是传递的。

第四种、第六种、第七种情形都是包含一个有序对的，满足传递性，以第四种情形为例，，为真，为假，为假，最后真值为真，故是传递的。

第八种情形是空关系，虽然没有有序对，但是真值为真，故满足传递性。

定义理解清楚后，是不是所有的二元关系都很容易判断了呢？在二元关系中，包含很多组有序对，如果有一组有序对不满足传递的定义，但其他组都满足传递的定义，那这个二元关系仍然是不传递的，比如分三组有序对考虑：（1）为真，为真，为真，则满足传递性;（2）为真，为真，但为假，故不传递;（3）为真，为真，但为假，故不传递;因为（2）（3）不传递，故不满足传递性。

如果定义中的有两个或三个相等，那么它仍然符合传递性的定义。如，将有序对分为三组考虑：（1）有序对，（2）有序对，（3）有序对，三组都满足传递性的定义，故是传递的。

2总结

综上所述，根据传递性的定义判断二元关系是否具有传递性容易出错，而结合定义的真值表发现，只要二元关系中包含第二种情形，则就不是传递的，其余情形都是传递的。

参考文献

[1] 屈婉玲.離散数学（第3版）[M].北京：清华大学出版社，2014.