本篇源于 B 站的【离散数学】3.5h让你离散数学不挂科，感谢老师！

概念

补充：

  • LAL_{A} 小于等于关系
  • DAD_{A} 整除关系
  • R⊆R_{\subseteq} 包含关系

补充：关系的运算

  • domRdomR：定义域

  • ranRranR：值域

  • fldRfldR：域，等于定义域并上值域

  • R−1R^{-1}：R 的逆

  • F∘GF\circ G：复合关系

例：设 F={<3,3>,<6,2>},G={<2,3>}F = \{<3,3>,<6,2>\},G = \{<2,3>\}

  1. F−1={<3,3>,<2,6>}F^{-1} = \{<3,3>,<2,6>\}
  2. F∘G=<6,3>F\circ G = {<6,3>}（6->2->3)

  • R↾AR↾A：R 在 A 上的限制

    R 中满足第一个元素，都是来源于 A 集合的有序对

  • R[A]R[A]：A 在 R 上的像

    R 中满足第一个元素，都是来源于 A 集合的有序对的第二个元素

例：设 R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>}R = \{<1,2>,<1,3>,<2,2>,<2,4>,<3,2>\}

  1. R↾{1}={<1,2>,<1,3>}R↾\{1\}=\{<1,2>,<1,3>\}（第一个元素为 1 的只有这两个）
  2. R↾∅=∅R↾\emptyset =\emptyset
  3. R[{1}]={2,3}R[\{1\}]= \{2,3\}（找出那两个对之后，只取第二个元素）

补充：关系的性质

  • 自反性（ ∀x,x∈A∀x,x∈A -> <x,x>∈R<x,x>∈R）

    关系图每个顶点都自成环，关系矩阵主对角元素都为 1

  • 反自反性（ ∀x,x∈A∀x,x∈A -> <x,x>∉R<x,x>∉R）

    关系图每个顶点都不自成环，关系矩阵主对角元素都为 0

  • 对称性 symmetric R−1=RR^{-1} = R

    关于主对角线对称，<x,y>∈R<x,y>∈R -> <x,y>∈R<x,y>∈R，

  • 反对称性 antisymmetric

    关于主对角线对称的任意两对元素至多有一个 1，<x,y>∈R⋀<y,x>∈R<x,y>∈R ⋀ <y,x>∈R -> x=yx=y

  • 传递性 Transitive

    R∘R⊆RR\circ R⊆R

B7B59CB23E9F3CA8B60FA63606D26F7F

img

  • （反）对称的关系图描述开头加个 如果
  • 对称：如果连跳了两个点及以上，那一定能跳回去（非原路）

注意：

  • 自反和反自反不是互斥的，可以既不是自反又不是反自反
  • 是否对称对于是否反对称没有关系

最多加到4次方

等价关系和等价类

未完成，空降 13:15