离散数学知识点总结（10）“关系” 知识的总结 ＜1＞：关系的基础概念 —— 有序 n 元组，集合的笛卡尔积，集合的关系（二元关系）的定义，关系的集合运算， 关系的基本性质_离散数学常考知识点

有序 n 元组和集合的笛卡尔积

序偶关系

有序二元组

• 有两个对象 $x,y$ 组成的序列称为有序二元组，也称之为序偶，记作 $<x,y>$
• 序偶与集合不同，次序非常重要

序偶相等

• 设 $<x,y>,<u,v>$ 是两个序偶，如果 $x=u且y=v$ 那么这两个序偶被认为是相等的，记作 $<x,y>=<u,v>$

有序三元组

• 有序三元组是一个序偶，其第一个元素也是个序偶
  
  • 因为第一个元素不是个序偶

有序n元组

• 有序n元组是一个序偶，其第一个元素本身是一个有序的 n-1 元组，记作 $<<x_1,x_2,...,x_{n-1}>,x_n>$，简记为 $<x_1,x_2,...,x_{n-1},x_n>$

有序 n 元组相等

集合的笛卡尔积

• 设集合 $A,B$ 由 $A$ 的元素为第一元素，$B$ 的元素为第二元素组成的全部序偶的集合，称为 $A$ 和 $B$ 的笛卡尔积，记作 $A\times B$

A × B = { < x , y > ∣ x ∈ A ∧ y ∈ B } A×B=\{<x,y>|x\in A \wedge y \in B\} A×B={<x,y>∣x∈A∧y∈B}

• 集合的笛卡尔积不满足交换律
• 集合的笛卡尔积也不满足结合律

集合笛卡尔积的性质

• 笛卡尔积后的元素个数
• 笛卡尔积对空集
• 笛卡尔积对 $\cap ,\cup$ 满足分配律
• 笛卡尔积对 $\subseteq$ 的性质
• 多个集合的笛卡尔积的符号描述

集合的二元关系及其表示方法

相关

• 我们可以认为，两个集合的关系是两个集合笛卡尔积的一个子集。或者说，两个集合的笛卡尔积代表了这两个集合之间可能发生的所有关系（即组合）
  
  

关系的定义

• 关系可以看做是 序偶的集合
  
  

关系的定义域和值域

• 定义域就是关系集合 $R$ 中的所有的第一元素 $x$ 组成的集合
• 值域就是 关系集合 $R$ 中所有的 第二元素 $y$ 组成的集合
  
  

关系的表示方法

枚举法

谓词公式法

有向图法

- 第一个图表示的是在两个集合上的关系：在 $A,B$ 上的关系 $R_1$
- 第二种图表示的是一个集合和自身的关系：$A,A$ 的关系，$R_2$

矩阵法

特殊的关系

空关系 $\varnothing$

全域关系（完全关系）

• 任意节点之间都有成对出现的边
• 每个节点都有指向自己的环
  

恒等关系

关系的基本运算

• 由于关系的本质还是集合，因此对于集合的基本运算 $\cap ,\cup ,\sim ,\oplus ,-$ 也同样适用。
  

关系的性质

• 自反性
• 反自反性
• 对称性
• 反对称性
• 传递性

Note： 这里涉及到的所有的关系，都是某个集合和自身的关系，即集合 $A$，关系 $R\subseteq A\times A$

自反性

• 有向图的每个节点都有指向自己的环
• 矩阵的主对角线值都为 1
  
  
  

反自反性

• 有向图的每个节点都没有指向自己的环
• 矩阵的主对角线值都为 0
• 一个关系，不是 自反的，也不一定就是 反自反的
  
  
  • 图中的 $R_6,R_7$ 既不是自反关系，也不是反自反关系

对称性

• 有向图的不同节点之间 只要有边，就是方向相反的两条边
• 矩阵特点：矩阵关于主对角线对称
• 特别注意：恒等关系（主对角线全为1）、空关系（矩阵全为0） 都是 对称关系
  
  
  • 图中 $R_4,R_8$ 分别是 恒等关系 和 空关系，他们都是对称关系

反对称性

• 有向图的不同节点之间 只要有边，最多只有一条单方向的边
• 矩阵特点：矩阵关于主对角线对称的位置，最多只有一个 1
• 对称关系和反对称关系不是完全对立的，有些对称关系，也同样是反对称关系

• 反对称或者对称的概念是对所有节点来说的，比如下图中的 $R_7$ 他是反对称的，虽然他在 1,2 节点的关系是对称的；
• 如果我们要说一个关系是对称的，就需要它里面所有的出现的边都是对称的；而只要找到一个反例，他就是反对称的了
• $R_4,R_8$ 他们既是对称的，也是反对称的
  

传递性

• 通过有向图和矩阵不容易识别是否具有传递性，要通过传递性的定义来检查。
  
  
• $R_1$ 中，$xRy$ 为假，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为假，因此整个谓词公式为真，因此满足传递性。所以我们可以得到结论，独立无环的节点不影响传递性
• $R_2$ 中，图中存在 $xRx$ 因此 $xRy$ 为假，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为假，因此依然满足传递性，所以我们得到另一个结论 独立有环的节点不影响传递性
• $R_3$ 中，图中存在 $xRx$ ， $xRy$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为假，依然满足传递性。
• $R_4$ 中，图中存在 $yRx$ 也有 $xRx$ （可以把 $yRx$ 和 $xRx$ 看做是 $xRy,yRz$ 的特殊情况），即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，而确实后件也确实为真，因为 $xRx$ 确实存在，所以 $R_4$ 满足传递性
• $R_5$ 中，图中存在 $xRy$ ， 不存在 $yRz$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为假，依然满足传递性。
• $R_6$ 中，图中存在 $xRy$ ， $yRx$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，但不存在后件 $xRx$ 因此不满足传递性。
• $R_7$ 中，图中存在 $xRy$ ， $yRx$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，同时也存在后件为真 $xRx$ 因此满足传递性。
• $R_8$ 中，图中存在 $xRy$ ， $xRz$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为假，因此满足传递性。
• $R_9$ 中，图中存在 $xRy$ ， $yRz$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，但不存在后件 $xRz$ 因此不满足传递性。
• $R_{10}$ 中，图中存在 $xRy$ ， $yRx$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，也存在后件 $xRz$ 因此满足传递性。
• $R_{11}$ 中，图中存在 $xRy$ ， $yRx$，即 $\forall x\forall y\forall z((x\in A\wedge y\in A\wedge z\in A\wedge xRy\wedge yRz)\to xRz)$ 中的前件为真，但后件为 $zRx$ 因此后件为假，不满足传递性。
• 此外，我们还可以推导出 空关系 和 恒等关系 以及 完全关系 也是满足传递性的
  • 因为空关系就是三个独立的点，使得传递性的前件为假
  • 恒等关系就是三个独立的成环的点，也使得传递性的前件为假
  • 完全关系就是所有点之间的线都是双向的并且有自己成环，因此他的传递性关系判断的前件为真，后件也为真