离散数学课程论文：探讨离散数学中的二元关系_离散数学传递性

摘要：

离散数学中的二元关系是非常重要的内容。它包括关系的基本概念，而关系的基本概念中包含自反关系、反自反关系、对称关系、反对称关系、传递关系，本课程论文将对这5种关系进行深入讨论，并给出对应的定义、关系图、关系矩阵、以及它们之间的关系。在对传递关系的讨论中，着重探讨了二元关系中传递关系的判定，并讨论了一道平时学习过程中经常弄错关于传递性判断的题目。最后对于二元关系的探讨进行思考与总结。

关键词：离散数学、二元关系、自反、反自反 、对称、反对称 、传递

---

目录

一、“关系”与“二元关系”的引入

二、自反关系

三、反自反关系

四、对称性

1.利用真值表判断传递性

2.关于传递性判断的总结

八、思考与总结

参考文献

---

---

一、“关系”与“二元关系”的引入

1.在日常生活中，关系一词是大家所熟知并且在生活学习和工作中经常遇到和处理的概念，我们都熟悉关系一词的含义，例如：兄弟关系、上下级关系、位置关系，在数学中，关系可表达集合中元素之 间的联系，如“4大于 3”、点 “P在点 a、b之间”，数学中的序偶 、序列可以表示两个客体、三个客体或 n个客体之间的联系。

2.数学中“关系”被抽象成为一个基本概念，它在计算机科学中被广泛应用；在形式语言、编程序设计、信息检索、数据结构 ，算法分析、数据库和有限自动机等方面起着重要作用。

3.在数学中，表示两个元素间的关系称为“二元关系”，表示三个及三以上元素之间的关系称为多元关系，二元关系是我们讨论 的重点内容 ，它包括：关系的基本概念 ，复合关系，逆关系、关系运算、等价关系，相容关系等。后续将对各种关系逐个进行分析。

二、自反关系

1.基本概念及例子：设 R是集合 x中的二元关系。对于每一个x∈X来说，如果 有 xRx亦即<x，x>∈R，则称 R是自反关系，并可表示成：

X中的R是自反的<-->

例如：（1）整数集合 z上的关系≤ (小于等于关系)正整数 

（2）集合N上的整除关系／都是自反关系。

2.在全集的所有子集的集合 中，包含关系、相等关系 (=)是 自反的，在实数集合中，因为对任何 x有 x≤X，所以关系≤是自反的。由自反性可以看出，真包含和小于关系不是自反的。 

1. 若用关系矩阵表示自反关系：矩阵的主对角线元素都为1；
2. 若用关系图表示，则图中每一节点上都必须有一条闭路，也可以说，若关系是自反的，则每点上都有环。
3. 若R1，R2为 A上的 自反关系，则经过并、交、逆 、合成运算以后仍能保持自反性 。
4. 任意一个关系ɑ是自反条件的充分必要条件是其关系图中的每一个结点都有自环。
5. 例如：X={1,2,3,4,5,6},R={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>}.

用关系矩阵表示：

主对角线元素为1，其余全为0

用关系图表示为：

三、反自反关系

1.设R是集合中的二元关系。对于每一个x∈X来说如果有 <x,x>不属于R，则称R是自反的。R是反自反的<->

在实数集R上的关系 ,“<”是反自反的。

2.在全集的所有非空子集的集合中，真包含关系是反自反的 ，但包含关系不是反自反的。集合 A上的恒等关系是自反关系，但自反关系却不一定是恒等关系。一个非空集合上的关系可以是自反的，不是自反的 ，或者是反自反的。

3.

（1）R1、R2为A上的反自反关系，则经过并、交、相对补、逆运算后仍能保持反自反性。

（2）任意一个关系ɑ为反自反关系的充要条件是关系图中没有一个自环。

（3）任意关系ɑ不是自反的，也不是反自反的充要条件是其关系图中有的结点有自环，而有的结点无自环。

例如：设集合X ={a,b,c} R={<a,a>,<a,b>,<c,b>,<3,3>},此时R既不是自反的，也不是反自反的。

1. 用关系矩阵表示反自反关系 ，则关系矩阵的主对角线元素全为零；若用关系图表示反自反关系的话 ，则图中的每结点上都没有闭路 ，即头上无环。
2. 例如：X={a,b,c,d}.关系R={<a,b>,<b,c>,<c,a>,<d,b>}

用关系矩阵表示为：

主对角线元素全为0.

用关系图表示为：

四、对称性

1.设R是中的二元关系。对于每一个x，y ∈X来说，如果每当xRy，则必定有 yRx，则称R是对称的关系 ，并可表示成 ：X中的 R是对称的<->

2.常见的对称关系

（1）In为N上的恒等关系，则 In是对称的，EN是Ⅳ上的全域关系，它是对称的。

（2）平面上直线的集合L上的关系 lI(平行关系)是对称的。

（3）相似关系也是对称关系。

3.关系图的特点：如果两个顶点之间有边 ，一定是一对方向相反的边；

关系矩阵的特点：对称关系的关系矩阵是一个对称矩阵。

4.R1、R2为 A上的对称关系，则经过并、交、相对、补、逆运算后仍能保持其对称性。

5.任意一个关系ɑ是对称的充要条件是关系图中任意两点间有弧线连结，且是双向的。

五、反对称关系

1. 概念：设 R是集合 中的二元关系、对于每一个x、y∈X来说 ，如果每当xRy和 yRx，就必有 x=y，则称是反对称的关系，也就是说，当且仅当：

中的关系R才是反对称的。

如：

（1）整数集Z中关系≦是反对称的，因为只要a≦b且b<a，就必有a=b。

（2）包含关系是反对称的，因为只要A属于B且B属于A，则必有A=B

（3）N上的整除关系是反对称的，因为只要 m｜n且 n｜m就必有 m=n(注意：整数集 Z上的整除关系不是反对称的）。

2.反对称关系

（1）关系图的特点：如果两个顶点之间有边，一定是一条有向边。

（2）在关系矩阵中，可有若 i≠i，如果rij=1时必有rji=0

3.关于反对称的关系的一些特殊情况

（1）In为N上的恒等关系，它既是对称的、又是反对称的。相等关系也是如此。

例如： S={a,b,c}  S上的关系R={<a,b>,<a,c>,<c,a>}

则R在S上是对称关系，也是反对称关系。

（2）可能有某种关系，既不是对称关系，也不是反对称关系。

例如：S={a,b,c},S上的关系R={<a,b>,<a,c>,<c,a>};则R在S上不是对称关系，也不是反对称关系。

4.（1）Rl，R2为 A上的反对称关系，则经过相对、补、 逆运算后仍能保持其反对称性 。

事实上，在A上是反自反和可传递的，则必是反对称的

  （2）对任 意的 x、y∈A，假设 xRy且 yRx，因为R是可传递的，所以有 xRx，这与已知R是反自反矛盾。由X、Y的任意性，所以R必是反对称的。

5.（1）对于任意一个关系ɑ是反对称关系的充要条件是关系图中任意两点间有弧线时，只能有一条。

  （2）任意一个关系ɑ是对称，又是反对称的充要条件是ɑ是恒等关系，即只是每个结点有自环。

六、传递性

1. 基本概念：R为集合A上的 二元关系，对于 任意a，b，c∈A当<a，b>∈R且<b、c>∈R时，有<a，c>∈ ，称为A上的传递关系，或者说R在A上具有传递性。
2. 全集的子集中，关系和相等关系都是可传递的。实数集合中，关系 ≦、<和 =都是可传递的，几何中平行 关系，相似关系、整除关系均为可传递的。家族中，兄弟关系、姐妹关系是可传递的，但父子关系不是可传递的。

**以教材的一个题目为例：试判定实数集上 “≦”二元关系的传递性。

解：

因为对于Va，b，c∈R当 a≦b且 b≦c时，必有 a≦c，所以实数集上的 “≦”二元关 系具有传递性。

3.传递关系的关系图

如果顶 点X i到Xj有边，Xj到Xk有边，则Xi到Xk有边。

4.

   （1）R1、R2为A上的传递关系，则经过交和逆运算后仍保持传递性。

   （2）任意一个关系ɑ是传递的充要条件是若结 点 a到 b有弧线，b到 c有弧线，则必有 a到c有 (有向)弧线。

   （3）任意一个关系ɑ不是传递的充要条件是其关系图中有从结点 a到 b，有 b到 c的有 向弧线，但没有从结点 a到 c的有向弧线。

5.关于传递关系的一些特殊情况

1. 结点 a有自环，a到 b有有向弧线，关系ɑ仍是传递的。只有序偶 <a，b>的关系ɑ是传递关系的特例，它的关系图中只有一条弧线 (有向)，从 a到 b。
2. 传递性对并运算不一定保持。

设A={1,2,3}  A上的关系R={<1,2>}和S={<2,3>}都是A上的传递关系，可是

却不是A上的传递关系。

七、关于二元关系传递性的判定

由上文二元关系的定义

1.利用真值表判断传递性

列出真值表如下：

真值表的第一种情形是我们熟悉的，从定义直接能判断出来的。比如R1，（a,b)∈R为真，(b,c)∈R为真，(a,c)∈R为真， 则满足传递性。

从真值表判断，第二种情形真值为假，即不满足传递性。比如R4={(a,b),(b,c)}，没有出现有序对 (a,c)，则(a,b)∈R为真，(b,c)∈R为真，(a,c)∈R为假，由真值表知，这是不满足传递性的。

第三种情形和第五种情形看似不传递，但满足传递性的定义。如 R2,(a,b)∈R为真，(b,c)为假，(a,c)为真，由真值表知，这是满足传递性的。再如 R5={(b,c),(a,c)},(a,b)∈R为假，(b,c)∈R为真，(a,c)∈R为真，满足定义，是传递的。

第四种、第六种、第七种情形都是包含一个有序对的，满足传递性，以第四种情形为例，R6={(a,b)}，(a,b)∈R为真，(b,c)∈R为假，(a,c)∈R为假，最后真值为真，故是传递的。

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

1. 根据特殊情形判断

1. 在二元关系中，包含很多组有序对，如果有一组有序对不满足传递的定义，但其他组都满足传递的定义，那这个二元关系仍然不是不传递的。
2. 如果定义中的x，y，z有两个或三个相等，那么它符合传递性的定义。

以R3={(a,a),(b,b),(c,c)}为例，将有序对分为三组考虑：I 有序对(a,a)   II 有序对(b,b)  III 有序对(c,c),三组均满足传递性的定义，故是传递的。

2.关于传递性判断的总结

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

4.例题：设集合 A={1,2，3，4)是 A上的二元关系， R={<1，1>，<1，2>，<1，3>，<2，3>)试判定 R的传递性。

设例中所给的二元关系是以序对集合的形式给出的，由于该二元关系本身不 明显，要实现传递性的判定必须按照定义中的条件依次对 R中的每一序对<a、b>，检查是否存在序对<b、c>∈R、以及 <a、 b>∈R。 

在本题中，对 R中的序对<1，1>，存在<1，2>∈ R，<1，3>∈R、以及<1，2>∈R、

<1，3>∈R、对 R中的序对<1，2>存在<2，3>∈R以及<1，3>∈R；但对 R 中的序对<1，3>，<2，3>由于不存在<3，x>(Vx∈A )，所以有的同学认为 R不是传递这样就错了。因为定义中说若有<b、c>∈R的话<a、c>∈R、那么找不到满足已知条件的所以传递关系。 

八、思考与总结

1.本文主要探讨离散数学中的二元关系。离散数学是研究基于离散空间而不是连续的数学结构的一门学科，在其中二元关系是一个重要的研究对象。选择此课题的原因一部分是因为自己的学习进度，另一部分是因为感觉自己对这方面的知识掌握的比较浅，缺乏系统性的总结和探讨。

2.何为二元关系，它是集合 A，B的笛卡儿积 A×B的子集，是有序对的集合，即

并称为集合 A到集合 B的二元关系，其中包括有序对、图论中的边等。当A=B时称为集合 A上 的二元关系。定义在某一集合上时二元关系具有自反性、反自反性、对称性、反对称性 以及传递性等性质，其在离散数学中有着广泛的应用，例如集合运算和图的遍历等。

实际判定某个二元关系性质时，自反性、反自反性、对称性的判定比较容易，而传递性的判定有时则较困难且易错，结合真值表的方法可以很好的解决这个问题。

3.通过对离散数学中二元关系的探讨，我们可以更深入地理解离散数学的理论基础，并且能够将其应用于实际问题中。同时通过本文的总结和探讨，我对二元关系的理解也更加深刻，掌握了各种性质的判定方法。

4.通过对离散数学中的二元关系的学习和探讨，我得到了以下启示和思考：

（1）抽象思维的重要性：离散数学课程中的二元关系是一个高度抽象的概念，需要学生具备一定的抽象思维能力才能理解和运用。而这种抽象思维能力是在课程学习中逐渐培养和提高的，因此学生需要不断地进行思考和实践。

（2）多样化的应用场景：离散数学中的二元关系具有广泛的应用场景，例如在计算机科学中，它被用来描述数据库中的关系模型，掌握这些知识可以为未来的工作做好准备。

（3）系统化的思维方法：离散数学中的二元关系需要学生学会采用系统化的思维方法，即将问题分解为更小的问题，并考虑它们之间的关系，这种思维方法是在学习中逐渐培养和改善的。

（4）良好的逻辑推理能力：离散数学中包含了很多的证明，需要学生具备良好的逻辑推理能力，以便于理解课程中的定理和算法，同时也需要学会使用逻辑符号和演算规则。

总之，离散数学中的二元关系是一个具有深刻思维和广泛应用的概念，在学习和探讨过程中，可以帮助我们培养抽象思维、系统化思维和逻辑推理能力等多方面的能力。

参考文献

[1]耿素云，屈婉玲，张立昂．离散数学 [M]．清华大学出版社 ．1998． 

[2]倪土健，蔡经球．离散数学 [M].科学出版社．2OO1．

2023-05-01