代数结构：5、格与布尔代数

16.1 偏序与格

偏序集：设P是集合，P上的二元关系“≤”满足以下三个条件，则称“≤”是P上的偏序关系（或部分序关系）

（1）自反性：a≤a，∀a∈P；

（2）反对称性：∀a，b∈P，若a≤b且b≤a，则a=b；

（3）传递性：∀a，b，c∈P，若a≤b且b≤c，则a≤c；

定义1 格

​ 设$(L,⪯)$为偏序集，如果任意的$a,b\in L $有最小上界与最大下界时，称$L$为‘格‘，以$a\lor b = lub(a,b)$(leastupperbond)表示$a,b$的最小上界，$a\land b =glb(a,b)$（greatestlowerbond)表示$a,b$的最大下界。

定义2 覆盖

​ $(L,⪯)$为格，如果$a⪯b,a\ne b$（记为$a\prec b$），且不存在 u ∈ L − { a , b } u\in L-\{a,b\} u∈L−{a,b},使$a\prec u\prec b$，则称$a$覆盖 $b$.

​ 链:若$a\prec b$，如果有$c_1,\cdots ,c_k\in L,k\ge 1$ ,使$c_{i+1}$覆盖$c_i(ui=1,2,\cdots ,k-1)$，且
$$a=c_1\prec c_2\prec \cdots \prec c_k=b$$
​ 则称$c_1,\cdots ,c_k$为连接$a,b$的链，如果L中的任意两个元素总有连接它们的链，则称$L$是离散的。

​ 有限的离散全序集的哈斯图由一条链组成

定义3 完全格

​ $(L;\prec )$为偏序集，当$\forall A\subseteq L $有最大下界、最小上界时，$L$显然是格，称为‘完全格‘，$L$自身的最小上界是整个格$L$的最大元，记为1；$L$自身的最小下界为整个格$L$的最小元记为0.子集$A$可以是有限的，也可以是无限的。

定理1 格的关系运算

$(L,⪯)$为格，则对任意$a,b\in L$有

1. $a\prec a\vee b,a\wedge b\prec a$
2. $a⪯b⟺a\vee b=b$
3. $a⪯b⟺a\wedge b=a$

画个哈斯图是显然的，或者注意到按照定义，我们有$a\vee b=lub(a,b),a\wedge b=glb(a,b)$，且若$a⪯b$,则$lub(a,b)=b$就容易得到了

定理2 格的运算律

1. 幂等律：$a\wedge a=a,a\vee a=a$
2. 交换律：$a\vee b=b\vee a,a\wedge b=b\wedge a$
3. 结合律：$a\vee (b\vee c)=(a\vee b)\vee c,a\wedge (b\wedge c)=(a\wedge b)\wedge c$
4. 吸收律：$a\vee (a\wedge b)=a,a\wedge (a\vee b)=a$

P211

那么我们可以将$[L;\wedge ,\vee ]$视为代数系统

引理 1 代数系统L中的等价关系

​ 在$[L;\vee ,\wedge ]$中二元关系$\vee ,\wedge$满足上述4条运算律，则$\forall a,b\in L,a\wedge b=a⟺a\vee b=b$

KaTeX parse error: Undefined control sequence: \and at position 38: …row a\lor b =(a\̲a̲n̲d̲ ̲b )\lor b =b(最后一步是吸收律)

$a\vee b=b\Rightarrow a\wedge b=a\wedge (a\vee b)=a$

引理2 通过L构造偏序集

​ 在$[L;\wedge ,\vee ]$中，$\wedge ,\vee$满足4条运算规律，定义关系$⪯$如下:$\forall a,b\in L,a⪯b$，当且仅当$a\vee b=b$.则$(L;⪯)$为偏序集

证明自反性，反对称性，传递性 P211

定理3 引理2中的偏序集是格

证明$a\vee b=lub(a,b),a\wedge b=glb(a,b)$ P211

定义4 格的另一种定义方式

​ $[L;\vee ,\wedge ]$是一代数系统，$\vee ,\wedge$是定义在$L$上的二元运算，当其满足$L_1$到$L_4$时，称$L$为格，并称$\wedge$为积(交),$\vee$为和(或并)

定理4 保序性

​ 格$[L;\vee ,\wedge ],\forall a,b,c\in L$,当$b⪯c$时有$a\wedge b⪯a\wedge c$及$a\vee b⪯a\vee c$

定义5 子格

​ $[L;\vee ,\wedge ]$为格，$T\ne \varnothing ,T\subseteq L$,$T$关于$\vee ,\wedge$封闭(即$a,b\in T,a\vee b\in T,a\wedge b\in T$)时，称$T$为$L$的子格

​ 注意，当$T$为$L$的子格时，$T$一定是格，但当$T\subseteq L$,$T$关于$L$中的偏序关系$⪯$为格时，$T$不一定是$L$的子格，因为$T$中的运算关系可能不同

​ 例如，一个群$G$的子群全体$S(G)$关于$\subseteq$关系所构成的格不是$G$的幂集关于$\subseteq$关系所构成的格的子格，因为子群的并不一定是子群

定义6 格的同态与同构

​ 设$[L;\vee ,\wedge ]$与$[S;+,\circ ]$为两个格，如果存在映射$\phi :L\to S，\forall a,b\in L$,有
$$\begin{gathered} \phi (a\wedge b)=\phi (a)\circ \phi (b) \\ \phi (a\vee b)=\phi (a)+\phi (b) \end{gathered}$$
​ 则称$\phi$为$L$到$S$的同态映射，当$\phi (L)=S$时(满射)，则说两个格同态，当$\phi$是一一对应(双射),说同构。如果$L=S$,则称为自同态和自同构。

定理 5 同态映射是保序的

​ 若$\phi$是格$L,S$间的同态映射，则$\phi$是同态映射，即$\forall a,b\in L$，若$a⪯b$,则$\phi (a)⪯\phi (b)$注意不是当且仅当

定理6 同构映射的保序性

​ $a⪯b⟺\phi (a)⪯\phi (b)$

定理7 对偶原理

1. 设$P$是对任意偏序集都为真的一个命题，$P^{\prime }$是将$P$中所有$⪯,⪰$对换得到的对偶命题，则$P^{\prime }$对任意偏序集也为真
2. 设$P$是从格$[B;\vee ,\wedge ]$推出的命题，$P^{\prime }$是将$P$中$\vee$与$\wedge$对换得到的对偶命题，则$P^{\prime }$对格$[B;\wedge ,\vee ]$也为真

偏序反转后，自然从P得到了P‘

16.2 有补格及分配格

定义7 有界格

​ 一个具有最大元1和最小元0的格$[L;\vee ,\wedge ]$称为有界格

定理8 最大元和最小元的性质

​ 有界格中，$\forall a\in L:a\vee 1=1,a\wedge 0=0,a\wedge 1=a,a\vee 0=a$

定义8 有补格

​ $[L;\vee ,\wedge ]$为有界格，$\forall a \in L $,若$\exist b\in L$,有$a\lor b =1,a\land b =0$，则称$b$为$a$的‘补元‘,记$b$为$a’$.若$L$中的每个元有补元，称$L$为有补格

我们可以发现，对任意格成立分配不等式，即格$[L;\vee ,\wedge ]$中任意$a,b,c\in L$,有：

1. $a\vee (b\wedge c)⪯(a\vee b)\wedge (a\vee c)$
2. KaTeX parse error: Undefined control sequence: \and at position 34: …and c)\preceq a\̲a̲n̲d̲(b\lor c)

怎么说了，这个不等关系很容易记反，就画哈斯图吧

定义9 分配格

我们可以发现，对任意格成立分配不等式，即格$[L;\vee ,\wedge ]$中任意$a,b,c\in L$,有：

1. $a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
2. KaTeX parse error: Undefined control sequence: \and at position 28: …or(a\land c)= a\̲a̲n̲d̲(b\lor c)

则称格L为分配格

两个典型的非分配格

​ 只要哈斯图中含有这种子结构，就可以判断它不是分配格

定理9 分配格的判断

$[L;\vee ,\wedge ]$为任意格，则下述条件等价

1. $\forall a,b,c\in L,a\wedge (b\vee c)=(a\wedge b)\vee (a\wedge c)$
2. $\forall a,b,c\in L,a\vee (b\wedge c)=(a\vee b)\wedge (a\vee c)$
3. $\forall a,b,c\in L,(a\wedge b)\vee (b\wedge c)\vee (c\wedge a)=(a\vee b)\wedge (b\vee c)\wedge (c\vee a)$
4. 不含$M_5$或$N_5$同构的子格