离散数学-格与布尔代数

偏序集+代数系统

格是若干种运算

Ⅰ 满足什么条件的偏序集是格

格是结构 就要考察相关元素

偏序集——自反 反对称 可传递

从偏序集中取出一个子集

对于这样的子集集合

• 从代数的角度：格是一个集合，配备了两个运算 ∨∨ 和 ∧∧。
• 从序理论的角度：格是一个带有特殊性质的偏序关系≤≤。
• 实际上，这两种视角是统一的，只是强调的重点不同：
  • 集合+运算：更适合研究代数结构。
  • 偏序关系：更适合研究序结构。

体现偏序结构

双重身份——偏序集 哈希图表示 偏序格

代数系统——代数格 可以用同态同构

其实核心就是“把关系 与 运算等价看待”

偏序格定义：

A任意两个元素都有最大下届 最小上界，且两界都包含在A内

性质：

所以的全序集（链）都是格，任何两个元素都可比较

判断是格的方法：

考虑不在同一条连的元素！

由于两界唯一存在，可以看作两个二元运算，用保交 保联表示 ∩∪

inf{x,y} sup{x,y}

既然是运算，会满足哪些运算定律？

1）交换 我和你你和我的上下界一样

2）结合

(ab)c=a(bc) 证明两个元素相等-》偏序性质-》反对称性-》两元素互相小于等于-》两元素相等

证明两个小于等于关系

3）幂等 统一元素上下界都是子集

4）吸收

偏序格定义：A任意两个元素都有最大下届 最小上界，且两界都包含在A内 满足交换律结合律吸收律

一句话：偏序集上两元素总是能找到上下界

这个偏序集就和找两界的代数系统就称为偏序格

找两界这个过程可以被定义成交并两种运算，运算与满足这两个运算的节点就构成了代数格

也就是把 小于等于 看作 交并运算 还是把交并运算 看作 小于等于 关系

代数格定义：设<L,∩∪>是二元代数系统，若∩∪满足交换律结合律吸收律 则称为代数格

<L,∩，∪>是代数格，<L,≤>是偏序格，其中 偏序格上我们可以定义寻找最小上界最大下界为两个运算 ，如果把这两个运算定义为交并就是代数格

从代数格-》偏序格

只要在一个代数系统上找个两个满足交换律 结合律吸收律的运算，就一定能对应找到其对应的偏序集

• 偏序格：从偏序关系 ≤ 出发，强调上下界的性质。
• 代数格：从集合和运算 ∨、∧ 出发，强调代数运算的性质。
• 证明：

从代数格-》偏序格：

罗列条件：交换律 结合律 吸收律

还原为偏序格，还要证明这个偏序关系能找到最大下界最小上界

下证{a, b}存在最小上界：avb

先证上界

即证 ab都小于等于这个上界

a≤avb→a∩(avb)=a

b≤avb→b∩(avb)=b

再证最小

即证 任意c属于上界 都有avb≤c->(avb)vc=c

因为c为上界 所以a≤c b≤c

avc=c bvc=c

要证：(avb)vc=c

=av(bvc)=avc=c

4. 总结

只要在一个代数系统上找到两个满足交换律、结合律和吸收律的二元运算 ∨ 和 ∧，就可以通过这些运算构造出一个偏序关系 ≤，从而得到一个对应的偏序格。反之亦然。

换句话说，代数格和偏序格本质上是同一个数学对象的不同描述方式，它们之间可以相互转换。

6

Ⅱ 格如何和代数系统联系起来？

两个定理

格的最小上界 最大下界是不是都存在

在元素中找——抽象成运算

集合中元素的结构关系-》集合上考察两种运算

只要存在格，就有对应的代数系统

（要把格研究到有补XX格）

例子：

非空幂集P（s） 上有并和交运算

最小上界=A∪B 最大下界=A∩B

寻找这两个界限的运算 以及这个集合 就构成了

格<P(S), ∩，∪>

例子：

任意两个正整数上下界都能找到

最大公约数GCD 最小公倍数LCM

定理一：有格就有代数系统

如果集合上的两个运算满足若干性质 就是代数系统

格是代数系统，拥有两个运算，对应位病娇运算 满足四个性质：

幂等律

交换律

结合律

吸收律

定理二：

对于一个代数系统，如果其中存在两个代数体贴能满足L1-L4 可以找到一个对应格

证明特别喜欢用偏序集的反对称性——a<a*b a*b<a则a=a*b

格的性质

格的两个运算满足一样的性质，交换无妨。

对偶格：<L,≥><L,≤>是对偶格

对偶命题：将≥换≤，交并互换

对偶原理：任何真命题的对偶命题也是真命题

保序性：a≤b，c≤d -》 avc≤bvd a∩c≤b∩d

分配不等式：吸取对合取是小于等于：av(b∩c)≤(avb)∩(avc);

合取对吸取是大于等于 ：a∩(bvc)≥(a∩b)∪(a∩c)

模不等式：a≤c 等价于 av(b∪c)≤(avb)∩c

通过哈斯图理解：

保序性：ac下界小于a，c，a，c小于b，d，所以ac下界小于bd的最大下界

分配不等式：下界一定小于最大下界！！！保序性特例

模不等式：分配不等式特例

证明：

分配不等式是保序性得到的，模不等式是分配不等式得到的，其中，分配不等式是对偶命题，因此只需证一个

1）证明a∩c是b、d的下界，而b∩d是b、d的最大下界，因此a∩c≤b∩d

2）是a=c的情况：av(b∩c)是(avb)、(avc)的下界，而(avb)∩(avc)是(avb)、(avc)的最大下界，得证

即证原式≤(avb)、(avc)。 因为a≤a，b∩c≤b、c，因此av(b∩c)≤（avb），（avc）

3）必要性：若a≤c，则avc=c。由分配不等式：av(b∩c)≤(avb)∩(avc)=(avb)∩c

充分性：若av(b∪c)≤(avb)∩c,要整a≤c

因为a≤av(b∩c), (avb)∩c≤c，传递性得证！

证明方法：

1.自然运算的性质 吸收律 a、b≤avb a∩b≤a、b； a≤b，a≤c，则a≤b∩c； a≤c，b≤c，则avb≤c

2.格是运算定律：交换 结合 吸收 幂等；

3.偏序集性质：自反 反对称 传递性

4.对偶证一个

5.保序性 分配不等式 模不等式（如何使用？？？）

子格与代数系统

S包含于L

{S, ∩，∪} 非空子集+封闭性+子集 构成子格

{S1US2US3U..., 包含 }子格+空集 在包含关系下构成格 叫子格格 或 Sub(L)

子格的判断：找不可比的元素，两两之间是否能找到，最大下界最小上界，存在子集中

子格的证明：非空由自反易得

封闭：选xy∈S子集,a∈L大群，x<a y<a,所以xvy<a x∩y<a

所以 xvy<a x∩y都满足x<a 属于S

特殊的子格——理想

a∈子格I x∈父格L

则由x≤a -》x∈子格I

也就是说 任何在父格中比子格元素小的元素 都在 子格I内（比子格中最大元素小的元素都在子格中）

L的所有 理想 在 包含关系下的格族 叫理想格

//格同态

两个格之间存在 两个运算的 同态等式

<L,∩ ， ∪> <S, *, 。>

f(x∩y)=f(x)*f(y) f(x∪y)=f(x)。f(y)

同样存在单同态 满同态 同构

Q：格同构的图像判断：

五元素格同构 菱形格 五角格 钻石格

格按照满足的运算定律 可以划分为

分配格

模格

按照特殊元划分 可以划分为有界格有补格，有补格是特殊的有界格

运算定律

分配格 模格

分配格都是模格（不含五角格 钻石格）

分配格：满足a∩(b∪c)=(a∩b)∪(a∩c)

幂集格 命题格 链 都是分配格

要求验证 不需要证明

证明：满足分配律

这里的所有证明都是翻译题：将小于等于关系与交并运算翻译过来就可以了

找中间量a 证明a∩(b∪c)=a (a∩b)∪(a∩c)=a

a与bc的结果有两种，

一是a是最大元

二是a不是最大元

下证在12情况下都有等式成立

2）中 ：

证明a∩(b∪c)=a ：因为b≤bvc c≤bvc

无论a比b小 还是a比c小，都有a≤bvc

翻译为：a∩(bvc)=a（也可以反向思考 把这个翻译回去）

证明(a∩b)∪(a∩c)=a：因为a≤b a≤c，则a∩b或a∩c=a，所以(a∩b)∪(a∩c)=a

证明不是分配格：即找三个元素，证明其不满足分配律

又因为我们讨论过，链上元素满足分配律，因此考虑不在一条链上的元素

钻石格：五角格

判断定理

伯克霍夫定理：一个格是分配格的充要条件是格中没有“任何子格与钻石格，五角格同构”

因此：Ⅰ 四个元素以下的格都是分配格

Ⅱ 五个元素的格仅有两个格是非分配格 ，其他三个格都是分配格

一个格是分配格的充裕条件是格的两种运算具有消去律

a∩b=a∩c且a∪b=a∪c 推出 b=c

即 已知 分配格 + a∩b=a∩c且a∪b=a∪c 要推出 b=c

分配格=吸收律 交换律 分配律

吸收律：b=b∩(bva)=b∩(avb)

由题知 =b∩(avc)

由分配律 =(b∩a)∪(b∩c)

由题知 =(a∩b)∪(b∩c)=(a∩c)∪(b∩c)

分配律提取c =(a∪b)∩c=(avc)∩c=c

类比集合

充分性：

反正，如果不是分配格，那么一定满足伯克霍夫定理。

即存 在两元素同最大最小元 但两元素不一样（五角格 钻石格）

模格（戴德金格）：

满足模律：模律描述了当 a≤c 时，格中的“并”和“交”运算满足的一种分配性质。

avc=c av(b∩c)=(avb)∩(avc)=(avb)∩c

从模不等式·-》模律

将五角格变为菱形格：菱形同构定理：戴德金转置定理

模格的哈斯图是若干个菱形堆积形成的

判定定理

戴德金判断定理：一个格是模格的充分必要条件是该格中没有任何子格与五角格同构

因此由所有分配格都是模格：
分配格满足a∩(b∪c)=(a∩b)∪(a∩c)

在分配格中，如果 a≤c，则模律成立

四个元素以下的格都是模格，

五个元素除五角格都是模格

也就是说，分配格是模格 不是分配格的钻石格也可能是模格，判断是否是模格就看也没有五角

完全格

格的任意子集的都存在两界

有限格必定是完全格

无限集不存在

幂集格是完全格

[0,1]是完全格 (0,1)不是完全格

有界格 有补格

有界格：存在全下界 全上界

<L,+，* ，0，1>

格<L,≤>

全上界：b∈L 对任意x∈L， 都有x≤b，称a为格<L,≤>的全上界 记为1

a是L中唯一的最小的元素

全下界：a∈L 对任意x∈L， 都有a≤x，称a为格<L,≤>的全下界 记为0

a是L中唯一的最小的元素

有限格一定是完全格

有限格一定是有界格

性质：

对于偏序运算 ∩（求最大下界）1是单位元 0是零元

因为上界比任何数都大，因此交出来还是本身（相对于全集）

对于偏序运算 ∪（求最小上界）0是单位元 1是零元

x+0=x x+1=1

x*0=0 x*1=x

有界格不一定是有限格 [0,1]被压缩在01，但是有无限个元素

有限格一定是有界格，此时 0全下界=a1∩a2∩a3∩a4∩an 1全上界=a1∪a2∪a3∪a4∪an

有上下界就可以探究补格

有补格：每个元素都有补元

有补格是有界格，否则不好说明谁是全集

L是全集-有界格

1是全上界 0是全下界

补元：

若子格中a∈L 总存在 b∈L，使得avb=1 a∪b=0，即 无交 且 覆盖

则称b为a的补元a',

补格：

若L子集中所有元素a都存在补元，则L是有补集

性质：

补元和本元 拥有共同最大下界0 最小上界1

01上下界互为补元

补元可以有多个

ab互为补元

判断补元/补格：

01互补

不可以在一条链上：否则一定构成偏序关系a≤b，则最大下界a，最小上界b

补元和本元 拥有共同最大下界0 最小上界1

+++++策略：找不是本链的元素，保证同上下元！！！！

有补格（补元可能多个）

有界分配格L（可能有元素没有补元），则L的任意一个有补元的补元唯一：

唯一性证明用反证法：

设a∈L有两补元b和c，由补元定义：

a∩b=a∩c=0 a∪b=a∪c=1 --分配格有消去律

b=c

所以补元唯一

（一旦有两补元，则由补元定义则上下界一致，由分配律消去得到两补元一致）

• 在一般格中，补元可能不唯一（例如非分配格）。
• 在分配格中，补元是唯一的，这是分配律的结果。

有补分配格L（任意元素都有补元），则L的任意一个元素都存在唯一补元

同理

<L,+,*,补，0，1>

因为是唯一补元，所以补元运算具有 双重否定、德摩根律

德摩根证明：

(avb)'=a'∩b'

即证：二者互补 即证二者相交=0 相并=1

拆开即可

布尔代数：

有补分配格 又称为布尔格，因为在其上的运算满足布尔运算

即 布尔格中每个元素都有补元且唯一，因此可以将求补元作为一元运算。！！！一元运算！！！

赋予了求补运算的布尔格称为布尔代数，<L,∩∪，'补，0，1>。

布尔代数性质：

格：交换 幂等 吸收 分配 结合 全上界 全下界 每个元素存在补元

同一律：存在全上界 全下界 可以用同一律描述：

a∩1=a av0=a(布尔代数性质)

互补律：补元存在可以用互补律描述：对任意a∈L，存在补元a'∈L，使得ava'=1,a∩a'=0（也是布尔代数性质！！！）

布尔代数满足交换 结合 吸收 分配 同一 互补律的代数系统

而 交换律 分配律 同一律 互补律 可以推导 结合律 吸收律

所以

设<Bool, ∩ ∪>其中∩∪是Bool二元运算，对任意abc有：

交换律

分配律

同一律

互补律

则称Bool为布尔代数

与或非门与布尔代数：

取最简单二元布尔代数：

仅包含{0,1}

集合代数：

P(A)是幂集，<P(A),∩∪补,空集，A>是布尔代数

哈斯图为n维立方体图 P(A)有2^n元素

命题代数：

<命题，合取，吸取，取反，F，T>

有界格使得元素有界

有补格使得元素有补，有补的前提是有界

而分配格使得补元唯一

所以有补分配格就是 补元唯一的格

布尔同态：