格，模格，分配格

偏序与格
定义. 设\((P,\le)\)是一个偏序集。如果P中任意两个元素都有上、下确界，称P关于\(\le\)构成一个格。
用\(a\bigcup b, a\bigcap b\)分别表示\(\{a,b\}\)的上、下确界。

格的基本性质：
(1) \(a\cap b \le a\le a\cup b\).
(2) \(a\le c, b\le d \Rightarrow a\cup b\le c\cup d, a\cap b \le c\cap d\).
(3) \(a\le b \Leftrightarrow a\cap b = a \Leftrightarrow a \cup b=b\).

对偶原理：设P是对任意格都成立的命题。将P中\(\le\leftrightarrow \ge, \cup\leftrightarrow \cap\)分别互换得到命题\(P'\)， 则P'对任意格也成立。

定理1. 设\((L,\le)\)是格，\(a,b,c\in L\).
(L1) \(a\cap a=a\cup a= a\);
(L2) \(a\cap b = b\cap a, a\cup b = b\cup a\);
(L3) \((a\cap b)\cap c = a\cap (b\cap c), (a\cup b)\cup c = a\cup (b\cup c)\).
(L4) \(a\cap(a\cup b) = a\cup (a\cap b)= a\).

n元运算与代数系统
定义. 称\(f:A^n\to A\)为A上的一个n元运算。
定义. \(f_1,\cdots, f_s\)是A上的\(k_1,\cdots,k_s\)元运算。称\((A;f_1,\cdots,f_s)\)为一个代数系统（代数结构）。

定理2. 设代数系统\((S;\cup,\cap)\)中的二元运算\(\cup,\cap)\)适合(L2,L3,L4). 则可以在S上构造一个偏序，使\((S,\le)\)是格。
构造：\(a\le b \Leftrightarrow a\cup b = b\).
定理2可视为格的等价定义。

定义. 若格L的任意非空子集都有上确界和下确界，称L为完全格。

子格，同态与同构
定义. 设\((A;f_i)\)是代数系统。若非空\(B\subseteq A\)关于任意代数运算\(f_i\)都是封闭的， 称\((B;f_i)\)是一个子代数系统。

定义. 设\((S;\cup, \cap)\)是一个格，T是S的非空子集。若T对于S中的交并运算都是封闭的，则称T是S的子格。
注意，这里要求交并运算与S中的一致。因为T中两元素的上/下确界未必与在S中的上下确界相同。

定义.
(1) 在两个代数系统\((A;f_1\cdots f_s), (B;g_1\cdots g_s)\)中，如果\(f_i,g_i\)的运算元数、代数常数的个数都相同，则称这两个代数系统是同类型的。
(2) 设\(A,B\)是两个同类型的代数系统，\(\varphi:A\to B\)满足\(\forall 1\le i\le s\), \[\varphi(f_i(a_1,\cdots ,a_k)) = g_i(\varphi(a_1),\cdots, \varphi(a_k))\]称\(\varphi\)是同态映射。当其为单射、满射、双射时，分别称为单同态、满同态、同构。
(3) 设\(S,S'\)为格，\(\varphi:S\to S'\). 如果\(\forall x, y\in S,\)\[\varphi(x\cup y) = \varphi(x)\cup \varphi(y),\ \ \varphi(x\cap y) = \varphi(x)\cap \varphi(y)\]称\(\varphi\)是格S到格S'的同态映射。
(4) 如果格映射\(\varphi:S\to S'\)满足\(\forall x, y\in S\), \[x\le y\Rightarrow \varphi(x)\le\varphi(y)\]称\(\varphi\)是保序映射。

定理3. 格同态映射保序。
定理4. 设\(\varphi\)是格双射。则\(\varphi\)是个同构的充要条件是\(\forall a, b\in S,\)\[a\le b\Leftrightarrow \varphi(a)\le \varphi(b).\]

模格，分配格，有补格
定义(分配格). 设格S，满足\(\forall a,b,c\in S,\)有\[a\cup(b\cap c) = (a\cup b)\cap (a\cup c),\]\[a\cap(b\cup c) = (a\cap b)\cup(a\cap c).\] 称S是分配格。

定理5. 对任意格S，有
(1) \(a\cup (b\cap c) \le (a\cup b)\cap (a\cup c), a\cap (b\cup c)\ge (a\cap b)\cup (a\cap c)\).
(2) \(a\le c\)时，\(a\cup (b\cap c) \le (a\cup b)\cap c\).（模不等式）

定义(模格). 设格S满足\(a\le c\)蕴含\[a\cup(b\cap c) = (a\cup b)\cap c\]称S为模格。

性质6. 分配格是模格。
定理7 格S是模格的充要条件是\(\forall a,b\in S,\)只要满足
(1)\(a\le b\)
(2) \(\exists c, a\cup c=b\cup c, a\cap c=b\cap c\)
就有\(a=b\)。

定理8. 格S是模格的充要条件是，S不含与\(M_5\)同构的子格。
\(M_5 = \{a,b,c,e,f\}, f\ge b\ge a\ge e, f\ge c\ge e.\)

定理9. 分配格的性质。设S是格，以下命题等价：
(1) \(\forall a,b,c\in S, a\cap(b\cup c) = (a\cap b)\cup (a\cap c)\)
(2) \(\forall a,b,c\in S, a\cup(b\cap c) = (a\cup b)\cap (a\cup c)\)
(3) \(\forall a,b,c\in S, (a\cap b)\cup(b\cap c)\cup (c\cap a)=(a\cup b)\cap(b\cup c)\cap (c\cup a)\)

定理10. 格S是分配格的充要条件是S不含与\(M_5,\)或\(N_5\)同构的子格。
\(N_5=\{a,b,c,e,f\}, f\ge a,b,c\ge e.\)

定理11. 格S是分配格的充要条件是\(\forall a,b\in S, \) 若存在c满足\(a\cup c=b\cup c, a\cap c=b\cap c\)可以推出\(a=b\).

定理12. 分配格的广义分配律。在分配格S中，\[(\bigcap a_i)\bigcup (\bigcap b_j) = \bigcap\bigcap(a_i\bigcup b_j)\]其对偶命题也成立。

定义(有界格) 若格S存在最大元和最小元，则称S为有界格。以0和1分别代表其最大/最小元。
定义(补元与有补格)
(1) a的补元b满足\(a\cup b = 1, a\cap b = 0\). a称为有补元。
(2) 有界格S中，每个元素都有补，称S为有补格。

定理13. 若格S有补且分配，则补元唯一。

    所属分类：离散数学     发表于2022-03-27