离散数学 1 第 6 章：关系的性质——五条性质与判定方法

写于 2026-11-01

这是全课最"表格化"的一章：五个性质，每个都有定义、关系矩阵判据、关系图判据三重表述。背定义本身不难，难在三个反直觉之处——反自反不是自反的否定、对称与反对称可以同时成立、传递性在自环参与时几乎自动满足。把这三处理顺，本章的判断题基本不会错；理顺不了，第 7 章求闭包时会连"要补哪些边"都说不清。

一、自反性与反自反性

设 R 是 A 上的关系。

自反：∀x∈A，∈R。等价说法：I_A ⊆ R。
反自反：∀x∈A，∉R。等价说法：R ∩ I_A = ∅。

判据：自反的关系矩阵主对角线全为 1，关系图每个结点都有自环；反自反则主对角线全为 0，图中一个自环都没有。

关键结论：反自反不是自反的否定。"自反"的否定是"存在某个 x 使 ∉R"，而"反自反"要求"对所有 x 都没有自环"，后者强得多。所以存在大量既不自反也不反自反的关系：

A = {1,2,3}，R = {<1,1>, <1,2>}。有 <1,1>，所以不是反自反；缺 <2,2>、<3,3>，所以也不是自反。两边都不算。

二、对称性与反对称性

对称：若 ∈R，则 ∈R。
反对称：若 ∈R 且 ∈R，则 x = y。

判据：对称的关系矩阵关于主对角线对称（mᵢⱼ = mⱼᵢ），关系图中每条边都有反向边（可画成无向边）。反对称的矩阵在 i≠j 时 mᵢⱼ 与 mⱼᵢ 不能同时为 1，图中不同结点之间至多一条单向边，不能出现一来一回。

第二个反直觉之处：对称与反对称不互斥。I_A 上每对都要求 x=y 才成立，两个条件同时满足；空关系也同时满足两者（前提永远为假，蕴含式恒真）。所以做题时不能说"它是对称的，所以不是反对称的"。

最小例子：A = {1,2}，R = {<1,1>, <2,2>}，矩阵是单位阵——它关于对角线对称，同时不同元素之间一条边都没有，于是也反对称。另外，图中的自环不影响反对称性：自环对应 x=y，正是反对称明确允许的情形，反对称约束的只是不同结点之间。

三、传递性

传递：若 ∈R 且 ∈R，则 ∈R。

矩阵判据：先算布尔积 M_R² = M_R ⊙ M_R，若 M² 中每个为 1 的位置在 M 中也必然为 1（即 M² ≤ M 逐元成立），则 R 传递。
图判据：任意一条长度为 2 的通路（x→y→z），都必须存在从 x 到 z 的直接边。

第三个反直觉之处：传递性只在"中间结点确实存在"时才被触发。若 R 中根本没有以 y 为终点的边，那么关于 y 的条件就是空真，不会带来任何要求。这也是为什么自环常常"白送"传递性：有和，需要，而它本来就在。

举例：A = {1,2,3}，R = {<1,2>, <2,1>, <1,1>, <2,2>}。检查：<1,2>,<2,1> 要求 <1,1> ✓；<2,1>,<1,2> 要求 <2,2> ✓；其余组合凑不出中间结点。所以 R 传递。

手工执行的顺序是：先算 M²，再把结果与原矩阵逐格比对。只要出现一格"M² 为 1 而 M 为 0"，就不传递，而且这个位置恰好告诉你缺哪条边——第 7 章求传递闭包要补的正是这些格子。反过来看，R = {<1,2>, <2,3>} 就不传递，因为缺 <1,3>；补上它之后才传递。这种"缺边—补边"的视角，比背定义更接近闭包算法的实质。

四、五条性质的判定总表

性质	定义	矩阵判据	图判据
自反	∀x，∈R	主对角线全 1	每点有自环
反自反	∀x，∉R	主对角线全 0	无任何自环
对称	xRy ⇒ yRx	矩阵关于主对角线对称	边成对出现
反对称	xRy ∧ yRx ⇒ x=y	i≠j 时 mᵢⱼ·mⱼᵢ = 0	两点间至多一条单向边
传递	xRy ∧ yRz ⇒ xRz	M² ≤ M（逐元）	长度 2 的通路必有捷径边

三种特殊关系的性质分布，值得单独记一行：

关系	自反	反自反	对称	反对称	传递
空关系 ∅	否	是	是	是	是
恒等关系 I_A	是	否	是	是	是
全域关系 E_A	是	否	是	否（n≥2）	是

注意空关系在"反自反、对称、反对称、传递"四项上全为是，这是判断题里最常见的陷阱选项。

五、一道综合判定

A = {1,2,3,4}，R = {<1,1>, <1,2>, <2,1>, <2,2>, <3,4>}，逐条过：

自反：缺 <3,3>、<4,4>，否。
反自反：有 <1,1>、<2,2>，否。
对称：<1,2> 与 <2,1> 配齐，但 <3,4> 的逆向 <4,3> 不在，否。
反对称：<1,2> 与 <2,1> 同时存在而 1≠2，直接否。
传递：<1,2>,<2,1> 要求 <1,1> ✓；<2,1>,<1,2> 要求 <2,2> ✓；<1,1> 与 <1,2> 要求 <1,2> ✓；其余组合无中间结点可接。是。

结论：这个关系只满足传递性。五条性质互不蕴含，一条成立推不出另一条，这是本章最该建立的认识。

顺带记一条容易考的结论：两个等价关系（自反+对称+传递）的交仍是等价关系，并则不一定——并会破坏传递性。传递关系同理，交保传递、并不保。检验这类"运算是否保性质"的题，用最小反例最快：A = {1,2,3}，R₁ = {<1,2>}∪I_A、R₂ = {<2,3>}∪I_A 各自都传递，并起来却缺 <1,3>，于是不传递。

六、判定与证明的写法

证明成立，按定义展开：

证自反：任取 x∈A，由……得 ∈R。
证对称：设 ∈R，由定义得 ∈R。
证反对称：设 ∈R 且 ∈R，推出 x=y。
证传递：设 ∈R、∈R，推出 ∈R。

证明不成立，举一个反例就够，而且反例越"小"越好：用两个元素反掉对称，比用四个元素更有说服力，说明你抓住了性质的触发条件。答题时把反例写成集合形式，并把"为什么它违反定义"点明一句，比只写"不成立"得分高得多。

易错点

反自反 ≠ 不自反。既不自反也不反自反的关系大量存在，别默认非此即彼。
对称与反对称可以同时成立（I_A、空关系），二者不是对立面。
反对称不是"没有对称的边"，而是"不能有来回两条边"；单向边完全允许。
判传递只看长度为 2 的通路，但要把所有有序对组合都试一遍，尤其别漏自环参与的组合。
传递性用矩阵判要算布尔积 M²，不是看矩阵长得对称不对称。

这一章在整门课里的位置

本章直接用第 5 章的关系矩阵与关系图作判据，是那三种表示的第一次实战。第 7 章的三种闭包，本质就是"缺哪条性质就补哪些边"：补自环得自反闭包，补逆向边得对称闭包，补捷径边得传递闭包。第 8 章则把"自反 + 对称 + 传递"打包成等价关系，把"自反 + 反对称 + 传递"打包成偏序关系。

本文是《离散数学 1：数理逻辑与集合论》第 6 章的知识点摘要。完整板书与例题见课程页；上一章集合与关系，下一章关系的运算。