格与布尔代数


偏序关系

  • 极 小/大 元:子集内不存在比其小/大的元素==(包括无法比)==
  • 最 小/大 元:子集内所有元素都比其大/小==(必须可比)(存在即唯一)==
  • 上/下 界:大于/小于 子集内所有元素==(必须可比)==
  • 上/下 确界:上界中最小/下界中最大==(必须可比)==

基本概念

  • 定义:偏序集中任取两个元素都有上下确界
  • 平凡格:所有的全序集
  • 格诱导代数系统:<A,∨,∧>是由格 <A,≼> 诱导的代数系统
  • 子格:设 <A,∨,∧>是由格<A,≼>诱导的代数系统。B是A的非空子集,如果∧和∨在B上封闭,则称<B, ≼>是<A, ≼>的子格。

格的对偶

<A,≼>是格, ≼的逆关系记作≽ , ≽也是偏序关系。 <A, ≽>也是格,<A, ≽>的Hasse图是将原Hasse图旋转$180^o$。
对偶命题:如果将命题P中的 ≼ 换成 ≽ ,∧换成∨,∨换成∧,得到命题P' ,称P'为P的对偶命题。
对偶原理: 如果P对任何格为真,则P'对任何格也为真。

P: a∧b≼a               P': a∨b≽a 
{a,b}的最大下界 ≼ a     {a,b}的最小上界 ≽ a

同态与同构

同态映射:$\begin{aligned}f (a∨_{1}b)= f (a)∨_{2} f (b)\\f (a∧_{1}b)= f (a)∧_{2} f (b)\end{aligned}$
同态像:$< f (A1), ≼_2> -> <A1, ≼_1>$
同构:f为双射,则为同构

格的性质

  1. $a≼a∨b, b≼a∨b, a∧b≼a, a∧b≼b$
  2. $如果a≼b, c≼d,则a∨c≼b∨d, a∧c≼b∧d$
    推论:==保序性==$在一个格中,任何 a, b, c∈A,如果b ≼ c,则 a∨b ≼ a∨c,a∧b ≼ a∧c。$
  3. $交换律。即 a∨b = b∨a, a∧b = b∧a$
  4. $幂等律。即 a∨a = a, a∧a = a$
  5. $结合律。即(a∨b)∨c = a∨(b∨c), (a∧b)∧c = a∧(b∧c)$
  6. $吸收律。即 a∨(a∧b) = a, a∧(a∨b) = a$
  7. <A,∨,∧>是代数系统,如果∨和∧是满足吸收律的二元运算,则∨和∧必满足幂等律。
  8. ∨和∧不满足分配律。但有分配不等式: $\begin{aligned}a∨(b∧c) ≼ (a∨b)∧(a∨c)\\(a∧b)∨(a∧c) ≼ a ∧(b∨c)\end{aligned}$
  9. $a≼b$ $\iff$ $a∧b=a$$\iff$$a∨b=b$

特殊的格

分配格

  • 定义:满足分配律的格诱导代数系统
  • $<P(E),∪,∩>是分配格$
  • 分配格中的两个等式互为充分必要条件。
  • 判定:没有任何子格与下述两个五元素非分配格之一同构==(充要条件)==
    两个重要的五元素格:
    五元素格
  • 推论:

    1. 小于五个元素的格都是分配格
    2. 任何一条链都是分配格
  • 性质:设< A, ≼ >是分配格,对任何a, b, c∈A, 如果有 ==a∧b=a∧c 及 a∨b=a∨c,则必有 b=c==。证明用吸收律

有界格

  • 全 上/下 界:设<A, ≼>是格,如果存在元素a∈A,对任何x∈A, x≼a / a≼x, 则称a是格的全上/下界,记作1/0。==(可比)(唯一)==
  • 定义:如果一个格存在全上界1与全下界0,则称此格为有界格。
  • 所有有限个元素的格都是有界格

有补格

  • 补元:设 <A, ≼>是个有界格,a∈A, 如果存在b∈A, 使得 a∨b=1, a∧b=0,则称a与b互为补元。
  • 定义:一个有界格中,如果每个元素都有补元,则称之为有补格。
  • 有界分配格中元素的补元唯一

布尔格

  • 定义:如果一个格是有补分配格,则称之为布尔格。布尔格中每个元素都有==唯一补元==,元素a的补元记作a 。

几个特殊格的关系

graph LR
        x[格]--有全上/下界-->a[有界格];
        a[有界格]--有补元-->b[有补格];
        x[格]--满足分配律-->c[分配格];
        b[有补格]-->d[布尔格];
        c-->d[布尔格];

布尔代数

  • 定义:由布尔格 <B, ≼> 诱导的代数系统 <B, ∨, ∧, ̄>,称 之为布尔代数。其中 ̄是取补元运算。如果B是有限集合,则称它是有限布尔代数。
  • 性质中德摩根律的证明:等式左边取非后析取=1;
  • 原子:Hasse图中盖住0的元素。
  • Stone定理:设<B,∨,∧, ̄>是有限布尔代数,M是B中所有原子构成的集合,则 <B,∨,∧, ̄>与<P(M),∪,∩,~>同构。

    • 推论1: 任何有限布尔代数的元素个数为2n
    • 推论2: 两个有限布尔代数同构的充分且必要条件是元素个数相同
  • 结论:

    1. 有限布尔代数的基数都是2的幂
    2. 对于任何自然数n, 仅存在一个2n元的布尔代数
Last modification:June 29, 2023
如果觉得我的文章对你有用,请随意赞赏