离散数学基础-课件 第2章 二元关系

02关系的定义及运算关系的性质等价关系与划分偏序关系

二元关系12.1二元关系的定义及运算

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

2定义2.1.1二元关系

3二元关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

4例2.1.1常见关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

5例2.1.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的表示——关系矩阵

6关系的表示——关系矩阵例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

7例2.1.3例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的表示——关系矩阵

8关系的表示——关系矩阵

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

9例2.1.4关系的运算

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

10例2.1.5关系的运算——求逆例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

11定义2.1.2例2.1.6关系的运算——复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

12定义2.1.3例2.1.7关系的运算——复合例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

13例2.1.7（续）逆关系和复合运算的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

在关系复合运算的基础上，可以如下归纳定义关系的幂运算.定理2.1.1例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

14定义2.1.4例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系的幂运算

15关系的幂运算例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

16例2.1.8解例2.1.8关系的幂运算例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

17例2.1.8解（续）关系的幂运算合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

18例2.1.8解（续）2.2关系的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

本节介绍关系常见的5种性质：自反性、反自反性、对称性、反对称性和传递性.

19定义2.2.1关系的性质—自反性和反自反性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

20解例2.2.1关系的性质—对称性和反对称性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

21定义2.2.2关系的性质—自反性和反自反性例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

22解例2.2.2关系的性质—传递性

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

23定义2.2.3解例2.2.3关系的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.定理2.2.1

24关系的性质定理2.2.1证明例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

25关系的性质定理2.2.1证明(续)例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

26关系的性质表2.2.1

关系性质的特征表示形式性质自反性反自反性对称性反对称性传递性集合表达式关系矩阵矩阵是对称矩阵关系图每个顶点都有自环每个顶点都没有自环如果两个顶点之间有边，那么一定是一对方向相反的边（无单边）如果两个顶点之间有边，那么一定只有一条有向边（无双向边）272.3等价关系与划分证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

28定义2.3.1定义2.3.2等价关系与划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

29例2.3.1等价类的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.定理2.3.1证明

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理2.3.130等价类的性质例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

定理2.3.1证明（续）例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

31商集例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

32定义2.3.3划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

33定义2.3.4划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

34解

例2.3.2划分不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

35解例2.3.3划分例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

图2.3.1

三元集的所有划分

36例2.3.3（续）关系闭包例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

37定义2.3.5例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.关系闭包

38闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

39证明命题2.3.1闭包的构造

40例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

证明命题2.3.2闭包的构造

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

41定理2.3.2例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

证明闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

42定理2.3.2证明（续）闭包的构造例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

43注2.3.22.4偏序关系例如，{x∈2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

44定义2.4.1偏序关系例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

45例2.4.1哈斯图利用偏序关系的自反性、反对称性和传递性，可以简化一个偏序关系的关系图，得到偏序集的哈斯图.为了说明哈斯图的画法，需要定义偏序集中元素的覆盖关系.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

46定义2.4.2哈斯图{x∈R

2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性不难证明，空集是唯一的，所以前文用∅表示空集是合理的.两个哈斯图如图2.4.1所示.

47解例2.4.2哈斯图反过来，给定一个哈斯图，我们也能立即得到对应的偏序集.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

48解例2.4.3偏序集的特殊元素例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

49定义2.4.3偏序集的特殊元素例如，{x∈R|x2=1}={1,−1}；N=Z

例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

50解例2.4.4偏序集的界例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

51定义2.4.4偏序集的界基于最小上界和最大下界，我们可以定义一类特殊的偏序集——格.格在程序验证、数据库和编译器设计等领域都有着广泛的应用.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

52定义2.4.5例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

例2.4.5拓扑排序在日常生活中，任务之间往往存在依赖关系，某些任务可能依赖于其他任务的完成，因此我们经常用偏序关系来约束这些任务的完成顺序.然而，尽管这些约束条件对任务施加了偏序关系，任务实际上必须按照某种顺序完成.我们面临的挑战是将偏序关系扩展为全序关系——也就是说，构建一个保持偏序关系所有约束条件，同时使以前无法比较的元素变成可比较的全序关系.为此，先引入相容性的概念.例如，{x∈R|x2=1}={1,−1}；N=Z+.由空集是任何集合的子集的性质不难证明，空集是唯一的，所以前文用∅表示空集是合理的.

一般地，对于给定的偏序，可能存在多个与之相容的全序，这意味着拓扑排序并