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

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

3 years ago

source link: https://www.guofei.site/2021/08/28/discrete_mathematics_4.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

2021年08月28日

Author: Guofei

文章归类: 5-9-应用数学，文章编号: 5904

版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2021/08/28/discrete_mathematics_4.html

Edit

格

【定义】格：（前面写了，偏序关系是一个自反、反对称、传递的关系）。(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)