离散数学第二章关系的章节总结3000字.docxVIP

第二章关系知识体系总结

一、关系基础概念

1.1基本定义

笛卡尔积：设A,B为集合，A×B={(a,b)|a∈A∧b∈B}

二元关系：R?A×B，若|A|=m,|B|=n，则不同关系数量为2^{m×n}

特殊关系：

空关系?：不含任何有序对

全域关系A×B：包含所有可能有序对

恒等关系I_A={(a,a)|a∈A}

1.2表示方法

表示形式

描述

示例

集合表达式

直接列出有序对

R={(1,2),(2,3)}

关系矩阵

M_R=[m_ij],其中m_ij=1当且仅当(a_i,b_j)∈R

A={1,2},B={a,b},M_R=[[0,1],[1,0]]

关系图

顶点表示元素，有向边表示关系

A={1,2,3},R={(1,2),(2,3)}图示为1→2→3

二、关系性质分析

2.1五大基本性质

性质

定义

判定条件

自反性

?a∈A,(a,a)∈R

关系矩阵主对角线全1

反自反性

?a∈A,(a,a)?R

主对角线全0

对称性

若(a,b)∈R则(b,a)∈R

M_R=M_R^T

反对称性

若(a,b)∈R且a≠b，则(b,a)?R

M_R∧M_R^T≤I

传递性

若(a,b),(b,c)∈R则(a,c)∈R

M_R^2≤M_R

2.2典型关系类型

类型

性质组合

示例

等价关系

自反+对称+传递

整数集合上的模3同余

偏序关系

自反+反对称+传递

集合包含关系?

拟序关系

反自反+传递

实数上的严格小于

三、关系运算体系

3.1基本运算

逆关系：R^{-1}={(b,a)|(a,b)∈R}

矩阵转置：M_{R^{-1}}=M_R^T

合成运算：R°S={(a,c)|?b,(a,b)∈R∧(b,c)∈S}

矩阵乘法：M_{R°S}=M_R⊙M_S（布尔积）

3.2闭包运算

闭包类型

定义

构造方法

自反闭包?r(R)

包含R的最小自反关系

r(R)=R∪I_A

对称闭包?s(R)

包含R的最小对称关系

s(R)=R∪R^{-1}

传递闭包?t(R)

包含R的最小传递关系

t(R)=R∪R^2∪R^3∪...=?_{n=1}^∞R^n

沃舍尔算法（Warshall）求传递闭包：

通过三重循环迭代更新路径可达性

时间复杂度：O(n3)

四、特殊关系专题

4.1等价关系与划分

等价类：[a]_R={x|x∈A∧(a,x)∈R}

商集：A/R={[a]_R|a∈A}

划分定理：集合A的每个划分唯一确定一个等价关系

4.2偏序关系

哈斯图绘制规则：

移去自反环

消除传递边

排列元素使箭头朝上

重要概念：

极大元/极小元

最大元/最小元

上界/下界

格（Lattice）：任意两元素都有最小上界和最大下界

4.3相容关系

性质：自反+对称

应用：数据库设计中的无损连接分解

五、典型应用场景

5.1计算机科学应用

数据库关系模型：关系代数运算（选择、投影、连接）

图论基础：邻接矩阵表示图结构

自动机理论：状态转移关系描述

5.2离散结构应用

等价类用于数据聚类分析

偏序关系描述任务调度依赖

传递闭包计算路径可达性

六、常见问题解析

6.1易混淆点对比

概念对比

关键区别

对称vs反对称

对称性要求双向关系，反对称限制非对称双向存在

偏序vs全序

全序要求任意两元素可比，偏序允许不可比元素存在

等价类vs划分块

等价类是划分块的具体表现形式

6.2典型证明方法

数学归纳法：证明传递闭包性质

反证法：验证偏序关系的反对称性

构造法：建立等价关系与划分的对应

七、知识结构图

关系基础

├─定义与表示

├─基本性质

│├─自反性

│├─对称性

│└─传递性

├─运算体系

│├─逆关系

│├─合成关系

│└─闭包运算

└─特殊关系

├─等价关系

├─偏序关系

└─相容关系

本章重点：

①掌握关系性质的矩阵判定方法

②熟练进行闭包运算（特别是传递闭包的沃舍尔算法）

③理解等价关系与划分的对应原理

④能绘制和分析哈斯图

学习建议：通过具体实例（如A={1,2,3}上的不同关系）进行矩阵运算与图形化验证，加深对抽象概念的理解。