证明(构造性证明方法)
定理5.4.3 设
定理5.4.4 设
定理5.4.5 设
定理5.4.6 (原子表示定理) 设
x= a1⊕a2⊕…⊕an
且如不计原子的出现顺序则这样的表示方式是唯一的。 证明(记y= a1⊕a2⊕…⊕an求证y=x)
定理5.4.7(Stone表示定理)
f(x)=
?，if x=0;
f(x)={a|a∈A∧a≤x}(即所有满足a≤x的原子集合) if x≠0;
推论 有限布尔代数的基数一定为2的幂次;
6
5.5 布尔代数Br2
用Bn表示具有n个元素的布尔代数
Br2= B2×B2×…×B2=< Sr2，⊕，⊙，′，0r，1r>; 其中0r=<0，0，…，0>，1r=<1，1，…，1>，且 ⊕
?
，
定理5.5.1 1) Br2是一个布尔代数，
2) 布尔代数< S2r，⊕，⊙，′，0，1>与Br2同构; 3) 任一有限布尔代数都同构于一个布尔集合代数;
5.6 布尔表达式及其范式定理
布尔代数可用于逻辑电路的设计。具有若干输入和某种逻辑功能的组合线路可以用一个定义在电路代数上的电路函数表示，而一个电路函数则可以用布尔表达式来表示。
定义5.6.1 设< S，⊕，⊙，′，0，1>为布尔代数，则S中的元素称为布尔常元; 取值于S中的变元称为布尔变量(Boole Variable)。
定义5.6.2 设< S，⊕，⊙，′，0，1>为布尔代数，x1，x2，…，xn为布尔变元，则由这n个布尔变元产生的布尔表达式(Boole
7
Expression)可递归定义如下:
1) S中的任何元素和变元为一个布尔表达式;
2) 若F和G都是布尔式，则F′，F⊕G，F⊙G也是布尔式; 3) 只有有限次使用1)或2)构造而成的符号串才是一个布尔式; (a)为了简便起见，规定⊕的运算优先级低于⊙
例5.6.1 在布尔代数<{0，1，?,? }，⊕，⊙，′，0，1>中，布尔式有0⊙1′，1⊕(?⊙x1) ⊕(x2′⊙x3)，(?′⊕x1⊕x3) ⊙1。
(b) 任一n元布尔式都可定义为是一个从Sn到S的一个函数; 例5.6.2 在布尔代数<{0，1，⊕，⊙，′，0，1>中，f(x,y)=(? ?,? }，⊙x′⊙y) ⊕(? ⊙x⊙(x⊕y′))是一个二元布尔函数。
(c) 两个布尔式相等:
布尔表达式f(x1，x2，…，xn)的值是将S中的元素作为x（2，…，ii=1，n）的值代入表达式以后计算出来的表达式的值;
若对n个布尔变元的任意指派(即给每个变元取上S中的元素)，两个布尔表达式的值均相等，则称这两个布尔表达式是相等或等价的。
定义5.6.3 设x1，x2，…，xn为n个布尔变元，则n元布尔式
ix1?1⊙x?22⊙…⊙xn?
n(其中xi?= xi if
?i=1，xi?i= xi′if ?i=0，i=1，2，…，n)称之为由x1，
m?1?2...?nx2，…，xn产生的n元小项(极小项，Minterm)，用
=
xi?1表示它; 相
应地可定义由x1，x2，…，xn生成的n元大项(极大项，Maxterm):
M?1?2...?nix1?i⊕x?22⊕…⊕xn?
n(xi?=xi if ?i=0， m0，m1，…，m
=xi′ if ?i=1)
注 1) 关于x1，x2，…，xn有2n个不同的小项(大项);
2?1n(m00…0，m00…1，…，m11…1)
8
M0，M1，…，M
2?1n(M00…0，M00…1，…，M11…1)
2) 任何两个不同小项的布尔积(⊙)为0，任何两个不同大项的布尔和(⊕)为1; 所有不同小项的布尔和为1;所有不同大项的布尔积为0; 3) 大项(小项)的补是一个小项(大项);
例5.6.3 x⊙y′⊙z′，x′⊙y⊙z为三元小项; x⊕y′⊕z′，x′⊕y⊕z为三元大项; 而x⊙y⊙y′⊙z′不是三元小项，x′⊕y⊕x⊕z不是三元大项;
定义5.6.4 形为(α0⊙m0)⊕(α1⊙m1)⊕…⊕(?M0)⊕(α1⊙M1)⊕…⊕(?常元。
注 不同的主析(合)取范式有|S|个。
2
n2?1n⊙m2?1n)的布尔表
达式称为主析取范式(Principal Disjunctive Normal Form); 形为(α0⊙
2?1n⊙M2?1n)的布尔表达式称为主合取范式
(Principal Conjunctive Normal Form); 其中αi(i=0，1，…，2n-1)为布尔
定理5.6.1(范式定理) 在布尔代数< S，⊕，⊙，′，0，1>中每个n元布尔表达均可表示成:
f(x1，x2，…，xn)= ⊕k (ck⊙mk) 其中k=δ1δ2…δn f(x1，x2，…，xn)= ⊙l (dl⊕Ml) 其中l=σ1σ2…σn 其中ck= f(δ1，δ2，…，δn)，dl= f(σ1，σ2，…，σn)
例5.6.4 在布尔代数<{0，1，⊕，⊙，′，0，1>中，f(x,y)=(? ?,? }，⊙x′⊙y) ⊕(? ⊙x⊙(x⊕y′))的主析取范式为
例5.6.5 在布尔代数<{0，1，⊕，⊙，′，0，1>中，f(x,y)=(? ?,? }，⊙x′⊙y) ⊕(? ⊙x⊙(x⊕y′))的主合取范式为
9
定义5.6.5 在布尔代数< S，⊕，⊙，′，0，1>中，一个S上的n元函数，如果能表示成n元布尔表达式，则称之为布尔函数。 特别地当S={0，1}时，即二值布尔代数S上的n元布尔式均是布尔函数。其中二值布尔式的主析(合)取范式就是小(大)项的布尔和(积)。
如何求一个二值布尔式的主析取范式和主合取范式: 1) 列表法
当f(δ1，δ2，…，δn)=1，则对应小项m??12...?n在f的主析取范式
12中出现; 当f(δ1，δ2，…，δn)=0时，则对应小项m??析取范式中不出现;
当f(σ1，σ2，…，σn)=0，则对应大项 取大项范式中不出现;
M?1?2...?n...?n在f的主
在f的主合取范
在f的主合
式中出现;当f(σ1，σ2，…，σn)=1，则对应大项
M?1?2...?n注 同一布尔式的主合取范式中大项的项数和主析取范式中小项的项数之和等于2n。 2) 布尔代数性质法
例5.6.6 在二值布尔代数中，求下列布尔式的主析(合)取范式： (1) (x⊙y) ⊕z′ (2) x⊙y
注 若f的主析取范式为g，则f′的主析取范式就是2n个小项中不在g中出现的小项的布尔和h，且h′就是f的主合取范式;反之，若f的主合取范式为g，则f′的主合取范式就是2n个大项中不在g中出现的大项的布尔积h，且h′就是f的主析取范式;
布尔式的范式定理与布尔式的简化在电子线路中的应用:
二值布尔代数可用于逻辑电路的设计。具有若干输入和某种逻辑功能的组合线路可以用一个定义在电路代数上的电路函数表示，而一
10