1
6-4 布尔代数定义 6-4.1 一个有补分配格称为 布尔格 。
求一个元素的补元素可以看作一元运算，称为补运算。
定义 6-4.2 设 <A,∨,∧,- > 是由布尔格 <A,≤ >
是所诱导的代数系统。称这个代数系统为 布尔代数 。
例 1 设 <?(S),∪,∩,~>是由布尔格 <?(S),?>
是所诱导的代数系统。这个代数系统为 布尔代数 。
当 S={a,b}时的运算表如表 6-4.1所示。 P-253页
2
3
定理 6-4.1 在一个有界分配格中，对于布尔代数中的任意两个元素 a,b，必定有
( a )=a
a∨ b= a∧ b
a∧ b= a∨ b
证明,只证第 (2)个等式先证互补的两个式子 相并 等于全上界,1”。
(a∨ b)∨ (a∧ b)= ((a∨ b)∨ a)∧ ((a∨ b)∨ b)
=(b∨ (a∨ a))∧ (a∨ (b∨ b))
=(b∨ 1)∧ (a∨ 1) =1
再证互补的两个式子 相交 等于全下界,0”。
(a∨ b)∧ (a∧ b)= 0?
4
定义 6-4.3 具有有限个元素的布尔代数称为 有限 布尔代数 。
定义 6-4.4 设 <A,∨,∧,- >和 <B,∨,∧,- >是两个布尔代数,如果存在着 A到 B的双射 f,对于任意的 a,b?A,
都有
f(a∨ b)=f(a)∨ f(b)
f(a∧ b)=f(a)∧ f(b)
f(a)=f(a)
则称 <A,∨,∧,- >和 <B,∨,∧,- >同构 。
可以证明,对于每一正整数 n,必存在着 2n个元素的布尔代数 ;反之,任一有限布尔代数,它的元素个数必为 2的幂次。
5
定义 6-4.5 设 <A,≤ > 是一个格，且具有全下界 0，
如果有元素 a盖住 0，则称元素 a为原子。
原子：与 0相邻且比 0“大”
定理 6-4.2 设 <A,≤ > 是一个具有全下界 0的有限格，
则对于任何一个非零元素 b（即不等于全下界 0的元素）
至少存在一个原子 a，使得 a ≤ b 。
证明,若 b是原子，则有 b ≤ b,若 b不是原子，则必有 b1存在，使得 0?b1?b
若 b1是原子，则定理得证，否则，必存在 b2使得
0?b2?b1?b
由于 <A,≤ >是一个有下界的有限格，所以通过有限不骤总可以找到一个原子 bi,使得 0?bi?...?b2?b1?b?
6
引理 6-4.1 设在一个布尔格中,b∧ c=0当且仅当 b ≤c。
证明,(1)先证 b∧ c=0? b ≤ c
若 b∧ c=0,因为 0∨ c=c,
则 (b∧ c)∨ c=c
根据分配性，就有
(b∨ c) ∧ (c∨ c) =c
即 (b∨ c) ∧ 1 =c
所以 b∨ c =c
又因为 b ≤ b∨ c
所以 b ≤ c
(2)再证 b ≤ c? b∧ c=0
若 b≤c,则 b∧ c?c∧ c,即 b∧ c?0,所以 b∧ c=0?
7
证明,(1)先证 a1∨ a2∨ …∨ ak ≤ b
记 a1∨ a2∨ …∨ ak =c,因为 aj ≤ b,所以 c ≤ b。
(2)再证 b ≤ a1∨ a2∨ …∨ ak
由引理 6-4.1知,要证 b≤c若是原子,只需证 b∧ c=0,
反设 b∧ c≠ 0,于是必有一个原子 a,使得 a≤b∧ c。
又因 b∧ c≤b,和 b∧ c≤c,所以 a≤b 和 a≤c,
因为 a是原子,且 a≤b,所以 a必是 a1,a2,…,ak中的一个,因此 a≤c,已有 a≤c,得 a≤c∧ c,即 a≤0,与 a是原子矛盾。
b∧ c≠ 0假设不成立 。综合 (1)和 (2)定理得证。
引理 6-4.2 设 <A,∨,∧,- >是一个有限布尔代数,若
b是 A中 任意非零元素,a1,a2,…,ak是 A中满足 aj≤b
的所有原子（ j=1,2,…,k）,则
b = a1∨ a2∨ …∨ ak
8
引理 6-4.3 设 <A,∨,∧,- >是一个有限布尔代数,若 b
是 A中 任意非零元素,a1,a2,…,ak是 A中满足 aj ≤b的所有原子（ j=1,2,…,k）,则 b = a1∨ a2∨ …∨ ak是将 b表示为原子之并的唯一形式。
证明,设有另一种表示形式为 b=aj1∨ aj1∨ …∨ ajt
其中 aj1,aj1,…,ajt是原子。因为 b是 aj1,aj1,…,ajt的最小上界,所以必有 aj1 ≤ b,aj2 ≤ b,...,ajt ≤ b。而 a1,a2,…,ak是 A
中所有满足 ai ≤ b （ i=1,2,…,k）的不同原子。
所以必有 t≤k
反设 t?k,那么在 a1,a2,…,ak中必有 aj0且 aj0≠ ajl
于是,由 aj0∧ (aj1∨ aj1∨ …∨ ajt)= aj0∧ (a1∨ a2∨ …∨ ak)
即 (aj0∧ aj1)∨ (aj0∧ aj2)∨ … ∨ (aj0∧ ajt)
= (aj0∧ a1)∨ (aj0∧ a2)∨ … ∨ (aj0∧ ak)
导致的 0= aj0矛盾。 t?k假设不成立 。 T=k定理得证。
9
引理 6-4.4 在一个布尔格 <A,?>中,对 A中 任意一个原子 a和另一个非零元素 b,a?b和 a?b两式中有且仅有一式成立。
证明,(1)先证 a?b和 a?b两式 不可能同时成立反设 a?b和 a?b同时成立，就有 a?b∧ b=0，这与 a是原子相矛盾，即 a?b和 a?b不 同时成立。
(2)再证 a?b 和 a?b两式中 必有一式成立因为 a∧ b?a,a是原子,所以只能是
a∧ b=0 或 a∧ b=a
若 a∧ b=0，则 a∧ (b) =0,由引理 6-4.1得
a?b；
若 a∧ b=a,由引理 6-1.6得 a?b。
10
定理 6-4.3(Stone 表示定理 ) 设 <A,∨,∧,- > 是由有限布尔格 <A,?>所诱导的一个有限布尔代数,S是布尔格中的所有原子的集合，则 <A,∨,∧,->和 <?(S),
∪,∩,~>同构。
证明,本定理的证明过程分三部分
(1)构造一个映射，并证明它是双射（既是入射又是满射）；
(2)描述代数系统 <A,∨,∧,- >和 <?(S),∪,∩,~>
同构并证明之；
(3)总结概括结论。
11
第 (1)部分 证明,对于任意非 0a?A,必有的唯一表示：
a=a1∨ a2∨? ∨ ak （引理 6-4.2a的原子表示）
其中 ai?a （ i=1,2,…,k）,作映射 f(a)=S1 = {a1,a2,…,ak}
那么，这个映射是 一个从 A到?(S)的一个双射。
第 1部分 双射证明：
,对于全下界 0?A，规定 f(0)=? 。
.如果 S1 ={a1,a2,…,ak}(S)，而有 a,b?A,使得
f(a)= f(a)=S1,则 a=a1∨ a2∨? ∨ ak = b，
所以 f是一个从 A到?(S)的一个入射。
.对于任一个 S1(S)，若 S1 ={a1,a2,…,ak}，则由于运算 ∨ 的封闭性，所以
a1∨ a2∨? ∨ ak = a?A
这就说明?(S)中任一元素，必是 A中某个元素的象，所以是一个从 A到?(S)的一个满射。
第 1部分 双射证明完毕。
12
第 (2)部分 证明,<A,∨,∧,- >和 <?(S),∪,∩,~>同构
第 2部分 同构性格证明：
,设 f(a∧ b)=S3,若 x?S3,则 x必是满足 x?a∧ b的原子，因为 a∧ b?a和 a∧ b?b，所以 x?a且 x?b，推得 x?S1
= f(a)且 x?S2 = f(b),即 x?S1∩ S2,这就证得
S3? S1∩ S2 。
反之,若 x?S1∩ S2,则 x?S1且 x?S2,所以 x必是满足 x?a
和 x?b的原子,推得 x必是满足 x?a∧ b的原子,所以 x?S3,这就证明了 S1∩ S2?S3 。
综上所述，就有 S3 = S1∩ S2,即
f(a∧ b)= f(a)∩ f(b)
13
,设 f(a∨ b)=S3,若 x?S3,则 x是满足 x?a∨ b的原子，所以必有 x?a或 x?b，这是因为：
若 x?a且 x?b,则由引理 6-4.4可知必有 x?a且 x?b,所以 x?a∧ b= a∨ b 。再由条件 x?a∨ b,便得
x? (a∨ b)∧ (a∨ b)=0
这与 x是原子相矛盾。
因此，若 x?a则 x?S1或者若 x?b则 x?S2，所以
x? S1∪ S2
这就证明了 S3? S1∪ S2 。
反之,若 x?S1∪ S2,则 x?S1或 x?S2,若 x?S1，则
x?a? a∨ b
所以 x?S3,同理，若 x?S2，则 x?b? a∨ b
所以 x?S3,这就证明了 S1∪ S2?S3 。
综上所述，就有 S3 = S1∪ S2,即
f(a∨ b)= f(a)∪ f(b)
14
.最后证明同构性的 f(a)= f(a)式：
将 S看作全集,另 f(a)=S1,则 f(a)=S-S1=S-f(a),可以证明 x?f(a)当且仅当 x?a,这是因为,若 x?f(a),必有 x?a,则由引理 6-4.4可知必有 x?a,反之,若原子 x满足 x?a,则必有 x?a,所以 x?f(a) 。
还可以证明,对于原子 x,x?a当且仅当 x?f(a),这是因为,若 x?a而 x?f(a),将导致 x?a的矛盾,所以 x?f(a),反之,若 x?f(a)而 x?a,也将导致 x?f(a)的矛盾,所以 x?a 。
另外还可以证明,x?f(a)当且仅当 x?f(a),所以,对于原子 x,x?f(a)当且仅当 x?f(a),因此,
f(a)=f(a) 第 2部分 同构性证明完毕。
(3)总结概括结论,<A,∨,∧,->和 <?(S),∪,∩,~>同构。
推论 6-4.1 有限布尔格的元素个数必定等于 2n，其中 n
是该布尔格中所有原子的个数。
推论 6-4.2 任何一个具有 2n个元素的有限布尔代数都是同构的。
15
6-5 布尔表达式定义 6-5.1 设 <A,∨,∧,->为布尔代数,如下递归地定义 A上 布尔表达式 (Boolean expressions)：
（ 1） 布尔常元 (取值于 A的常元 )是布尔表达式,布尔常元常用 a,b,c等符号表示。
（ 2） 布尔变元 (取值于 A的变元 )是布尔表达式，布尔变元常用 x,y,z等符号表示。
（ 3） 如果 e1,e2为布尔表达式，那么
(e1),(e1∨e 2),(e1∧e 2) 也是布尔表达式。
（ 4） 除有限次使用条款（ 2），（ 3）生成的表达式是布尔表达式外，没有别的是布尔表达式。
例 1 给出了两个布尔函数的例子,见表 6-5.1和 6-5.2。
例 2 给出了布尔表达式的例子,见 P-262页。
16
定义 6-5.2 一个含有 n个相异变元的布尔表达式，
称为含有 n元的布尔表达式，记为 E(x1,x2,?,x n)，
其中 x1,x2,?,x n为 变元。
定义 6-5.3 布尔代数 <A,∨,∧,->上的一个含有 n
元的布尔表达式 E(x1,x2,?,x n)的值是指：将 A中的元素作为变元 xi(i=1,2,?,n) 的值来代替表达式中相应的变元（即对变元赋值）,从而计算出表达式的值。
定义 6-5.4 布尔代数 <A,∨,∧,->上两个 n元的布尔表达式为 E1(x1,x2,?,x n)和 E2(x1,x2,?,x n),
如果对于 n个变元的任意赋值 xi=xi’,xi’?A时均有
E1(x1’,x2’,?,x n’ )=E2(x1’,x2’,?,x n’ )
则称这两个 布尔表达式 是等价的。
17
例 4 布尔代数 <{0,1},∨,∧,->上两个 3元的布尔表达式为 E1(x1,x2,x3)=(x1∧x 2)∨(x 1∧x 3)
和 E2(x1,x2,x3)=x1∧(x 2∨x 3)
验证这两个布尔表达式是等价的。
E1(0,1,1)=(0∧1)∨(0∧0)=0
E2(0,1,1)=0∧(1∨0)=0
E1(1,1,1)=(1∧1)∨(1∧0)=1
E2(1,1,1)=1∧(1∨0)=1
E1(0,0,0)=(0∧0)∨(0∧1)=0
E2(0,0,0)=0∧(0∨1)=0
等等 (全部赋值状况共 8种需要验证。 )。
结论：一个 n元布尔表达式确定一个从 An到 A的函数。
定义 6-5.5 设 <A,∨,∧,->为布尔代数,一个从 An到 A
的函数，如果它能够用 <A,∨,∧,->上的一个 n元布尔表达式 E(x1,x2,?,x n)来表示，那么，称此函数为 布尔函数 。
18
定理 6-5.1 对于两个元素的布尔代数 <{0,1},∨,∧,->,
任何一个从 {0,1}n到 {0,1}的函数,都是布尔函数。
证明,n元布尔表达式若有 x1’ ∧x 2’ ∧?∧x n’ 形式 (其中 xi’ 是 xi或 xi中的任一个 ),则称它为 小项,若一个布尔表达式能表示成 小项的并,则称它为 析取范式 。对于一个从
{0,1}n到 {0,1}的函数,先用那些使函数值为 1的有序 n元组分别构造小项，其中
xi 若 n元组中第 i个分量为 1
xi 若 n元组中第 i个分量为 0
由这些小项构成的析取范式就是原函数对应的布尔表达式。
xi’ =
例 5 对于表 6-5.3定义的函数写出布尔表达式的析取范式。
第 1步：利用函数值为 1的所有行写出小项；
第 2步：写出小项的析取式。
19
n元布尔表达式若有 x1’ ∨x 2’ ∨?∨x n’ 形式 (其中 xi’
是 xi和 xi中的任一个 ),则称它为 大项,若一个布尔表达式能表示成 大项的交,则称它为 合取范式 。对于一个从 {0,1}n到
{0,1}的函数,先用那些使函数值为 0的有序 n元组分别构造大项，其中
xi 若 n元组中第 i个分量为 0
xi 若 n元组中第 i个分量为 1
由这些大项构成的合取范式就是原函数对应的布尔表达式。
对于表 6-5.3定义的函数写出布尔表达式的合取范式。
第 1步：利用函数值为 0的所有行写出大项；
第 2步：写出大项的合取式。
定理 6-5.5 布尔代数 <A,∨,∧,->上的任意一个 n元布尔表达式 E(x1,x2,?,x n)一定能写成析取范式（合取范式）。
证明,略?
xi’ =
6-4 布尔代数定义 6-4.1 一个有补分配格称为 布尔格 。
求一个元素的补元素可以看作一元运算，称为补运算。
定义 6-4.2 设 <A,∨,∧,- > 是由布尔格 <A,≤ >
是所诱导的代数系统。称这个代数系统为 布尔代数 。
例 1 设 <?(S),∪,∩,~>是由布尔格 <?(S),?>
是所诱导的代数系统。这个代数系统为 布尔代数 。
当 S={a,b}时的运算表如表 6-4.1所示。 P-253页
2
3
定理 6-4.1 在一个有界分配格中，对于布尔代数中的任意两个元素 a,b，必定有
( a )=a
a∨ b= a∧ b
a∧ b= a∨ b
证明,只证第 (2)个等式先证互补的两个式子 相并 等于全上界,1”。
(a∨ b)∨ (a∧ b)= ((a∨ b)∨ a)∧ ((a∨ b)∨ b)
=(b∨ (a∨ a))∧ (a∨ (b∨ b))
=(b∨ 1)∧ (a∨ 1) =1
再证互补的两个式子 相交 等于全下界,0”。
(a∨ b)∧ (a∧ b)= 0?
4
定义 6-4.3 具有有限个元素的布尔代数称为 有限 布尔代数 。
定义 6-4.4 设 <A,∨,∧,- >和 <B,∨,∧,- >是两个布尔代数,如果存在着 A到 B的双射 f,对于任意的 a,b?A,
都有
f(a∨ b)=f(a)∨ f(b)
f(a∧ b)=f(a)∧ f(b)
f(a)=f(a)
则称 <A,∨,∧,- >和 <B,∨,∧,- >同构 。
可以证明,对于每一正整数 n,必存在着 2n个元素的布尔代数 ;反之,任一有限布尔代数,它的元素个数必为 2的幂次。
5
定义 6-4.5 设 <A,≤ > 是一个格，且具有全下界 0，
如果有元素 a盖住 0，则称元素 a为原子。
原子：与 0相邻且比 0“大”
定理 6-4.2 设 <A,≤ > 是一个具有全下界 0的有限格，
则对于任何一个非零元素 b（即不等于全下界 0的元素）
至少存在一个原子 a，使得 a ≤ b 。
证明,若 b是原子，则有 b ≤ b,若 b不是原子，则必有 b1存在，使得 0?b1?b
若 b1是原子，则定理得证，否则，必存在 b2使得
0?b2?b1?b
由于 <A,≤ >是一个有下界的有限格，所以通过有限不骤总可以找到一个原子 bi,使得 0?bi?...?b2?b1?b?
6
引理 6-4.1 设在一个布尔格中,b∧ c=0当且仅当 b ≤c。
证明,(1)先证 b∧ c=0? b ≤ c
若 b∧ c=0,因为 0∨ c=c,
则 (b∧ c)∨ c=c
根据分配性，就有
(b∨ c) ∧ (c∨ c) =c
即 (b∨ c) ∧ 1 =c
所以 b∨ c =c
又因为 b ≤ b∨ c
所以 b ≤ c
(2)再证 b ≤ c? b∧ c=0
若 b≤c,则 b∧ c?c∧ c,即 b∧ c?0,所以 b∧ c=0?
7
证明,(1)先证 a1∨ a2∨ …∨ ak ≤ b
记 a1∨ a2∨ …∨ ak =c,因为 aj ≤ b,所以 c ≤ b。
(2)再证 b ≤ a1∨ a2∨ …∨ ak
由引理 6-4.1知,要证 b≤c若是原子,只需证 b∧ c=0,
反设 b∧ c≠ 0,于是必有一个原子 a,使得 a≤b∧ c。
又因 b∧ c≤b,和 b∧ c≤c,所以 a≤b 和 a≤c,
因为 a是原子,且 a≤b,所以 a必是 a1,a2,…,ak中的一个,因此 a≤c,已有 a≤c,得 a≤c∧ c,即 a≤0,与 a是原子矛盾。
b∧ c≠ 0假设不成立 。综合 (1)和 (2)定理得证。
引理 6-4.2 设 <A,∨,∧,- >是一个有限布尔代数,若
b是 A中 任意非零元素,a1,a2,…,ak是 A中满足 aj≤b
的所有原子（ j=1,2,…,k）,则
b = a1∨ a2∨ …∨ ak
8
引理 6-4.3 设 <A,∨,∧,- >是一个有限布尔代数,若 b
是 A中 任意非零元素,a1,a2,…,ak是 A中满足 aj ≤b的所有原子（ j=1,2,…,k）,则 b = a1∨ a2∨ …∨ ak是将 b表示为原子之并的唯一形式。
证明,设有另一种表示形式为 b=aj1∨ aj1∨ …∨ ajt
其中 aj1,aj1,…,ajt是原子。因为 b是 aj1,aj1,…,ajt的最小上界,所以必有 aj1 ≤ b,aj2 ≤ b,...,ajt ≤ b。而 a1,a2,…,ak是 A
中所有满足 ai ≤ b （ i=1,2,…,k）的不同原子。
所以必有 t≤k
反设 t?k,那么在 a1,a2,…,ak中必有 aj0且 aj0≠ ajl
于是,由 aj0∧ (aj1∨ aj1∨ …∨ ajt)= aj0∧ (a1∨ a2∨ …∨ ak)
即 (aj0∧ aj1)∨ (aj0∧ aj2)∨ … ∨ (aj0∧ ajt)
= (aj0∧ a1)∨ (aj0∧ a2)∨ … ∨ (aj0∧ ak)
导致的 0= aj0矛盾。 t?k假设不成立 。 T=k定理得证。
9
引理 6-4.4 在一个布尔格 <A,?>中,对 A中 任意一个原子 a和另一个非零元素 b,a?b和 a?b两式中有且仅有一式成立。
证明,(1)先证 a?b和 a?b两式 不可能同时成立反设 a?b和 a?b同时成立，就有 a?b∧ b=0，这与 a是原子相矛盾，即 a?b和 a?b不 同时成立。
(2)再证 a?b 和 a?b两式中 必有一式成立因为 a∧ b?a,a是原子,所以只能是
a∧ b=0 或 a∧ b=a
若 a∧ b=0，则 a∧ (b) =0,由引理 6-4.1得
a?b；
若 a∧ b=a,由引理 6-1.6得 a?b。
10
定理 6-4.3(Stone 表示定理 ) 设 <A,∨,∧,- > 是由有限布尔格 <A,?>所诱导的一个有限布尔代数,S是布尔格中的所有原子的集合，则 <A,∨,∧,->和 <?(S),
∪,∩,~>同构。
证明,本定理的证明过程分三部分
(1)构造一个映射，并证明它是双射（既是入射又是满射）；
(2)描述代数系统 <A,∨,∧,- >和 <?(S),∪,∩,~>
同构并证明之；
(3)总结概括结论。
11
第 (1)部分 证明,对于任意非 0a?A,必有的唯一表示：
a=a1∨ a2∨? ∨ ak （引理 6-4.2a的原子表示）
其中 ai?a （ i=1,2,…,k）,作映射 f(a)=S1 = {a1,a2,…,ak}
那么，这个映射是 一个从 A到?(S)的一个双射。
第 1部分 双射证明：
,对于全下界 0?A，规定 f(0)=? 。
.如果 S1 ={a1,a2,…,ak}(S)，而有 a,b?A,使得
f(a)= f(a)=S1,则 a=a1∨ a2∨? ∨ ak = b，
所以 f是一个从 A到?(S)的一个入射。
.对于任一个 S1(S)，若 S1 ={a1,a2,…,ak}，则由于运算 ∨ 的封闭性，所以
a1∨ a2∨? ∨ ak = a?A
这就说明?(S)中任一元素，必是 A中某个元素的象，所以是一个从 A到?(S)的一个满射。
第 1部分 双射证明完毕。
12
第 (2)部分 证明,<A,∨,∧,- >和 <?(S),∪,∩,~>同构
第 2部分 同构性格证明：
,设 f(a∧ b)=S3,若 x?S3,则 x必是满足 x?a∧ b的原子，因为 a∧ b?a和 a∧ b?b，所以 x?a且 x?b，推得 x?S1
= f(a)且 x?S2 = f(b),即 x?S1∩ S2,这就证得
S3? S1∩ S2 。
反之,若 x?S1∩ S2,则 x?S1且 x?S2,所以 x必是满足 x?a
和 x?b的原子,推得 x必是满足 x?a∧ b的原子,所以 x?S3,这就证明了 S1∩ S2?S3 。
综上所述，就有 S3 = S1∩ S2,即
f(a∧ b)= f(a)∩ f(b)
13
,设 f(a∨ b)=S3,若 x?S3,则 x是满足 x?a∨ b的原子，所以必有 x?a或 x?b，这是因为：
若 x?a且 x?b,则由引理 6-4.4可知必有 x?a且 x?b,所以 x?a∧ b= a∨ b 。再由条件 x?a∨ b,便得
x? (a∨ b)∧ (a∨ b)=0
这与 x是原子相矛盾。
因此，若 x?a则 x?S1或者若 x?b则 x?S2，所以
x? S1∪ S2
这就证明了 S3? S1∪ S2 。
反之,若 x?S1∪ S2,则 x?S1或 x?S2,若 x?S1，则
x?a? a∨ b
所以 x?S3,同理，若 x?S2，则 x?b? a∨ b
所以 x?S3,这就证明了 S1∪ S2?S3 。
综上所述，就有 S3 = S1∪ S2,即
f(a∨ b)= f(a)∪ f(b)
14
.最后证明同构性的 f(a)= f(a)式：
将 S看作全集,另 f(a)=S1,则 f(a)=S-S1=S-f(a),可以证明 x?f(a)当且仅当 x?a,这是因为,若 x?f(a),必有 x?a,则由引理 6-4.4可知必有 x?a,反之,若原子 x满足 x?a,则必有 x?a,所以 x?f(a) 。
还可以证明,对于原子 x,x?a当且仅当 x?f(a),这是因为,若 x?a而 x?f(a),将导致 x?a的矛盾,所以 x?f(a),反之,若 x?f(a)而 x?a,也将导致 x?f(a)的矛盾,所以 x?a 。
另外还可以证明,x?f(a)当且仅当 x?f(a),所以,对于原子 x,x?f(a)当且仅当 x?f(a),因此,
f(a)=f(a) 第 2部分 同构性证明完毕。
(3)总结概括结论,<A,∨,∧,->和 <?(S),∪,∩,~>同构。
推论 6-4.1 有限布尔格的元素个数必定等于 2n，其中 n
是该布尔格中所有原子的个数。
推论 6-4.2 任何一个具有 2n个元素的有限布尔代数都是同构的。
15
6-5 布尔表达式定义 6-5.1 设 <A,∨,∧,->为布尔代数,如下递归地定义 A上 布尔表达式 (Boolean expressions)：
（ 1） 布尔常元 (取值于 A的常元 )是布尔表达式,布尔常元常用 a,b,c等符号表示。
（ 2） 布尔变元 (取值于 A的变元 )是布尔表达式，布尔变元常用 x,y,z等符号表示。
（ 3） 如果 e1,e2为布尔表达式，那么
(e1),(e1∨e 2),(e1∧e 2) 也是布尔表达式。
（ 4） 除有限次使用条款（ 2），（ 3）生成的表达式是布尔表达式外，没有别的是布尔表达式。
例 1 给出了两个布尔函数的例子,见表 6-5.1和 6-5.2。
例 2 给出了布尔表达式的例子,见 P-262页。
16
定义 6-5.2 一个含有 n个相异变元的布尔表达式，
称为含有 n元的布尔表达式，记为 E(x1,x2,?,x n)，
其中 x1,x2,?,x n为 变元。
定义 6-5.3 布尔代数 <A,∨,∧,->上的一个含有 n
元的布尔表达式 E(x1,x2,?,x n)的值是指：将 A中的元素作为变元 xi(i=1,2,?,n) 的值来代替表达式中相应的变元（即对变元赋值）,从而计算出表达式的值。
定义 6-5.4 布尔代数 <A,∨,∧,->上两个 n元的布尔表达式为 E1(x1,x2,?,x n)和 E2(x1,x2,?,x n),
如果对于 n个变元的任意赋值 xi=xi’,xi’?A时均有
E1(x1’,x2’,?,x n’ )=E2(x1’,x2’,?,x n’ )
则称这两个 布尔表达式 是等价的。
17
例 4 布尔代数 <{0,1},∨,∧,->上两个 3元的布尔表达式为 E1(x1,x2,x3)=(x1∧x 2)∨(x 1∧x 3)
和 E2(x1,x2,x3)=x1∧(x 2∨x 3)
验证这两个布尔表达式是等价的。
E1(0,1,1)=(0∧1)∨(0∧0)=0
E2(0,1,1)=0∧(1∨0)=0
E1(1,1,1)=(1∧1)∨(1∧0)=1
E2(1,1,1)=1∧(1∨0)=1
E1(0,0,0)=(0∧0)∨(0∧1)=0
E2(0,0,0)=0∧(0∨1)=0
等等 (全部赋值状况共 8种需要验证。 )。
结论：一个 n元布尔表达式确定一个从 An到 A的函数。
定义 6-5.5 设 <A,∨,∧,->为布尔代数,一个从 An到 A
的函数，如果它能够用 <A,∨,∧,->上的一个 n元布尔表达式 E(x1,x2,?,x n)来表示，那么，称此函数为 布尔函数 。
18
定理 6-5.1 对于两个元素的布尔代数 <{0,1},∨,∧,->,
任何一个从 {0,1}n到 {0,1}的函数,都是布尔函数。
证明,n元布尔表达式若有 x1’ ∧x 2’ ∧?∧x n’ 形式 (其中 xi’ 是 xi或 xi中的任一个 ),则称它为 小项,若一个布尔表达式能表示成 小项的并,则称它为 析取范式 。对于一个从
{0,1}n到 {0,1}的函数,先用那些使函数值为 1的有序 n元组分别构造小项，其中
xi 若 n元组中第 i个分量为 1
xi 若 n元组中第 i个分量为 0
由这些小项构成的析取范式就是原函数对应的布尔表达式。
xi’ =
例 5 对于表 6-5.3定义的函数写出布尔表达式的析取范式。
第 1步：利用函数值为 1的所有行写出小项；
第 2步：写出小项的析取式。
19
n元布尔表达式若有 x1’ ∨x 2’ ∨?∨x n’ 形式 (其中 xi’
是 xi和 xi中的任一个 ),则称它为 大项,若一个布尔表达式能表示成 大项的交,则称它为 合取范式 。对于一个从 {0,1}n到
{0,1}的函数,先用那些使函数值为 0的有序 n元组分别构造大项，其中
xi 若 n元组中第 i个分量为 0
xi 若 n元组中第 i个分量为 1
由这些大项构成的合取范式就是原函数对应的布尔表达式。
对于表 6-5.3定义的函数写出布尔表达式的合取范式。
第 1步：利用函数值为 0的所有行写出大项；
第 2步：写出大项的合取式。
定理 6-5.5 布尔代数 <A,∨,∧,->上的任意一个 n元布尔表达式 E(x1,x2,?,x n)一定能写成析取范式（合取范式）。
证明,略?
xi’ =
