【离散数学3】格和布尔代数

格

【定义】格：（前面写了，偏序关系是一个自反、反对称、传递的关系）。(A,≼)(A,≼) 是一个偏序集，如果 A 中任意两个元素都有最小上界和最大下界，称为 (A,≼)(A,≼) 是格。

• 最小上界 记为 a∨ba∨b
• 最大下界 记为 a∧ba∧b
• (A,∨,∧)(A,∨,∧) 称为 格所诱导的代数系统

【定义】子格： 格 (A,≼)(A,≼) 诱导的代数系统是 (A,∨,∧)(A,∨,∧)，如果 B⊆A,B≠∅B⊆A,B≠∅，而且 ∧,∨∧,∨ 对 B 粉笔，那么称为 (B,≼)(B,≼) 是 (A,≼)(A,≼) 的子格

• 【定理】 子格是格

【定理1】：

• a≼a∨ba≼a∨b
• b≼a∨bb≼a∨b
• a∧b≼ba∧b≼b
• a∧b≼aa∧b≼a

【定理2】：如果 a≼b,c≼da≼b,c≼d，那么

• a∨c≼b∨da∨c≼b∨d
• a∧c≼b∧da∧c≼b∧d

【定理3】保序性： 如果 b≼cb≼c，那么 a∨b≼a∨c,a∧b≼a∧ca∨b≼a∨c,a∧b≼a∧c （用定理2推导）

【定理3】运算律

• 交换律。a∨b=b∨a,a∧b=b∧aa∨b=b∨a,a∧b=b∧a
• 结合律。a∨(b∨c)=(a∨b)∨c,a∧(b∧c)=(a∧b)∧ca∨(b∨c)=(a∨b)∨c,a∧(b∧c)=(a∧b)∧c
• 幂等律。a∨a=a,a∧a=aa∨a=a,a∧a=a
• 吸收率。 a∨(a∧b)=a,a∧(a∨b)=aa∨(a∧b)=a,a∧(a∨b)=a

证明：根据定义，交换律、幂等律显然成立。
结合律的证明：第一步，借用定理1得到结论 a≼(a∨b)∨c,b≼(a∨b)∨c,c≼(a∨b)∨ca≼(a∨b)∨c,b≼(a∨b)∨c,c≼(a∨b)∨c；第二步，对三个式子用定理2，得到 a∨(b∨c)≼(a∨b)∨ca∨(b∨c)≼(a∨b)∨c （右边做了幂等律）；第三步，用类似的方式，可证 (a∨b)∨c≼a∨(b∨c)(a∨b)∨c≼a∨(b∨c)，然后等式成立。
吸收率的证明思路类似

【定理4】分配律

• a∨(b∧c)≼(a∨b)∧(a∨c)a∨(b∧c)≼(a∨b)∧(a∨c)
• (a∧b)∨(a∧c)≼a∧(b∨c)(a∧b)∨(a∧c)≼a∧(b∨c)

证明：
一方面，a=a∧a≼(a∨b)∧(a∨c)a=a∧a≼(a∨b)∧(a∨c)
另一方面 b∧c≼b≼a∨b,b∧c≼c≼a∨cb∧c≼b≼a∨b,b∧c≼c≼a∨c，合起来得到 b∧c≼(a∨b)∧(a∨c)b∧c≼(a∨b)∧(a∨c)
上面两个合起来，得到 a∨(b∧c)≼(a∨b)∧(a∨c)a∨(b∧c)≼(a∨b)∧(a∨c)

分配格

上面指出了一个定理：

• a∨(b∧c)≼(a∨b)∧(a∨c)a∨(b∧c)≼(a∨b)∧(a∨c)
• (a∧b)∨(a∧c)≼a∧(b∨c)(a∧b)∨(a∧c)≼a∧(b∨c)

我们研究这样一类特殊的格，使得上式以等号的形式成立

【定义】分配格： (A,∨,∧)(A,∨,∧) 是格 (A,≼)(A,≼) 引导的代数系统，如果同时满足以下条件，称为 (A,≼)(A,≼) 是分配格

1. a∨(b∧c)=(a∨b)∧(a∨c)a∨(b∧c)=(a∨b)∧(a∨c)
2. (a∧b)∨(a∧c)=a∧(b∨c)(a∧b)∨(a∧c)=a∧(b∨c)

参考文献

《离散数学》上海科学技术出版社，左孝凌