第六章 偏序

序关系（ordering relation）也叫做“偏序关系”、“弱偏序关系”或“半序关系”是集合元素间的一种二元关系。设一非空集合S，其元素之间定义了一种二元关系→，若R满足：1.不可逆性：对任意a,b∈S，若有a→b，则没有b→a。2.传递性：对任意a,b,c∈S，若有a→b，b→c，则有a→c。3.有自反性：对任意a∈S，都有a→a。则→称为S上的一个偏序或偏序关系。

序关系和结构

• 6.1 偏序集
  • 自反、反对称、传递
    • 等价关系：对称性
  • 定理2. 偏序的有向图中没有长度大于1的回路（cycle）。
  • （A,R）集合A上的二元关系R是一个偏序 (partial order)
  • 
  • 对偶偏序集：如果R是A上偏序，则R-1也是A上偏序。 （A，R-1）称为（A，R）的对偶偏序集。
    • 例：（A，≥）是（A，≤）的对偶偏序集。
  • 线性序关系
    • 偏序集（A，≤）中任意两个元素都是可比的
    • 称（A，≤）是一个线性序集（linearly ordered set）
    • A上的偏序≤也称为是线性序
    • 也称（A，≤）是一个链（chain）
  • 乘积偏序
    • 如果(A,≤1)，(B,≤2)是偏序，则(A×B，≤)是乘积偏序（product partial order）
    • 其中的偏序≤定义为：
    • 子主题
  • 字典序
    • 严格序
      • （A，≤）是偏序，令a<b  a≤b，a≠b， 称（A，<）是严格序。
    • 字典序
      • 
        • 
      • 
  • 哈斯图
    • 顶点和无向边
    • 
    • 子主题
  • 拓扑排序
    • 
  • 同构
    • 
    • 
• 6.2 偏序集的极大极小元
  • 极大元（第一层的元素）、极小元、最大元（第一层只有一个）、最小元、上界、下界
    • 
      • 上界是大偏序集A-B 或B中的一个元素
    • a 是A的最大元: a∈A，任意b∈A，b ≤a.
      • 是自身偏序集A的元素
    • a 是A的极大元: a∈A，没有b∈A，a<b.
  • 定理1. 有限偏序集A中，至少有一个极大元，至少有一个极小元。
  • 定理2. 偏序集A中，至多有一个最大元，至多有一个最小元。
  • 偏序集A中，如果有最大元，称之为单位元1，如果有最小元，称之为零元0。
  • 子主题
• 6.3 格
  • 定义: 格是一个偏序集（L，≤），其中对任意a，b∈L，a，b都有上下确界（LUB、GLB）
  • 格 (L, ≤，∨，∧)
    • 
    • 定理1. 设（L1, ≤,∨,∧），（L2, ≤,∨,∧）都是格。 则（L1×L2，≤,∨,∧）也是格。
  • 
    • 封闭是指上下确界也得在里面
  • 格的同构
    • 
    • 定理2：设L是格，则a≤b  a∨b＝b  a∧b＝a.
    • L是一个线性序集，则它是一个格。
  • 格的性质
    • 
  • 
  • ≤、≥只是表示上下界，∨和∧才是上确界和下确界
  • 特殊格
    • 有界格（Bounded lattice）：有最大元1，最小元0的格叫有界格。
    • 分配格(Distributive Lattice)：满足分配律的格：
      • 1. a∧(b∨c)＝(a∧b)∨(a∧c)
      • 2. a∨(b∧c)＝(a∨b)∧(a∨c)
        • b∧c为0，还有∨a呢，但是后面的有一个为0就没了
      • 格(P(S),∪,∩)是分配格。
      • 不满足条件的子格限制，其他满足
      • 一般情况下除了幂集的包含关系都不是分配格
    • 可补格
      • 有界格L称为是可补格，如果对任意a∈L，有a’∈L，使得 a∨a’=1，a∧a’=0. 称a’为a的补元。
      • 设L是有界分配格，a∈L，如果a有补元，则其补元唯一。
• 6.4 有限布尔代数
  • 
  • 有补分配格叫做布尔代数。
  • Bn（幂集 ）是布尔代数。
    • 
  • Dn是n的因子组成的格（整除关系那个）
    • 定理2. n=p1p2……pk时，Dn是布尔代数。
  • 布尔代数的性质
    • 
    • 
  • 
• 6.5 布尔函数
  • 布尔函数又叫真值函数，布尔函数的表也叫真值表