6.二元关系

1.二元关系

1. 有序对(序偶)：由两个元素 $x$ 和 $y$ 按照一定顺序排列而成的二元组，记作 $< x, y>$。

2. 笛卡尔积：设A, B 为集合，用$A$中元素为第一元素，$B$中元素为第二元素构成的有序对，所有这样的有序对组成的集合，称作 A 和$B$的笛卡尔积，记作 $A \times B$。
   符号化表示为：$A \times B=\{< x, y> \mid x \in A \land y \in B\}$
   若 $|A|=m,|B|=n$，则 $|A \times B|=mn$。

   • 例1：$A=\{a, b\},\ B=\{0,1,2\}$，求 $A \times B,\ B \times A$
     解：
     $A \times B=\{ < a,0> ,< a,1> ,< a,2> ,< b,0> ,< b,1> ,< b,2> \}$
     $B \times A=\{ < 0,a> ,< 0,b> ,< 1,a> ,< 1,b> ,< 2,a> ,< 2,b> \}$
     $|A|$代表集合$A$中元素的个数。

笛卡尔积运算的性质

1. $A \times \emptyset=\emptyset,\ \emptyset \times A=\emptyset$
2. 笛卡尔积运算不满足交换律：$A \times B \neq B \times A$（当 $A \neq\emptyset \land B \neq\emptyset \land A \neq B$ 时）
3. 笛卡尔积运算不满足结合律：$(A \times B) \times C \neq A \times(B \times C)$（当$A\neq\emptyset\land B\neq\emptyset\land C\neq\emptyset$时）
4. 笛卡尔积对并、交运算满足分配律：
   $A \times (B\cup C)=(A \times B)\cup (A \times C)$
   $(B \cup C) \times A=(B \times A) \cup(C \times A)$
   $A \times (B\cap C)=(A \times B)\cap (A \times C)$
   $(B\cap C)\times A=(B\times A)\cap (C\times A)$

二元关系

1. 如果一个集合满足以下条件之一：
   ① 集合非空，且它的元素都是有序对
   ② 集合是空集
   则称该集合为一个二元关系，记作 $R$。
   对于二元关系 $R$，如果 $< x, y> \in R$ 则记作 $xRy$。

2. 设 $A,B$ 为集合，$A \times B$ 的任何子集所定义的二元关系称作从 A 到 B 的二元关系；
   特别当 $A=B$ 时称作 A 上的二元关系。

3. 若 $|A|=n$，那么 $|A \times A|=n^2$。$A \times A$ 的子集就有 $2^{n^2}$ 个，
   每一个子集代表一个 $A$ 上的二元关系，因此 $A$ 上有 $\boldsymbol{2^{n^2}}$ 个不同的二元关系。

   • 例1：设集合 $X=\{1,2,3\}$，设关系 $R$ 为 $X$ 上的小于关系，则 $R=\{< 1,2>,< 1,3>,< 2,3>\}$
     解：

     $$\begin{align*} X\times X&=\{ < x,y> \mid x\in X\land y\in X\} \\ &=\{ < 1,1> ,< 1,2> ,< 1,3> ,< 2,1> ,< 2,2> ,< 2,3> ,< 3,1> ,< 3,2> ,< 3,3> \} \end{align*}$$

     取其中 $x,y$ 满足 $x<y$ 的有序对，得 $< 1,2> ,< 1,3> ,< 2,3>$。

   • 例2：设 $A$ 为集合，且 $|A|=3$，则 $A$ 上最多可定义 512 个不同的二元关系。
     解：
     $|A|=n$，$|A\times A|=n^2$，子集数目 $2^{n^2}$。
     代入 $n=3$：$|A\times A|=9,\ 2^{9}=512$。

A上的特殊关系

• 空关系：空集 $\emptyset$

• 全域关系 $E_A$：$E_{A}=\{<x, y>\mid x \in A \land y \in A\}=A \times A$
  例：$A=\{1,2,3\}$
  则：$E_{A}=\{ < 1,1> ,< 1,2> ,< 1,3> ,< 2,1> ,< 2,2> ,< 2,3> ,< 3,1> ,< 3,2> ,< 3,3> \}$

• 恒等关系 $I_A$：$I_{A}=\{<x, x>\mid x \in A\}$
  例：$A=\{1,2,3\},\ I_{A}=\{< 1,1> ,< 2,2> ,< 3,3> \}$

关系的表现形式

1. 集合表达式
   例：$A=\{1,2,3,4\}$
   $R=\{ < 1,1> ,< 1,2> ,< 2,3> ,< 2,4> ,< 4, 2> \}$

2. 关系矩阵

   $$M_{R}=\begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}$$

3. 关系图 - 例：已知集合 $A=\{a, b, c\}$ 上二元关系 $R$ 的关系矩阵 $M_R=\begin{bmatrix}0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0\end{bmatrix}$，$R=\{< a, b>,< b, a>,< b, b>,< c, a>\}$

---

2.关系的运算

• 设 $R$ 是二元关系：

  1. 定义域：$R$ 中所有有序对的第一元素构成的集合，记作 $\mathrm{dom}R$。

  2. 值域：$R$ 中所有有序对的第二元素构成的集合，记作 $\mathrm{ran}R$。

  3. 域：$R$ 的定义域和值域的并集，记作 $\mathrm{fld}R$。
     形式化：$\mathrm{fld}R=\mathrm{dom}R \cup \mathrm{ran}R$。
     例：$R=\{< 1,2>,< 1,3>,< 2,4>,< 4,3>\}$
     $\mathrm{dom}R =\{1,2,4\}$
     $\mathrm{ran} R=\{2,3,4\}$
     $\mathrm{fld}R =\{1,2,3,4\}$

  4. 逆关系：$R$ 的逆，记作 $R^{-1}$
     $R^{-1}=\{ <y,x> \mid< x,y> \in R\}$ 逆关系：把有序对前后两个元素互换。

  5. 右复合：设 $F,G$ 为二元关系，$G$ 对 $F$ 的右复合记作 $F \circ G$。
     $F\circ G=\{ < x,y> \mid \exists t(< x,t> \in F\land < t,y> \in G)\}$
     例：设 $F=\{< 3,3>,< 6,2>\},\ G=\{< 2,3>\}$
     $F^{-1}=\{ < 3,3> ,< 2,6> \}$
     $F \circ G=\{< 6,3>\}$
     $G \circ F=\{< 2,3>\}$

---

3.关系的性质

• 设 $A=\{1,2,3\}$

  1. 自反
     $R 在 A 上自反 \Leftrightarrow \forall x(x \in A \to< x, x> \in R)$
     例：$R=\{ < 1,1> ,< 2,2> ,< 3,3> \}$

  2. 反自反
     $R 在 A 上反自反 \Leftrightarrow \forall x(x \in A \to< x, x> \notin R)$

  3. 对称
     $R 在 A 上对称 \Leftrightarrow \forall x \forall y(x, y \in A \land< x, y> \in R \to< y, x> \in R)$
     例：$R=\{< 1,2>,< 2,1>\}$

  4. 反对称
     $A 上反对称 \Leftrightarrow \forall x \forall y(x, y \in A \land< x, y> \in R \land< y, x> \in R \to x=y)$
     例：$R=\{< 1,3>,< 2,2>,< 3,3>\}$

  5. 传递
     $A 上传递 \Leftrightarrow \forall x \forall y \forall z(x, y, z \in A \land< x, y> \in R \land< y, z> \in R \to< x, z> \in R)$
     例：$R=\{< 1,2>,< 2,3>,< 1,3>\}$

  	自反性	反自反性	对称性	反对称性	传递性
  集合表达式	$I_A \subseteq R$	$R\cap I_A = \emptyset$	$R= R^{-1}$	$R\cap R^{-1} \subseteq I_A$	$R\circ R\subseteq R$
  关系矩阵	主对角线元素全是1	主对角线元素全是0	矩阵是对称矩阵	若 $r_{ij}=1$ 且 $i\neq j$ 则 $r_{ji}=0$	对 $M_R$ 中1所在的位置，$M_R\circ M_R$ 相应位置都是1
  关系图	每个顶点都有环	每个顶点都没有环	两点有边必是一对反向边，无单边	两点之间若有边，只能是单向有向边	若$x_i\to x_j$有边，$x_j\to x_k$有边，则$x_i\to x_k$也必须有边

  • 例1：给定 $A=\{1,2,3,4\}$，A上关系
    $R=\{< 1,3>,< 1,4>,< 2,3>,< 2,4>,< 3,4>\}$
    
    $$R \cap I_{A}=\emptyset \quad(\text{反自反性})$$
    $$R \cap R^{-1} \subseteq I_{A} \quad(\text{反对称性})$$
    $$R \circ R \subseteq R \quad(\text{传递性})$$

• 例2：设集合A为整数集，A上小于关系：
  $A=\{1,2,3\},$
  $E_A = \{⟨1,1⟩, ⟨1,2⟩, ⟨1,3⟩, ⟨2,1⟩, ⟨2,2⟩, ⟨2,3⟩, ⟨3,1⟩, ⟨3,2⟩, ⟨3,3⟩\}$，
  $R= \{⟨1,2⟩, ⟨1,3⟩, ⟨2,3⟩\}$

  $$R \cap I_{A}=\emptyset \quad(\text{反自反性})$$
  $$R \cap R^{-1} \subseteq I_{A} \quad(\text{反对称性})$$
  $$R \circ R \subseteq R \quad(\text{传递性})$$

• 例3：设 $S=\{1,2,3\}$ 上关系$R$的关系图：

  $$每个顶点都有环（自反性），无单向边（对称性）。$$

• 例4：集合 $A=\{1,2,3\}$ 上关系R的关系矩阵

  $$M_{R}=\begin{bmatrix}1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1\end{bmatrix}$$

---

4.关系的闭包运算

• 设 $R$ 是非空集合 $A$ 上的关系，$R$ 的自反(对称或传递)闭包是 $A$ 上的关系 $R'$，使 $R'$ 满足以下条件：

  1. $R'$ 是自反的(对称的或传递的)
  2. $R \subseteq R'$
  3. 对 $A$ 上任何包含 $R$ 的自反(对称或传递)关系 $R''$，有 $R' \subseteq R''$

• 记法：

  1. 自反闭包：$r(R)$
  2. 对称闭包：$s(R)$
  3. 传递闭包：$t(R)$

• 例：给定 $A=\{1,2,3,4\}$ 和 A 上的关系 $R= \{⟨1,3⟩, ⟨1,4⟩, ⟨2,3⟩, ⟨2,4⟩, ⟨3,4⟩\}$
  

  $$r(R)=\{< 1,1> ,< 2, 2> ,< 3,3> ,< 4,4> ,< 1,3> ,< 1,4> ,< 2,3> ,< 2,4> ,< 3,4> \}$$

  说明：每个顶点都加上自环。

  $$s(R)=\{< 3,1> ,< 4,1> ,< 3,2> ,< 4,2> ,< 4, 3> ,< 1,3> ,< 1,4> ,< 2,3> ,< 2,4> ,< 3,4> \}$$

  说明：补充反向有序对，构造双向边。

$$t(R)=\left\{ \begin{aligned} &< 1,3>,< 1,4>,< 2,3>,< 2,4>,< 3,4> \\ &\text{推导：} <2,3> \in R \land <3,4> \in R \Rightarrow <2,4> \ (\text{已在}R\text{中}) \end{aligned} \right\}$$