离散数学：四、关系

离散数学的关系部分，参考教材为XJTU出版的离散数学。内容包括关系的概念、关系的性质、关系的合成。

四、关系

• 集合的叉积 n元组
  • n元组
    • 有顺序
  • 叉积
    • 定义——叉积是元组的集合
    • 前集、后集、前者、后者、维数
    • 叉积相等、元组相等
      • 与空集的叉积
    • 叉积 对交和并的左右分配律
    • 叉积幂
• 关系的基本概念
  • 定义——关系是叉积的子集
  • 全关系、空关系、幺关系/单位关系
  • 关系的交并补运算
    • 关系是叉积的子集，故关系也是集合
  • 关系的扩充
  • n元关系
  • 前域，后域
  • 关系的一些关联性质
    • 包含时前域后域的保序性
    • 交、并时前域后域的关系：
• 关系的表示方法
  • 集合表示法
  • 矩阵表示法
  • 图形表示法——有向图，称为关系图
• 关系的性质
  • 牢记定义，证明都要从定义出发
  • 自反/反自反
    • 要求："xÎX
    • 常见的自反关系有：=，≤，包含关系
    • 常见的反自反关系有：≠，＜，真包含
    • 从关系矩阵来看：自反关系关系矩阵的对角线上元素全是1；反自反关系关系矩阵的对角线上元素全是0。从关系图来看：自反关系关系图的各结点上全都有自反圈；反自反关系关系图的各结点上全都没有自反圈。
    • 幺关系一定是自反关系，但自反关系不一定是幺关系
  • 对称/反对称
    • 要求抓住定义即可
    • 对称——=，≠，同余
    • 不对称——≤，包含
    • 从关系矩阵来看：对称关系的关系矩阵是对称矩阵。从关系图来看：对称关系关系图的结点间若有弧则都是双向弧；反对称关系关系图的结点间若有弧则都是单向弧.
  • 传递/反传递
    • 传递——=、≤，包含关系
    • 反传递——≠、父子关系、朋友关系
  • 相等关系是自反的、对称的、反对称的、传递关系。 全关系X2是自反的、对称的、传递的。 幺关系I 是自反的、对称的、反对称的、传递的。 空关系是反自反的、对称的、反对称的、传递的。
• 关系的运算
  • 关系的逆运算
    • 定义
    • 基本定理
      • 反身律、保序性、分配律（交、并、差）、叉积、交换律（补）
  • 关系的合成运算
    • 定义
      • 涉及两个关系，三个集合
    • 基本定理
      • 前域、后域；保序性；结合律；分配律-并；分配不等式-并；逆运算
  • 关系矩阵的合成运算
    • 矩阵乘法——其中，乘法加法变为布尔乘与布尔加
  • 关系的复合幂和闭包
    • 定义
      • 复合幂：0次，1次，m+1次（建立在合成运算的基础上）
      • 传递闭包：1到无穷
      • 自反传递闭包：传递闭包+自反关系
    • 传递闭包基本定理
      • 
    • 自反传递闭包的基本定理类似
• 等价关系
  • 等价关系和等价类
    • 定义
      • 等价关系：自反、对称、传递
      • 等价类——具有等价关系，代表元（任意一个）
      • 商集、秩
    • 等价关系的实质是将A中的元素进行分类
    • 等价类的性质
    • 等价关系的粗细
      • 例：A上最细的等价关系为幺关系，A上最粗的等价关系为全关系
    • 等价关系包含，等价类包含；等价关系相等，等价类相等
      • 等价关系与等价类集合一一对应。即相同的等价关系对应着相同的等价类集合，不同的等价关系对应着不同的等价类集合
  • 集合的划分
    • 覆盖、划分
      • A上的划分一定是A上的覆盖；反之则未必
      • 由集合A上的等价关系R所产生的等价类之集构成集合A上的一个划分
• 半序关系
  • 定义：非空+自反、反对称、传递——≤，包含
    • 拟序（反自反、传递）——＜，真包含
  • 可比较性
    • 半序关系实际上是在集合中建立了一种比较关系
    • 全序/线性序关系
      • 半序关系+全可比较性
  • 相关概念
    • 后继、前驱
      • (R, ≤)的每个元素都没有后继；每个元素都没有前驱。
  • 半序集的表示法——哈斯图
    • (1)结点a+必须画在结点a 的紧(斜)上方； (2)不画边的方向。
    • 省略了自反性的边(圈)； 省略了(反对称性)方向； 省略了传递性的边；
  • 4类元素
    • 最大/最小元
      • 不一定存在（即使是有限集）；若存在则唯一；在B中
    • 极大/极小元
      • 不一定存在（有限集一定）；若存在一般不唯一；在B中
    • 上/下界，有界
      • 不一定存在（有限不一定有，有也不一定有限）；若存在，可以在B中，也可以不在B中
    • 上/下确界
      • 不一定存在（即使是有限集）；若存在则唯一；若存在，可以...，也可以不在...
  • 良序集
    • 半序关系+任意一个非空子集都有最小元
    • 全序集未必是良序集
      • (I , ≤) 虽是全序集，但却不是良序集
    • 性质
      • 良序集一定是全序集
      • 对于良序集中的元素a，若a不是最大元，则a的直接后继一定存在