离散数学中,格的定义如下:
设 < S , ≼ > < S, \preccurlyeq> <S,≼>是偏序集,如果 ∀ x , y ∈ S , { x , y } \forall x,y\in S, \{x,y\} ∀x,y∈S,{x,y}都有最小上界和最大下界,则称 S S S关于偏序 ≼ \preccurlyeq ≼作成一个格。[1]
那么对于某一偏序集的哈斯图,我们只需对图中任意两个不同元素都验证其最大下界以及最小上界的存在性。
注意到:这里的最大下界和最小上界都是针对下界集和上界集而言的。 要求最大下界满足与下界集合中的任意一个元素都可比,最小上界满足与上界集合中的任意一个元素都可比。这里的上界集和下界集都是公共上界集和公共下界集。
举例说明:
1)对于图1, { b , d } \{b,d\} {b,d}的上界集为 { e , c } \{e,c\} {e,c},而 e , c e,c e,c不可比,故不是格。
2)对于图2,任意两个元素组成的集合都有最小上界和最大下界,故是格。
3)对于图3, { d , f } \{d,f\} {d,f}的下界集为 { b , c , a } \{b,c,a\} {b,c,a},而 b , c b,c b,c不可比,故下界集中找不到能跟所有元素都可比且最大的元素,从而该偏序集不是格。
上图中,比较具有迷惑性的是图2的 { 3 , 10 } \{3,10\} {3,10},但实际上,它们的上界集是 { 30 } \{30\} {30},显然,30是最小上界。
参考:
[1] 离散数学,第2版,dldls等.
[2] https://zhuanlan.zhihu.com/p/64478645
[3] https://jasonyanglu.github.io/files/lecture_notes/%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6_2020/%E7%AC%AC%E5%85%AD%E7%AB%A0%20%E5%87%A0%E4%B8%AA%E5%85%B8%E5%9E%8B%E7%9A%84%E4%BB%A3%E6%95%B0%E7%B3%BB%E7%BB%9F.pdf