离散数学 课件 3.5 关系的性质

CHAPTER03·集合SETS3.5关系的性质PROPERTIESOFRELATIONS课程大纲CONTENTS01自反性与反自反性定义、示例与判断方法02对称性与反对称性定义、示例与判断方法03传递性定义、示例与判断方法04综合应用综合例题解析，巩固知识体系学习背景与意义提出问题❓理论探索：

给定一个集合A，其上存在众多二元关系。在这些复杂的关系中，我们能够发现哪些既有趣又具备理论与应用价值的性质？💡实际应用：

在社交网络好友推荐、用户行为分析等包含海量数据的图结构关系中，如何利用数学工具挖掘并定义“朋友关系”、“关注关系”背后有价值的特征？学习目标🎯核心掌握：

深入理解并熟练判定关系的五个基本性质：自反性、反自反性、对称性、反对称性、传递性。能够从定义、关系矩阵及关系图三个维度进行识别。🧩承上启下：

理解这些性质是后续学习关系的闭包计算、等价关系与划分、偏序关系与哈斯图等进阶内容的重要基石。定义3.21：自反性(Reflexive)▍定义原文设R为定义在集合X上的二元关系，如果对于每个x∈X，有xRx，则称二元关系R是自反的。逻辑等价式：R在X上自反⇔∀x(x∈X→<x,x>∈R)01.前提条件自反性讨论的对象必须是“一个集合”上的关系。若关系R是定义在两个不同集合上的笛卡尔积，则无自反性可言。02.核心要求“每一个”是关键词。集合X中的任何一个元素x，都必须满足xRx。只要有一个元素不满足，则关系R不具备自反性。自反性示例同姓氏关系在所有人的姓名集合上，任何人都与自己同姓，即：

<张三,张三>∈R集合包含关系集合论中的基本关系。对于任意集合A，其元素都包含于自身，即：

A⊆A恒成立整数整除关系在整数域中，任意整数都可以被自身整除。对于任意整数x：

x|x成立实数小于等于关系(≤)实数集上的全序关系，任意实数都不会大于其本身。对于任意实数x：

x≤x恒成立三角形全等关系(≅)几何学中的等价关系。任何三角形的形状、大小都与自身完全重合，即：

任何三角形都与自身全等定义3.22：反自反性(Antireflexive)定义原文设R为定义在集合X上的二元关系，如果对于每个x∈X，都有xRx不成立（即有序偶<x,x>∉R），则称该二元关系R是反自反的。逻辑等价式R在X上反自反⇔∀x(x∈X→<x,x>∉R)关键要点•适用范围：仅适用于定义在同一个集合X上的二元关系，非两个不同集合间的关系。•核心要求：集合中的每一个元素，都绝对不能与自身构成序偶并出现在关系R中。只要有一个元素违反，R就不是反自反的。反自反性示例父子关系任何人都不可能是自己的父亲，即<张三,张三>∉R。真包含关系对于任意集合A，

A⊂A不成立。实数小于关系对于任意实数x，

x<x不成立。实数大于关系对于任意实数x，

x>x不成立。例题3.25：关系性质判断(自反/反自反)题目描述设集合A={1,2,3}，并在A上定义了以下三种二元关系：•关系R：{<1,1>,<1,2>,<2,2>,<3,3>}•关系S：{<1,2>,<2,3>,<3,1>}•关系T：{<1,1>,<1,2>,<3,3>}❓思考：试讨论关系R,S,T的自反性与反自反性。判断方法总结基于序偶集合检查关系集合是否完全包含/完全排除恒等关系IA中的所有元素。基于关系图(Graph)检查图中每一个结点是否都有自环(自反)，或所有结点都没有自环(反自反)。基于关系矩阵(Matrix)检查矩阵主对角线上的元素是否全为1(自反)，或全为0(反自反)。例题3.25：解法与结论判定结论关系R：包含恒等关系IA，满足“每个元素都与自身相关”，故自反。关系S：与恒等关系IA无任何交集，满足“所有元素都不与自身相关”，故反自反。关系T：仅包含部分自环元素（如<1,1>、<3,3>），但缺少<2,2>。因此既非自反，也非反自反。深入思考：边界情况Q:是否存在“既是自反，又是反自反”的二元关系？A:存在。即：空集合∅上的空关系∅。原理解释：根据数理逻辑中的“善意推定”原则，若蕴含式的前提条件无法满足（即集合为空，没有任何元素x能满足x∈∅），则整个蕴含式逻辑为真。因此，空集合上的空关系同时满足自反性和反自反性的定义。定义3.23：对称性(Symmetric)定义原文设R为定义在集合X上的二元关系，如果对于每个x,y∈X，若存在xRy，必有yRx，则称R是对称的。逻辑表达式R在X上对称⇔∀x∀y(x∈X∧y∈X∧xRy→yRx)理解要点当x≠y时，序偶<x,y>和<y,x>必须成对出现在R中。对称性关系的有向图表示

若存在从x到y的边，则必存在从y到x的边对称性示例同姓关系若<张红,张亮>∈R，则<张亮,张红>∈R。朋友关系若<Alice,Bob>是朋友，则<Bob,Alice>也是朋友。同余关系若5和8模3同余，则8和5也模3同余。三角形相似关系若三角形A相似于B，则B也相似于A。这在几何学中是非常基础且重要的对称性质。邻居关系若A是B的邻居，则B也是A的邻居。这是现实生活中典型的对称二元关系。定义3.24：反对称性(Antisymmetric)定义原文设R为定义在集合X上的二元关系，如果对于每个x,y∈X，若存在xRy和yRx时，必有x=y，则称R是反对称的。逻辑表达式R在X上反对称⇔∀x∀y(x∈X∧y∈X∧xRy∧yRx→x=y)理解要点当x≠y时，序偶<x,y>和<y,x>不能同时出现在关系R中。这意味着在关系图中，两个不同的顶点之间不能存在双向的边。反对称性示例父子关系若<张新明,张磊>是父子关系，则<张磊,张新明>一定不是。体现了关系在逆序下不成立的特点。集合包含关系若A⊆B且B⊆A，则必有A=B。两个集合互为子集时，仅当二者完全相等时才成立。整除关系若a|b且b|a（a,b为正整数），则必有a=b。正整数间互相整除，说明二者数值完全一致。实数小于等于关系若x≤y且y≤x，则必有x=y。这是实数集上最典型的反对称关系之一，也是数学分析的基础。例题3.26：关系性质判断(对称/反对称)题目条件：设集合A={1,2,3,4}，并在A上定义了如下四个二元关系：R={<1,1>,<1,3>,<3,1>,<4,4>}|S={<1,1>,<1,3>,<1,4>,<2,4>}|T={<1,1>,<1,2>,<1,3>,<3,1>,<1,4>}|V=Iₐ={<1,1>,<2,2>,<3,3>,<4,4>}关系R{<1,1>,<1,3>,<3,1>,<4,4>}💡分析：

有序对<1,3>与<3,1>成对出现，且不存在x≠y时<x,y>和<y,x>只出现其一的情况。关系S{<1,1>,<1,3>,<1,4>,<2,4>}💡分析：

存在如<1,3>，但无<3,1>;有<2,4>，但无<4,2>，且无任何x≠y使得<x,y>和<y,x>同时存在。关系T{<1,1>,<1,2>,<1,3>,<3,1>,<1,4>}💡分析：

既有<1,3>与<3,1>成对出现，又有<1,2>存在但<2,1>不存在。关系V(恒等关系Iₐ){<1,1>,<2,2>,<3,3>,<4,4>}💡分析：

仅包含所有<x,x>形式的有序对，没有x≠y的情况，故不存在对称性或反对称性的反例。例题3.26：解法与结论R对称关系序偶<1,3>和<3,1>成对出现，满足对称性定义，故关系R是对称的。S反对称关系不存在满足x≠y的成对序偶<x,y>和<y,x>，符合反对称定义，故关系S是反对称的。T非对称·非反对称同时存在对称的序偶对(<1,3>与<3,1>)和不对称的序偶(<1,2>无对应<2,1>)，故两者都不是。V对称且反对称集合中仅包含自环序偶(如<1,1>)，不破坏任何一条规则，因此兼具对称性和反对称性。💡结论：对称性与反对称性并非互斥关系。关系可分为四类：对称、反对称、既是对称又是反对称、既非对称也非反对称。定义3.25：传递性(Transitive)定义原文设R为定义在集合X上的二元关系，如果对于每个x,y,z∈X，若存在xRy和yRz，则必有xRz，称R是传递的。逻辑表达式R在X上传递⇔∀x∀y∀z(x∈X∧y∈X∧z∈X∧xRy∧yRz→xRz)理解要点若存在“中间桥梁”y，则首尾两端的元素x和z必须直接相连。传递性示例(正/反)具有传递性的关系•同姓关系：A与B同姓，B与C同姓，则A与C同姓。•集合包含关系：A⊆B且B⊆C，则A⊆C。•祖先关系：A是B的祖先，B是C的祖先，则A是C的祖先。•实数大小关系：≤,≥,<,>,=等基本的大小比较关系均满足传递性。不具有传递性的关系•朋友关系：A是B的朋友，B是C的朋友，A不一定是C的朋友，朋友关系不具备传递性。•父子关系：A是B的父亲，B是C的父亲，则A是C的祖父，而不是父亲。这表明父子关系不具有传递性。例题3.27：关系性质判断(传递性)关系R={<1,1>,<1,2>,<2,3>,<1,3>}分析：检查所有可能的传递条件：

1.存在<1,2>和<2,3>，且<1,3>∈R

2.存在<1,1>和<1,2>，且<1,2>∈R；存在<1,1>和<1,3>，且<1,3>∈R。

其他有序对均不构成传递前提。➜结论：R是传递的。关系S={<1,2>}分析：关系S中只有一个有序对，不存在形如<a,b>和<b,c>的两个有序对。

根据“善意的推定”（vacuoustruth），在前提条件不成立时，蕴含式的真值为真。➜结论：S是传递的。关系T={<1,1>,<1,2>,<2,3>}分析：存在有序对<1,2>和<2,3>，构成了传递条件的前提。

根据传递性的定义，必须有<1,3>属于关系T才能满足传递。

但<1,3>∉T，不满足传递性要求。➜结论：T不是传递的。关系V={<1,2>,<2,3>,<1,3>,<2,1>}分析：存在有序对<2,1>和<1,2>，构成传递条件的前提。

根据定义，必须有<2,2>∈V才能满足传递性。

但<2,2>∉V，故不满足传递性要求。➜结论：V不是传递的。例题3.27：解法与结论R传递性分析序偶<1,2>和<2,3>可推出<1,3>，且<1,3>包含在关系R中，满足传递定义。✅结论：传递(Transitive)S传递性分析不存在任何满足xRy且yRz的序偶组合。根据逻辑学中的“善意推定”原则，视为满足传递性。✅结论：传递(Transitive)T传递性分析序偶<1,2>和<2,3>应推出<1,3>，但<1,3>并不包含在关系T中，破坏了传递性定义。❌结论：不传递(Non-transitive)V传递性分析序偶<1,2>和<2,1>应推出<1,1>，但<1,1>并不包含在关系V中，破坏了传递性定义。❌结论：不传递(Non-transitive)传递性判断方法总结序偶集合法逐一检查集合中所有可能的传递组合(xRy,yRz)，验证最终结果(xRz)是否同样包含在序偶集合中。关系图法检查图中是否存在长度为2的“通路”x→y→z。若存在这样的通路，则必须在图中补充一条直接边x→z。关系矩阵法对于矩阵M中的任意元素，如果M[i][j]=1且M[j][k]=1，则必须同时满足M[i][k]=1，否则不满足传递性。特别注意：传递性的判断通常比自反性、对称性更复杂，很难直接从关系图或矩阵中快速“看”出来，最稳妥的方法是耐心地逐一验证所有潜在的传递组合。综合例题3.28：根据关系图判断性质R全关系(Universal)具有以下性质：自反性

对称性

传递性S特定关系具有以下性质：反自反性

反对称性T特定关系具有以下性质：对称性M特定关系具有以下性质：自反性

反对称性

传递性N空关系(Empty)具有以下性质：反自反性·对称性

反对称性·传递性综合例题3.29：分析关系性质题目：给定集合A={1,2,3,4}上的二元关系R={<1,1>,<1,3>