imicola 关系
关系

关系

725 字 · 约 2 分钟

五种关系

由集合SS上的元素构成二元关系RR

  • 自反
    • 定义:对于 ∀x∈S\forall x \in S 都有 (x,x)∈R(x,x) \in R
    • 证明思路:
      • 设x∈Sx \in S
      • 根据基于RR的具体定义构造x与x的关系并且满足于R
      • 因此(x,x)∈R(x,x) \in R
  • 对称
    • 定义:∀x,y∈S\forall x,y \in S,如果 (x,y)∈R(x,y) \in R,那么(y,x)∈R(y,x) \in R
    • 证明思路:
      • 设x,y∈Sx,y \in S且(x,y)∈R(x,y) \in R
      • 根据(x,y)∈R(x,y) \in R 与RR的具体定义,推导出yy与xx也满足关系 RR
      • 因此(y,x)∈R(y,x) \in R
  • 传递
    • 定义:∀x,y,z∈S\forall x,y,z \in S,如果(x,y)∈R(x,y) \in R且(y,z)∈R(y,z) \in R 那么 (x,z)∈R(x,z) \in R
    • 证明思路:
      • 设 x,y,z∈Sx,y,z \in S 且 (x,y)∈Rand(y,z)∈R(x,y) \in R \quad \text{and}\quad (y,z) \in R
      • 根据RR推导出xx与zz也满足关系
      • 因此(x,z)∈R(x,z) \in R
  • 反对称
    • 定义:∀x,y∈A\forall x,y \in A 如果(x,y)∈R(x,y)\in R且(y,x)∈R(y,x)\in R 那么x=yx = y
    • 证明思路:
      • 设x,y∈Sx,y \in S 且 (x,y)∈R(x,y) \in R 且 (y,x)∈R(y,x) \in R
      • 根据RR推导出如果假设成立则必须有x=yx = y
      • 因此 x=yx = y,故RR是反对称的

等价类

等价类代表某一特性在这个等价关系中是 等价的 如在x≡y (mod  3)x \equiv y \ (\mod 3)关系下有三个等价类: [0]={x ∣xmod  3=0,x∈I}[0] = \{x \ | x \mod 3 = 0,x \in I\} [1]={x ∣xmod  3=1,x∈I}[1] = \{x \ | x \mod 3 = 1,x \in I\} [2]={x ∣xmod  3=2,x∈I}[2] = \{x \ | x \mod 3 = 2,x \in I\}

等价关系与偏序关系

若一个二元关系R满足自反 对称 传递 则这个二元关系为等价关系 若一个二元关系R满足自反 反对称 传递 则这个二元关系为偏序关系

关系的运算

关系的复合运算一般使用矩阵形式展开

Aij={1(i,j)∈R0(i,j)∉RA_{ij} = \begin{cases} 1 & (i,j) \in R \\ 0 & (i,j) \notin R \end{cases}

  • 复合关系 R∘SR \circ S 则使用RR矩阵与SS矩阵进行矩阵乘法
  • 逆关系矩阵为原矩阵的转置

知识关联

1 反向链接 · 0 提及笔记
局部关系图谱 悬停高亮 · 点击跳转