离散数学左孝凌-格和布尔代数

格和布尔代数复习

主要框架

格的定义以及性质#

定义：

格：设\(<S, \preccurlyeq>\)为一个偏序集，若对任意两个元素都可以找到一个最小上界和最大下界，那么称此偏序集为格。

规定：

\(\and\)表示最小上界

\(\or\) 表示最大下界

对偶命题：将所有的符号换成相反的符号的命题为对偶命题，大于等于变小于等于。对偶命题与原命题具有等价性。

格的二元关系定义：若\(<S, *, \circ>\)满足2格二元关系，满足交换律，结合律，吸收律，幂等律，则可以定义偏序，从而有格。

定理：

11.1.1：格满足交换律，结合律，幂等律，吸收律。（格的本质是继承于偏序关系，只不过为了保证格的封闭性，要求最小上界最大下界必须存在。）

其余的一些定理，基本上就和初中学过的比大小的定理基本一致，直接跳过。

分配格，有补格与布尔代数#

就和定义环时的特殊环一样，格作为比环性质更加丰富的结构，也会出现很多特殊的格

定义：

分配格：满足分配律的格,注意是取上界与取下界都有分配律。

有界格：对于取上界运算\(\and\)存在零元，对于取下界运算\(\or\)存在零元，也就是说存在最大最小值（全局的）。

补元：若对于格两个元素\(a, b\)若\(a\and b = 1\), \(a\or b = 0\)那么称这两个元素互为补元。

有补格：每一个元素都存在补元，的格则称为有补格，

布尔代数：继承与有阶分配格的有补格称为布尔代数（有补分配格）

满足交换律，分配律，同一律，补元律的代数系统为一个布尔代数。

原子：最接近格中加法单位元的元素为原子。

\[设L是格，0\in L, a\in L, 若\forall b\in L\\ 0\prec b\preccurlyeq a\Leftrightarrow a = b \]
\(a为L中原子\)

定理：

11.2.1：L是分配格，当且仅当L中不存在与钻石格和五角格同构的子格。

推论：

小与5元的格都是分配格。

任何一条链是分配格。

11.2.2:有界分配格，若元素存在补元，那么补元唯一。

11.2.3：布尔格符合双重否定律与德摩根律，（补元的唯一性，补元的定义）

11.2.4：有限布尔代数表示定理：设B是有限布尔代数，A是B的全体原子构成的集合，B同构于A的幂集代数\(P(A)\)

推论：

所有有限布尔代数的基为\(2^n\)

等势的有限布尔代数同构。