当前位置：首页 > news >正文

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

news 2025/7/9 6:28:26

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,\preceq)$ 为偏序集，如果任意的$a,b\in L $有最小上界与最大下界时，称$ L $为 ‘ 格 ‘ ，以$ a\lor b = lub(a,b) $(l e a s t u pp er b o n d) 表示$ a,b $的最小上界，$ a\land b =glb(a,b) $（ g re a t es tl o w er b o n d) 表示$ a,b$的最大下界。

定义2 覆盖

$(L,\preceq)$ 为格，如果 $a\preceq b,a\neq b$ （记为 $a\prec b$ ），且不存在 $u\in 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,\preceq)$ 为格，则对任意 $a,b\in L$ 有

$a\prec a\lor b ,a\land b \prec a$
$a\preceq b \Longleftrightarrow a\lor b =b$
$a\preceq b \Longleftrightarrow a\land b = a$

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

定理2 格的运算律

幂等律： $a\land a = a, a\lor a = a$
交换律： $a\lor b=b\lor a,a\land b=b\land a$
结合律： $a\lor(b\lor c)=(a\lor b )\lor c,a\land(b\land c)=(a\land b)\land c$
吸收律： $a\lor(a\land b)=a,a\land(a\lor b)= a$

P211

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

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

在 $[L;\lor,\land]$ 中二元关系 $\lor,\land$ 满足上述4条运算律，则 $\forall a,b\in L ,a\land b= a\Longleftrightarrow a\lor 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\lor b =b\Rightarrow a\land b = a\land(a\lor b )=a$

引理2 通过L构造偏序集

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

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

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

证明 $a\lor b = lub(a,b),a\land b = glb(a,b)$ P211

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

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

定理4 保序性

格 $[L;\lor,\land],\forall a,b,c\in L$ ,当 $b\preceq c$ 时有 $a\land b \preceq a\land c$ 及 $a\lor b\preceq a\lor c$

定义5 子格

$[L;\lor,\land]$ 为格， $T\neq\varnothing,T\subseteq L$ , $T$ 关于 $\lor,\land$ 封闭(即 $a,b\in T,a\lor b \in T,a\land b \in T$ )时，称 $T$ 为 $L$ 的子格

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

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

定义6 格的同态与同构

设 $[L;\lor,\land]$ 与 $[S;+,\circ]$ 为两个格，如果存在映射 $\varphi:L\rightarrow S，\forall a,b\in L$ ,有
$\varphi(a\land b )=\varphi(a)\circ\varphi(b)\\ \varphi(a\lor b)=\varphi(a)+\varphi(b)$
则称 $\varphi$ 为 $L$ 到 $S$ 的同态映射，当 $\varphi(L)=S$ 时(满射)，则说两个格同态，当 $\varphi$ 是一一对应(双射),说同构。如果 $L = S$ ,则称为自同态和自同构。

定理 5 同态映射是保序的

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

定理6 同构映射的保序性

$a\preceq b \Longleftrightarrow \varphi(a)\preceq\varphi(b)$

定理7 对偶原理

设 $P$ 是对任意偏序集都为真的一个命题， $P^{'}$ 是将 $P$ 中所有 $\preceq,\succeq$ 对换得到的对偶命题，则 $P^{'}$ 对任意偏序集也为真
设 $P$ 是从格 $[B;\lor,\land]$ 推出的命题， $P^{'}$ 是将 $P$ 中 $\lor$ 与 $\land$ 对换得到的对偶命题，则 $P^{'}$ 对格 $[B;\land,\lor]$ 也为真

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

16.2 有补格及分配格

定义7 有界格

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

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

有界格中， $\forall a\in L:a\lor 1 =1,a\land 0 =0,a\land 1 =a,a\lor 0 =a$

定义8 有补格

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

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

$a\lor (b\land c)\preceq (a\lor b)\land(a\lor c)$
$KaTeX parse error: Undefined control sequence: \and at position 34: …and c)\preceq a\̲a̲n̲d̲(b\lor c)$

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

定义9 分配格