布尔代数

布尔代数
定义. 有补分配格称为布尔代数（布尔格）。布尔代数中，元素a的补元记为\(\bar a\).
基本性质：
(1) \(\bar{\bar a} = a\).
(2) \(\overline{a\cup b} = \bar a \cap \bar b\), 对偶命题也成立。
(3) \(a \le b \Leftrightarrow a\cap \bar b = 0\Leftrightarrow \bar a \cup b = 1\).
(4) 幂等律，交换律，结合律，吸收律，分配律，零一律，互补律，对合律，摩根律。
定理14. 如果代数系统\((B;\cup,\cap, \bar{\ }, 1, 0)\)满足：
(1) 交换律； (2) 分配律；(3) 零一律；(4) 互补律，则为一个布尔代数。

定义. 如果布尔代数的子集\(T\subseteq B\)含有\(\{0,1\}\), 关于B的两个二元运算\(\cap, \cup\)和一元运算 \(\bar{\ }\) 都是封闭的，则称T是B的子布尔代数。

定理1. T是B的子布尔代数的充要条件是，T对B的\(\bigcup,\bigcap, \bar{\ }\) 封闭。

同态与同构
定义. 设\(B, B'\)是两个布尔代数，\(f:B\to B'\)满足格同态(保并性，保交性)，保补性\(f(\bar{a})=\overline{f(a)}\), 则称f是同态映射。
布尔代数的单同态、满同态和同构可类似定义。

有限布尔代数与原子
定义. 设B是布尔代数，\(a\in B, a\ne 0\), 小于a的元素只有0. 则称a是B中的一个原子。

引理2. 设B是有限布尔代数。
(1) \(\forall x\in B-\{0\},\) 存在B中原子a使得\(a\le x\).
(2) B中任意两原子\(a_1,a_2\), 必有\(a_1\cap a_2=0\)或\(a_1=a_2\).
(3) 对B中任一原子a和任意元素b，\(a\le b\)和\(a\le \bar b\)恰有一个成立。

引理3. 设B是有限布尔代数。b是B中非零元，\(a_1,\cdots,a_t\)是B中所有\(\le b\)的原子。则
(1) \(b = a_1\bigcup\cdots\bigcup a_t\);
(2) 分解式唯一。

定理4（Stone表示定理） 设B是有限布尔代数，\(S=\{a_1,\cdots , a_n\}\)是原子集。则B与\(\rho(S)\)同构。

推论5. 有限布尔代数B的元素数目是\(2^n, n=|S|.\)
推论6. 元素数目相同的有限布尔代数同构。

布尔环
在布尔代数B上定义两个运算：
\(a+b = (a\cap \bar b) \cup (\bar a \cap b)\),
\(a\cdot b = a \cap b\). 则B关于这两个运算构成一环。乘法单位元为最大元1.

定义. 含有单位元的环R若满足\(\forall a \in R, a^2 = a\). 则称R为布尔环。
定理7. 布尔环R是交换环，且\(\forall a, 2a=0\).
定理8. 在布尔环R上定义\(\cup, \cap, \bar{\ }\)如下：
\(a\cup b = a+ b-a\cdot b, a\cap b=a\cdot b, \bar{a} = 1-a.\)
则\((B;\cup, \cap, \bar{\ }, 1,0)\)是一个布尔代数。

布尔表达式
定义. 设\(x_1,\cdots, x_n\)是n个变量，B是一个布尔代数。则
(1) B中任何一个元素是一个布尔表达式；
(2) 任何一个变量\(x_i\)是一个布尔表达式；
(3) \(E_1, E_2\)是布尔表达式，则\(\bar{E_1}, E_1\bigcap E_2, E_1\bigcup E_2\)也是布尔表达式。
(4) 除有限次使用以上三种法则外，无其他布尔表达式。
一般地，用\(E(x_1,\cdots,x_n)\)表示一个可含有n个变元的布尔表达式，称为n元布尔表达式。
每个n元布尔表达式确定了\(B^n\to B\)的一个函数，称为布尔函数。

定理9. 对于布尔代数\(B=\{0,1\}\), 任何从\(B^n\to B\)的函数都是布尔函数。

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