第九章 格与布尔代数
9.1 格
9.2 布尔代数
9.3 子布尔代数,积布尔代数和布尔代数同态
9.4 布尔代数的原子表示
9.5 布尔代数 Br2
9.6 布尔表达式及其范式定理退出
9.1 格
1,格作为偏序集定义 9.1.1 设 <L,≤>是一个偏序集,若对任意 a,b,?L,存在 glb{a,b}和 lub{a,b},则称 <L,≤>
为格,并记为 a*b=glb{a,b},a?b=lub{a,b},称
和?分别为 L上的交 （ 或积 ） 和并 （ 或和 ） 运算 。 称 <L,?,*>为 <L,≤>所诱导的代数结构的格 。
若 L是有限集合,称 <L,≤>为有限格 。
格的对偶性原理是成立的：
令 <L,≤>是偏序集，且 <L,≥>是其对偶的偏序集。若 <L,≤>是格，则 <L,≥>也是格，反之亦然。这是因为，对于 L中任意 a和 b,<L,≤>中
lub{a,b}等同于 <L,≥>中 glb {a,b},<L,≤>中
glb{a,b}等同于 <L,≥>中的 lub{a,b}。若 L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。
从上讨论中，可知两格互为对偶。互为对偶的两个 <L,≤>和 <L,≥>有着密切关系，即格
<L,≤>中交运算?正是格 <L,≥>中的并运算?，而格 <L,≤>中的并运算?正是格 <L,≥>中的交运算?。
因此，给出关于格一般性质的任何有效命题，
把关系 ≤换成 ≥（或者 ≥换成 ≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。
定义 9.1.2 设 <L,≤>是格，且 S?L。若对任意 a,b?S，有 a*b?S和 a?b?S，则称 <S,≤>是格
<L,≤>的子格。
2,格的基本性质在证明格的性质前,回忆一下 a*b和 a?b的真正含义是有好处的 。
① a*b≤a和 a?b≤b,则表明 a*b是 a和 b的下界 。
② 若 c≤a和 c≤b,则 c≤a*b,这表明 a*b是 a
和 b的最大下界 。
①’ a≤a?b和 b≤a?b,则表明 a?b是 a和 b
的上界 。
②’ 若 a≤c,且 b≤c,则 a?b≤c,这表明
a?b是 a和 b的最小上界 。
定理 9.1.1 设 <L,≤>是格，对任意 a,b?L，
有
① a?b=b?a≤b
② a*b=a?a≤b
③ a*b=a?a?b=b
亦即 a≤b?a?b=b?a*b=a
定理 9.1.2 设 <L,≤>是格,对任意 a,b?L，
有
① a*b=a,a?a=a。 （ 幂等律 ）
② a*b=b*a,a?b=b?a。 （ 交换律 ）
③ a*(b*c)=(a*b)*c
a?(b?c)=(a?b)?c （ 结合律 ）
④ a*(a?b)=a
a?(a*b)=a （ 吸收律 ）
定理 9.1.3 设 <L,≤>是格,对任意 a,b,c?L，
有
① 若 a≤b和 c≤d,则 a*c≤b*d,a?c≤b?d。
② 若 a≤b,则 a*c≤b*c,a?c≤b?c。
③ c≤a和 c≤b c≤a*b
④ a≤c和 b≤c a?b≤c
定理 9.1.4 设 <L,≤>是格,对任意的 a,b,c?L，
有
a?(b*c)≤(a?b)*(a?c)
(a*b)?(a*c)≤a*(b?c)
通常称上二式为格中分配不等式 。
定理 9.1.5 设 <L,≤>是格,对任意的 a,b,c?L，
有
a≤c?a?(b*c) ≤(a?b)*c
推论,在格 <L,≤>中,对任意的 a,b,c?L，
有
(a*b)?(a*c)≤a*(b?(a*c))
a?(b*(a?c))≤(a?b)*(a?c)
3,特殊的格定义 9.1.3 设 <L,≤>是格,若 L中有最大元和最小元,则称 <L,≤>为有界格 。 一般把格中最大元记为 1,最小元记为 0。
由定义可知,对任意 a?L,有
0≤a≤1
a*0=0,a?0=a
a*1=a,a?1=1
定理 9.1.6 设 <L,≤>是有限格，其中
L={a1,a2,··,an}，则 <L,≤>是有界格。
定义 9.1.4 设 <L,≤>是有界格，对于 a?L，
存在 b?L，使得
a*b=0,a?b=1
称 b为 a的补元，记为 a’。
由定义可知，若 b是 a的补元，则 a也是 b的补元，即 a与 b互为补元。
显然,0’=1和 1’=0，且易证补元是唯一的。
一般说来，一个元素可以有其补元，未必唯一，也可能无补元。
定义 9.1.5 设 <L,≤>是格,对任意的 a,b,c?L，
有
① a*(b?c)=(a*b)?(a*c)
② a?(b*c)=(a?b)*(a?c)
则称 <L,≤>为分配格,称 ① 和 ② 为格中分配律 。
定义 9.1.6 设 <L,≤>是格，对任意的 a,b,c?L，
有
a≤c?a?(b*c)=(a?b)*c
称 <L,≤>为模格。
定理 9.1.7 分配格是模格定理 9.1.8 每个链都是分配格 。
定理 9.1.9 一个格为分配格,当且仅当它不含有任何子格与这两个五元素格中任一个同构 。
定理 9.1.10 设 <L,≤>是分配格,对任意
a,b,c?L,有
(a*b=a*c)且 (a?b=a?c)?b=c
定理 9.1.11 设 <L,≤>是有界分配格,若 a?L，
且补元存在,则其补元是唯一的 。
定义 9.1.7 设 <L,≤>是格,若 L中每个元素至少有一补元,则称 <L,≤>为有补格 。
由于补元的定义是在有界格中给出的,可知,有补格一定是有界格 。
定义 9.1.8 若一格既是有补又是分配的,则称该格为有补分配格,或布尔格,或布尔代数 。
定理 9.1.12 设 <L,≤>是有补分配格,若任意元素 a?L,则 a的补元 a’是唯一的 。
该定理 9.1.11的直接推论,因为有补分配格当然是有界分配格 。
由于有补分配格中,每个元素 a都有唯一的补元 a’,因此可在 L上定义一个一元运算 — 补运算,’” 。 这样,有补分配格可看作具有两个二元运算和一个一元运算的代数结构,习惯上称它为布尔代数,记为 <B,?,*,’,0,1>,其中 B=L。
定理 9.1.13 设 <L,≤>是有补分配格，对任意 a,b?L，则
① (a’)’=a
② (a*b)’=a’?b’
③ (a?b)’=a’*b’
后两式称为格中德 ·摩根律。
定理 9.1.14 设 <L,≤>是有补分配格,对任意 a,b?L,有
a≤b?a*b’=0
a’?b=1
格同态,格直积等概念可以接下来定义和研究,但这里不打算这样做,因为如此进行会相对较繁,而是将格作为一个代数结构而引入它们 。
4,格是代数结构能自然地把代数结构中有关子代数,同态,
积代数等概念,引入到格中 。
定义 9.1.9 设 <L,?,*>是一代数结构,其中
和 *是 L上满足交换律,结合律和吸收律的二元运算,且对任意 a,b?L,定义关系 ≤如下：
a≤b?a*b=a
则 <L,≤> 是格,称 <L,≤> 为 代 数 系 统
<L,?,*>所诱导的偏序集确立的格 。
定义 9.1.10 设 <L,?,*>和 <S,?,?>是格 。 存在函数 f:L?S,若对任意 a,b?L,有
f(a?b)=f(a)?f(b),f(a*b)=f(a)?f(b)
则称 f是从 <L,?,*>到 <S,?,?>的格同态 。
下述定理说明格同态是保序的 。
定理 9.1.15 设 <L,?,*>和 <S,?,?>是格,而
<L,≤>和 <S,≤’>分别是给定两个格所诱导的偏序集确立的格 。 若 f:L?S是格同态,则对任意
a,b?L,且 a≤b,必有 f(a)≤’f(b)。
在定义 9.1.10中,若 f是双射函数,则称 f是格同构 。 或称 <L,?,*>和 <S,?,?>两个格同构 。
由于同构是相互的,又是保序的,故对任意
a,b?L,有
a≤b?f(a)≤’f(b)
和
f(a)≤’f(b)?a≤b
这表明同构的两个格的哈斯图是一样的,
只是各结点的标记不同而已 。
定义 9.1.11 设 <L,?,*>和 <S,?,?>是格,定义一个代数结构 <L?S,+,o>如下：
对任意 <a1,b1>,<a2,b2>?L?S,有
<a1,b1>+<a2,b2>=<a1?b1,a2?b2>
<a1,b1>o<a2,b2>=<a1*b1,a2?b2>
称 <L?S,+,o>是格 <L,?,*>和 <S,?,?>的直积 。
两个格的直积也是格。这是因为在 L?S上，
运算 o和 +是封闭的，且满足交换律、结合律和吸收律。
格积的阶等于两个格的阶乘积。由于
<L?S,o,+>是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。
9.2 布尔代数前已指出,布尔代数是有补分配格,
常记为 <B,?,*,’,0,1>。 对任意 a,b,c?B，
有
① <B,?,*>是格，且 ≤为 B上由?或 *所定义的偏序关系，满足
(L-1) a?b=lub{a,b},a*b=glb{a,b}
(L-2) a≤b?a?b=b?a*b=a
(L-3) a?a=a,a*a=a （等幂律）
(L-4) a?b=b?a,a*b=b*a （交换律）
(L-5) (a?b)?c=a?(b?c),(a*b)*c=a*(b*c)
（结合律）
(L-6) a?(a*b)=a,a*(a?b)=a （吸收律）
② <B,?,*>是分配格，满足
(D-1) a?(b*c)=(a?b)*(a?c)，
a*(b?c)=(a*b)?(a*c) （分配律）
(D-2) (a?b=a?c)?(a*b=a*c)?b=c
(D-3) (a?b)*(b?c)*(c?a)=(a*b)?(b*c)?(c*a)
③ <B,?,*,’,0,1>是有界格，满足
(B-1) 0≤a≤1
(B-2) a?0=a,a*a=a （幺律）
(B-3) a?1=1,a*0=0 （零律）
④ <B,?,*,’,0,1>是有补格，满足
(C-1) a?a’=1,a*a’=0 （互补律）
(C-2) 1’=0,0’=1
⑤ <B,?,*,’,0,1>是有补分配格，满足
(CD-1) (a?b)’=a’*a’,(a*b)’=a’?b’
（德 ·摩根律）
(CD-2) a≤b?a’?b=1?a*b’=0?b’≤a’
注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。
定义 9.2.1 设 <B,?,*,’>是一代数结构，其中?和 *是 B上的二元运算，’是 B上的一元运算。
0,1?B。若对任意 a,b?B，有
① a?b=b?a,a*b=b*a （交换律）
② a?(b*c)=(a?b)*(a?c)，
a*(b?c)=(a*b)?(a*c) （分配律）
③ a?0=a,a*1=a （幺律）
④ a?a’=1,a*a’=0 （互补律）
则称 <B,?,*,’>是布尔代数，称?,*和’
分别是 B上的并、交和补运算,0和 1分别称为?
和 *的零元和幺元。
代数结构 <B,?,*,’,0,1>满足定义 9.2.1的条件,所以它是布尔代数,它是二元布尔代数 。
二元布尔代数其哈斯图是链的唯一布尔代数 。
9.3 子布尔代数、积布尔代数和布尔代数同态把子代数,积代数和同态的概念应用到布尔代数上,便得到了相应论题,本节不准备详尽叙述它,仅就其特点讨论之 。
定义 9.3.1 给定布尔代数 <B,?,⊙,’，
0,1>,?≠T?B，若 T对所有运算封闭，且 0，
1∈ T，则称 <T,?,⊙,’ >是子布尔代数。
显然,<B,?,⊙,’,0,1>和 <{0,1}，
,⊙,’,0,1>是子布尔代数。
应该指出，没有必要对所有三个运算?，
⊙ 和’都要检查封闭性，也没有必要验证 0与 1
是否在 T中，只要对运算集合 {?，’ }或
{⊙,’ }检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能集得出。因为对任意 x,y∈ S，有 x⊙ y=(x’?y’)’,0=(x’?x)’，
1=x?x’，故对于?和’的封闭便保证了 ⊙ 的封闭以及 0,1∈ T。
对于 {⊙,’ }可用同样论证。
显然，每个子布尔代数都是布尔代数。
布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否封闭而定。
定义 9.3.2 给定两个布尔代数 <B1,?1，
⊙ 1，’,01,11> <B2,?2,⊙ 2,″,02，
12>，则两个布尔代数的积也是布尔代数，称为积布尔代数，记作 <B1× B2,?3,⊙ 3，’’’，
03,13>，其中对任意 <b11,b21>,<b12，
b22>∈ B1× B2，有
<b11,b21>?3<b12,b22>=<b11?1b12，
b21?2b22>
<b11,b21>⊙ 3<b12,b22>=<b11⊙ 1b12，
b21⊙ 2b22>
<b11,b21>’’’=<b11’,b21″>
03=<01,02>,13=<11,12>
可见，积布尔代数能够生成新的布尔代数。
定义 9.3.3 给定两个布尔代数 <B,+,·，’，
0,1>和 <T,?,⊙,ˉ,α,β>，则
<B,+,·，’,0,1>?<T,?,⊙,ˉ,α，
β>,=(?f)(f∈ TB∧ (?x)(?y)(x,y∈ S→(f(x+y)=f(x)
f(y)∧ f(x·y)=f(x)⊙ f(y)∧ f(x’)= ∧ f(0)=α∧ f(1)=β)))
并称 f为从 <B,+,·，’,0,1>到 <T,?，
⊙,ˉ,α,β>的布尔同态映射。
如前所述，同态的定义仍可简化成：若保持运算 {?，’ }或 {⊙,’ }则 f∈ TB为布尔同态映射。又若 f为双射，则 f为布尔同构映射。
定理 9.3.1 若 f为从 <B,+,·，’,0,1>到
<T,?,⊙,ˉ,α,β>的布尔同态映射，且
|f(B)|≥2，其中 f(B)={y|f(x)=y∈ T∧ x∈ B}，则
<f(B),?,⊙,ˉ,f(0),f(1)>是布尔代数。
9.4 布尔代数的原子表示在布尔集合代数中,每个子集可表成单元集的并,而且这种表示在不计项的次序情况下是唯一的 。 对于任何有限布尔代数,也将有同样的结果,这里起着单元集作用的那些元素,
称它们是原子 。
定义 9.4.1 给定布尔代数 <B,?,⊙,’，
0,1>且 0≠a∈ B，则 a为原子：
=(?x)(x∈ B→ a⊙ x=a∨ a⊙ x=0)
因为 a⊙ x=a?a?x，所以上述定义又可表为
a为原子,=(?x)(x∈ S→ a?x∨ a⊙ x=0)
若 a为原子且 x?a，则 x=0或 x=a。这表明原子在偏序图中是那些紧位于零元之上的元素。
定理 9.4.1 若 a1和 a2为布尔代数 <B,?，
⊙,’ >的原子，且 a1⊙ a2≠0，则 a1=a2。
定理 9.4.2 若 x是有限布尔代数 <B,?，
⊙,’ >的非零元,则存在原子 a∈ S,使得 a?x。
定理 9.4.3 若 a,a1,a2,…,an为有限布尔代数 <B,?,⊙,’,0,1>的原子,则
a?a1?a2?…?an?(?i)(i∈ {1,2,…,
n}∧ a=ai)
定理 9.4.4 设有限布尔代数 <B,?，
⊙,’,0,1>的所有原子是 a1,a2,…,
an,且 y∈ B,则
y=0?(?i)(i∈ {1,2,…,
n}→ y⊙ ai=0)
定理 9.4.5(原子表示定理 )
给定布尔代数 <B,?,⊙,’,0，
1>,0≠x∈ B以及 i=1,2,…,n,ai?x，
则 x= ai,且不计原子的次序表示式是唯一的 。
定理 9.4.6 (斯通 (Stone)定理 )
设 <B,?,⊙,’,0,1>是有限布尔代数,
且 A表示该代数中的所有原子的集合,则 <B,?，
⊙,’,0,1>同构于幂集代数 <P(A),∪,∩，
ˉ,?,A>。
本定理说明了,能够用布尔代数的各原子,
完全确定该布尔代数,并且可用布尔集合代数
<P(A),∪,∩,ˉ,?,A>表示这一布尔代数 。
由本定理可直接得到下面推论：
|B|=2|A|
由此又可推出，若两个有限布尔代数中的集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因此可得到如下定理：
定理 9.4.7 每个有限布尔代数的集合基数均为 2的方幂，具有同样集合基数的布尔代数都是同构的。
9.5 布尔代数 Br2
为了书写方便,用 Bn表示具有 n个元素的布尔代数 <Bn,?,⊙,’ >,即 Bn=<Bn,?，
⊙,’ >。 根据定理 9.4.7可知,n必为 2的方幂 。
因此,,最小,的布尔代数即是二元布尔代数
B2=<B2,?,⊙,’ >,其中 B2={0,1}。 B2的运算表如表 9.1.1所示 。 下面再给出,次最小,
的布尔代数 B4=<B4,?,⊙,’ >的运算表 9.5.1，
其中 B4={0,α,β,1}。
特别令人感兴趣的代数结构是
B2× B2× … × B2(r个 ),即 r个相同的布尔代数 B2
的直积 。 该系统记作 Br2,且其运算符号仍与 B2
中的?,⊙ 和 ’ 相同,即 Br2=<Br2,?,⊙,’,
0r,1r>。 对任意 <σ1,σ2,…,σr>和 <δ1,
δ2,…,δr>∈ Br2,其中 σi,δj∈ {0,1},i,j=1，
2,…,n。
<σ1,σ2,…,σr>?<δ1,δ2,…,
δr>=<σ1?δ1,σ2?δ2,…,σr?δr>
<σ1,σ2,…,σr>⊙ <δ1,δ2,…,
δr>=<σ1⊙ δ1,σ2⊙ δ2,…,σr⊙ δr>
<σ1,σ2,…,σr>’ =<σ1’,σ2’,…,σr’>
0’=<0,0,…,0>和 1’=<1,1,…1>
由积代数的理论可知,Br2保持 B2中重要性质，于是断言,Br2是布尔代数，并且由定理
9.4.7能得到下面定理：
定理 9.5.1 布尔代数 <,?,⊙,’ >
与
<Br2,?,⊙,’ >是同构的，并且每个布尔代数同构于某布尔代数 Bk2=<Bk2,?，
⊙,’ >。
综上所述可知,每个布尔代数同构于某布尔集合代数 。
9.6 布尔表达式及其范式定理本节中先给出布尔表达式或布尔函数的定义,后讨论布尔表达式的范式定理 。
定义 9.6.1 给定布尔代数 <B,?,⊙,’,
0,1>及 n个变元 x1,x2,…,xn,则在 <B,?，
⊙,’,0,1>上由 n个变元产生的布尔表达式可归纳定义如下：
(1) (基础 )。 B中的任何元素和变元 xi(i=1，
2,…,n)都是一个布尔表达式。
(2) (归纳步 )。若 e1和 e2是布尔表达式，那么 e’1,(e1)?(e2)和 (e1)⊙ (e2)也是布尔表达式。
注意，当约定 ⊙ 先于?运算时，可适当省略表达式中的园括号。
如果限定 n个变元 x1,x2,…,xn都取值于
B中的元素,那么在布尔代数 <B,?,⊙,’,
0,1>上由变元 x1,x2,…,xn所产生的布尔表达式的值便表示 B中的元素 。 因此,这些表达式便是一个函数 f∈ Bn,这里 f(x1,x2,…,xn)对任意变元 x1,x2,…,xn可由布尔代数 <B,?，
⊙,’,0,1>中关于?,⊙,’ 的运算来确定 。
因此,有时将在 <B,?,⊙,’,0,1>上由变元 x1,x2,…,xn产生的布尔表达式称为在 <B，
,⊙,’,0,1>上的 n元布尔函数 (以下简称布尔函数 )。
定义 9.6.2 形如 ⊙ ⊙ … ⊙ 的布尔表达式称为由变元 x1,x2,…,xn产生的小项,
其中 δi∈ {0,1},用 x1i表示 xi,x0i表示 xi’,i∈ {1，
2,…,n},并用 表示该小项 。
形如…? 的布尔表达式称为由变元 x1,x2,…,xn产生的大项,其中
σi∈ {0,1},x1i表示 x’i,x0i表示 xi,i∈ {1，
2,…,n},并用 表示该大项 。
为书写方便，将二进制数 δ1δ2… δn和
σ1σ2… σn分别化为十进制数 i和 j作为 m和 M的下标，即 mi和 Mj。
关于小项和大项有下列关系：
mi⊙ mj=0 (i≠j)
Mi?Mj=1 (i≠j)
这是显然的，因为对于两个不同的小项 (大项 )，必有一个变元 xk，使得这两个小项 (大项 )
之一含有 xk，而另一个含有 x’k。于是，
xk⊙ xk’=0,xk?xk’=1。因此上列关系成立。
使用归纳法不难证明下列关系：
mi=1
Mi=0
定理 9.6.1(范式定理 ) 在布尔代数 <B,?，
⊙,’,0,1>上由变元 x1,x2,…,xn产生的每个布尔表达式 f(x1,x2,…,xn)均可表成：
f(x1,x2,…,xn)= (ck⊙ mk) (1)
f(x1,x2,…,xn)= (Cl?Ml) (2)
这里,k和 l分别取遍 2n个所有可能的组态
δ1δ2… δn和 σ1σ2… σn，并且
=f(δ1,δ2,…,δn)
=f(σ1,σ2,…,σn) (3)
由本定理可知,布尔代数 <B,?,⊙,’,
0,1>上的由变元 x1,x2,…,xn产生的每个布尔表达式均可表为所有小项的带,权,的并,
或者所有大项的带,权,的交,其中这些
,权,(即 cδ1δ2… δn或 Cσ1σ2… σn)是 B中的元素,它可用布尔表达式用公式 (3)计算得到 。 由于这些权是唯一的,故上述公式 (1)和 (2)便是唯一的,
并称 (1)为小项范式或析取范式,称 (2)为大项范式或合取范式 。
布尔表达式的范式也可由下面算法 9.6.1
（ 或 9.6.2） 得到 。
算法 9.6.1（ 或 9.6.2）
本算法可求出 <B,?,⊙,’ >上的布尔表达式 f(x1,x2,…,xn)范式,其具体步骤是：
(1)使用定律和定理把 f(x1,x2,…,xn)表示成形如 c⊙ ⊙ ⊙ ···⊙ （或 C?
···? ）的不同交（或并）的并（或交），其中 c,C?B且 i1<i2<··<ik。
( 2 )若每个交 （ 或并 ） 是形如 c⊙ m（ 或
C?M）,其中 c?B（ 或 C?B）,m是小项 （ 或
M是大项 ）,则增加项 (0⊙ m1)?(0⊙ m2)?···（ 或增加项 ( 1? M 1 ) ⊙ ( 1? M 2 ) ⊙ ···）,其中
m1,m2,··（ 或 M1,M2,··） 是表达式中缺乏的小项
（ 或 大 项 ）,否 则 转 到 ( 3 ) 。
(3)从最后得到的表达式中，选取形如 c⊙
⊙ ⊙ ···⊙ （或 C?
···? ）的交（或并），其中
k<n和对某个 h,（或 ）不出现，
则用
hihix?
再在新的交（或并）中按下标增加次序重新排列 （或 ），于是使用
(c1?c2?···) ⊙ m(或 (C1⊙ C2⊙ ··)?M代替
c1⊙ m,c2⊙ m,··（或 C1?M,C2?M,··）的交（或并）。转到 (2)。
因为在 <B,?,⊙,’ >上的布尔表达式 f(x1,x2,…,xn)是由 2n个权唯一确定,又因为每个权是 B中的元素,所以在
<B,?,⊙,’ >上共有 个不同布尔表达式 。
另一方面，形如 f? 的不同函数共有 个
。可见，当 |B|>2时，形如 f? 的函数中确有那些函数，它不是布尔函数。而且可以精确计算 - 个函数不是布尔函数。
例如对于 S={0,?,?,1}，函数 f? 的定义中有
f(0,0)=0,f(0,1)=1,f(1,0)=f(1,1)=?，
f(0,?)=?
则 f不是布尔函数，为什么？读者从上面的说明中是不难给出正确地回答。
9.1 格
9.2 布尔代数
9.3 子布尔代数,积布尔代数和布尔代数同态
9.4 布尔代数的原子表示
9.5 布尔代数 Br2
9.6 布尔表达式及其范式定理退出
9.1 格
1,格作为偏序集定义 9.1.1 设 <L,≤>是一个偏序集,若对任意 a,b,?L,存在 glb{a,b}和 lub{a,b},则称 <L,≤>
为格,并记为 a*b=glb{a,b},a?b=lub{a,b},称
和?分别为 L上的交 （ 或积 ） 和并 （ 或和 ） 运算 。 称 <L,?,*>为 <L,≤>所诱导的代数结构的格 。
若 L是有限集合,称 <L,≤>为有限格 。
格的对偶性原理是成立的：
令 <L,≤>是偏序集，且 <L,≥>是其对偶的偏序集。若 <L,≤>是格，则 <L,≥>也是格，反之亦然。这是因为，对于 L中任意 a和 b,<L,≤>中
lub{a,b}等同于 <L,≥>中 glb {a,b},<L,≤>中
glb{a,b}等同于 <L,≥>中的 lub{a,b}。若 L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。
从上讨论中，可知两格互为对偶。互为对偶的两个 <L,≤>和 <L,≥>有着密切关系，即格
<L,≤>中交运算?正是格 <L,≥>中的并运算?，而格 <L,≤>中的并运算?正是格 <L,≥>中的交运算?。
因此，给出关于格一般性质的任何有效命题，
把关系 ≤换成 ≥（或者 ≥换成 ≤），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。
定义 9.1.2 设 <L,≤>是格，且 S?L。若对任意 a,b?S，有 a*b?S和 a?b?S，则称 <S,≤>是格
<L,≤>的子格。
2,格的基本性质在证明格的性质前,回忆一下 a*b和 a?b的真正含义是有好处的 。
① a*b≤a和 a?b≤b,则表明 a*b是 a和 b的下界 。
② 若 c≤a和 c≤b,则 c≤a*b,这表明 a*b是 a
和 b的最大下界 。
①’ a≤a?b和 b≤a?b,则表明 a?b是 a和 b
的上界 。
②’ 若 a≤c,且 b≤c,则 a?b≤c,这表明
a?b是 a和 b的最小上界 。
定理 9.1.1 设 <L,≤>是格，对任意 a,b?L，
有
① a?b=b?a≤b
② a*b=a?a≤b
③ a*b=a?a?b=b
亦即 a≤b?a?b=b?a*b=a
定理 9.1.2 设 <L,≤>是格,对任意 a,b?L，
有
① a*b=a,a?a=a。 （ 幂等律 ）
② a*b=b*a,a?b=b?a。 （ 交换律 ）
③ a*(b*c)=(a*b)*c
a?(b?c)=(a?b)?c （ 结合律 ）
④ a*(a?b)=a
a?(a*b)=a （ 吸收律 ）
定理 9.1.3 设 <L,≤>是格,对任意 a,b,c?L，
有
① 若 a≤b和 c≤d,则 a*c≤b*d,a?c≤b?d。
② 若 a≤b,则 a*c≤b*c,a?c≤b?c。
③ c≤a和 c≤b c≤a*b
④ a≤c和 b≤c a?b≤c
定理 9.1.4 设 <L,≤>是格,对任意的 a,b,c?L，
有
a?(b*c)≤(a?b)*(a?c)
(a*b)?(a*c)≤a*(b?c)
通常称上二式为格中分配不等式 。
定理 9.1.5 设 <L,≤>是格,对任意的 a,b,c?L，
有
a≤c?a?(b*c) ≤(a?b)*c
推论,在格 <L,≤>中,对任意的 a,b,c?L，
有
(a*b)?(a*c)≤a*(b?(a*c))
a?(b*(a?c))≤(a?b)*(a?c)
3,特殊的格定义 9.1.3 设 <L,≤>是格,若 L中有最大元和最小元,则称 <L,≤>为有界格 。 一般把格中最大元记为 1,最小元记为 0。
由定义可知,对任意 a?L,有
0≤a≤1
a*0=0,a?0=a
a*1=a,a?1=1
定理 9.1.6 设 <L,≤>是有限格，其中
L={a1,a2,··,an}，则 <L,≤>是有界格。
定义 9.1.4 设 <L,≤>是有界格，对于 a?L，
存在 b?L，使得
a*b=0,a?b=1
称 b为 a的补元，记为 a’。
由定义可知，若 b是 a的补元，则 a也是 b的补元，即 a与 b互为补元。
显然,0’=1和 1’=0，且易证补元是唯一的。
一般说来，一个元素可以有其补元，未必唯一，也可能无补元。
定义 9.1.5 设 <L,≤>是格,对任意的 a,b,c?L，
有
① a*(b?c)=(a*b)?(a*c)
② a?(b*c)=(a?b)*(a?c)
则称 <L,≤>为分配格,称 ① 和 ② 为格中分配律 。
定义 9.1.6 设 <L,≤>是格，对任意的 a,b,c?L，
有
a≤c?a?(b*c)=(a?b)*c
称 <L,≤>为模格。
定理 9.1.7 分配格是模格定理 9.1.8 每个链都是分配格 。
定理 9.1.9 一个格为分配格,当且仅当它不含有任何子格与这两个五元素格中任一个同构 。
定理 9.1.10 设 <L,≤>是分配格,对任意
a,b,c?L,有
(a*b=a*c)且 (a?b=a?c)?b=c
定理 9.1.11 设 <L,≤>是有界分配格,若 a?L，
且补元存在,则其补元是唯一的 。
定义 9.1.7 设 <L,≤>是格,若 L中每个元素至少有一补元,则称 <L,≤>为有补格 。
由于补元的定义是在有界格中给出的,可知,有补格一定是有界格 。
定义 9.1.8 若一格既是有补又是分配的,则称该格为有补分配格,或布尔格,或布尔代数 。
定理 9.1.12 设 <L,≤>是有补分配格,若任意元素 a?L,则 a的补元 a’是唯一的 。
该定理 9.1.11的直接推论,因为有补分配格当然是有界分配格 。
由于有补分配格中,每个元素 a都有唯一的补元 a’,因此可在 L上定义一个一元运算 — 补运算,’” 。 这样,有补分配格可看作具有两个二元运算和一个一元运算的代数结构,习惯上称它为布尔代数,记为 <B,?,*,’,0,1>,其中 B=L。
定理 9.1.13 设 <L,≤>是有补分配格，对任意 a,b?L，则
① (a’)’=a
② (a*b)’=a’?b’
③ (a?b)’=a’*b’
后两式称为格中德 ·摩根律。
定理 9.1.14 设 <L,≤>是有补分配格,对任意 a,b?L,有
a≤b?a*b’=0
a’?b=1
格同态,格直积等概念可以接下来定义和研究,但这里不打算这样做,因为如此进行会相对较繁,而是将格作为一个代数结构而引入它们 。
4,格是代数结构能自然地把代数结构中有关子代数,同态,
积代数等概念,引入到格中 。
定义 9.1.9 设 <L,?,*>是一代数结构,其中
和 *是 L上满足交换律,结合律和吸收律的二元运算,且对任意 a,b?L,定义关系 ≤如下：
a≤b?a*b=a
则 <L,≤> 是格,称 <L,≤> 为 代 数 系 统
<L,?,*>所诱导的偏序集确立的格 。
定义 9.1.10 设 <L,?,*>和 <S,?,?>是格 。 存在函数 f:L?S,若对任意 a,b?L,有
f(a?b)=f(a)?f(b),f(a*b)=f(a)?f(b)
则称 f是从 <L,?,*>到 <S,?,?>的格同态 。
下述定理说明格同态是保序的 。
定理 9.1.15 设 <L,?,*>和 <S,?,?>是格,而
<L,≤>和 <S,≤’>分别是给定两个格所诱导的偏序集确立的格 。 若 f:L?S是格同态,则对任意
a,b?L,且 a≤b,必有 f(a)≤’f(b)。
在定义 9.1.10中,若 f是双射函数,则称 f是格同构 。 或称 <L,?,*>和 <S,?,?>两个格同构 。
由于同构是相互的,又是保序的,故对任意
a,b?L,有
a≤b?f(a)≤’f(b)
和
f(a)≤’f(b)?a≤b
这表明同构的两个格的哈斯图是一样的,
只是各结点的标记不同而已 。
定义 9.1.11 设 <L,?,*>和 <S,?,?>是格,定义一个代数结构 <L?S,+,o>如下：
对任意 <a1,b1>,<a2,b2>?L?S,有
<a1,b1>+<a2,b2>=<a1?b1,a2?b2>
<a1,b1>o<a2,b2>=<a1*b1,a2?b2>
称 <L?S,+,o>是格 <L,?,*>和 <S,?,?>的直积 。
两个格的直积也是格。这是因为在 L?S上，
运算 o和 +是封闭的，且满足交换律、结合律和吸收律。
格积的阶等于两个格的阶乘积。由于
<L?S,o,+>是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。
9.2 布尔代数前已指出,布尔代数是有补分配格,
常记为 <B,?,*,’,0,1>。 对任意 a,b,c?B，
有
① <B,?,*>是格，且 ≤为 B上由?或 *所定义的偏序关系，满足
(L-1) a?b=lub{a,b},a*b=glb{a,b}
(L-2) a≤b?a?b=b?a*b=a
(L-3) a?a=a,a*a=a （等幂律）
(L-4) a?b=b?a,a*b=b*a （交换律）
(L-5) (a?b)?c=a?(b?c),(a*b)*c=a*(b*c)
（结合律）
(L-6) a?(a*b)=a,a*(a?b)=a （吸收律）
② <B,?,*>是分配格，满足
(D-1) a?(b*c)=(a?b)*(a?c)，
a*(b?c)=(a*b)?(a*c) （分配律）
(D-2) (a?b=a?c)?(a*b=a*c)?b=c
(D-3) (a?b)*(b?c)*(c?a)=(a*b)?(b*c)?(c*a)
③ <B,?,*,’,0,1>是有界格，满足
(B-1) 0≤a≤1
(B-2) a?0=a,a*a=a （幺律）
(B-3) a?1=1,a*0=0 （零律）
④ <B,?,*,’,0,1>是有补格，满足
(C-1) a?a’=1,a*a’=0 （互补律）
(C-2) 1’=0,0’=1
⑤ <B,?,*,’,0,1>是有补分配格，满足
(CD-1) (a?b)’=a’*a’,(a*b)’=a’?b’
（德 ·摩根律）
(CD-2) a≤b?a’?b=1?a*b’=0?b’≤a’
注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。
定义 9.2.1 设 <B,?,*,’>是一代数结构，其中?和 *是 B上的二元运算，’是 B上的一元运算。
0,1?B。若对任意 a,b?B，有
① a?b=b?a,a*b=b*a （交换律）
② a?(b*c)=(a?b)*(a?c)，
a*(b?c)=(a*b)?(a*c) （分配律）
③ a?0=a,a*1=a （幺律）
④ a?a’=1,a*a’=0 （互补律）
则称 <B,?,*,’>是布尔代数，称?,*和’
分别是 B上的并、交和补运算,0和 1分别称为?
和 *的零元和幺元。
代数结构 <B,?,*,’,0,1>满足定义 9.2.1的条件,所以它是布尔代数,它是二元布尔代数 。
二元布尔代数其哈斯图是链的唯一布尔代数 。
9.3 子布尔代数、积布尔代数和布尔代数同态把子代数,积代数和同态的概念应用到布尔代数上,便得到了相应论题,本节不准备详尽叙述它,仅就其特点讨论之 。
定义 9.3.1 给定布尔代数 <B,?,⊙,’，
0,1>,?≠T?B，若 T对所有运算封闭，且 0，
1∈ T，则称 <T,?,⊙,’ >是子布尔代数。
显然,<B,?,⊙,’,0,1>和 <{0,1}，
,⊙,’,0,1>是子布尔代数。
应该指出，没有必要对所有三个运算?，
⊙ 和’都要检查封闭性，也没有必要验证 0与 1
是否在 T中，只要对运算集合 {?，’ }或
{⊙,’ }检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能集得出。因为对任意 x,y∈ S，有 x⊙ y=(x’?y’)’,0=(x’?x)’，
1=x?x’，故对于?和’的封闭便保证了 ⊙ 的封闭以及 0,1∈ T。
对于 {⊙,’ }可用同样论证。
显然，每个子布尔代数都是布尔代数。
布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否封闭而定。
定义 9.3.2 给定两个布尔代数 <B1,?1，
⊙ 1，’,01,11> <B2,?2,⊙ 2,″,02，
12>，则两个布尔代数的积也是布尔代数，称为积布尔代数，记作 <B1× B2,?3,⊙ 3，’’’，
03,13>，其中对任意 <b11,b21>,<b12，
b22>∈ B1× B2，有
<b11,b21>?3<b12,b22>=<b11?1b12，
b21?2b22>
<b11,b21>⊙ 3<b12,b22>=<b11⊙ 1b12，
b21⊙ 2b22>
<b11,b21>’’’=<b11’,b21″>
03=<01,02>,13=<11,12>
可见，积布尔代数能够生成新的布尔代数。
定义 9.3.3 给定两个布尔代数 <B,+,·，’，
0,1>和 <T,?,⊙,ˉ,α,β>，则
<B,+,·，’,0,1>?<T,?,⊙,ˉ,α，
β>,=(?f)(f∈ TB∧ (?x)(?y)(x,y∈ S→(f(x+y)=f(x)
f(y)∧ f(x·y)=f(x)⊙ f(y)∧ f(x’)= ∧ f(0)=α∧ f(1)=β)))
并称 f为从 <B,+,·，’,0,1>到 <T,?，
⊙,ˉ,α,β>的布尔同态映射。
如前所述，同态的定义仍可简化成：若保持运算 {?，’ }或 {⊙,’ }则 f∈ TB为布尔同态映射。又若 f为双射，则 f为布尔同构映射。
定理 9.3.1 若 f为从 <B,+,·，’,0,1>到
<T,?,⊙,ˉ,α,β>的布尔同态映射，且
|f(B)|≥2，其中 f(B)={y|f(x)=y∈ T∧ x∈ B}，则
<f(B),?,⊙,ˉ,f(0),f(1)>是布尔代数。
9.4 布尔代数的原子表示在布尔集合代数中,每个子集可表成单元集的并,而且这种表示在不计项的次序情况下是唯一的 。 对于任何有限布尔代数,也将有同样的结果,这里起着单元集作用的那些元素,
称它们是原子 。
定义 9.4.1 给定布尔代数 <B,?,⊙,’，
0,1>且 0≠a∈ B，则 a为原子：
=(?x)(x∈ B→ a⊙ x=a∨ a⊙ x=0)
因为 a⊙ x=a?a?x，所以上述定义又可表为
a为原子,=(?x)(x∈ S→ a?x∨ a⊙ x=0)
若 a为原子且 x?a，则 x=0或 x=a。这表明原子在偏序图中是那些紧位于零元之上的元素。
定理 9.4.1 若 a1和 a2为布尔代数 <B,?，
⊙,’ >的原子，且 a1⊙ a2≠0，则 a1=a2。
定理 9.4.2 若 x是有限布尔代数 <B,?，
⊙,’ >的非零元,则存在原子 a∈ S,使得 a?x。
定理 9.4.3 若 a,a1,a2,…,an为有限布尔代数 <B,?,⊙,’,0,1>的原子,则
a?a1?a2?…?an?(?i)(i∈ {1,2,…,
n}∧ a=ai)
定理 9.4.4 设有限布尔代数 <B,?，
⊙,’,0,1>的所有原子是 a1,a2,…,
an,且 y∈ B,则
y=0?(?i)(i∈ {1,2,…,
n}→ y⊙ ai=0)
定理 9.4.5(原子表示定理 )
给定布尔代数 <B,?,⊙,’,0，
1>,0≠x∈ B以及 i=1,2,…,n,ai?x，
则 x= ai,且不计原子的次序表示式是唯一的 。
定理 9.4.6 (斯通 (Stone)定理 )
设 <B,?,⊙,’,0,1>是有限布尔代数,
且 A表示该代数中的所有原子的集合,则 <B,?，
⊙,’,0,1>同构于幂集代数 <P(A),∪,∩，
ˉ,?,A>。
本定理说明了,能够用布尔代数的各原子,
完全确定该布尔代数,并且可用布尔集合代数
<P(A),∪,∩,ˉ,?,A>表示这一布尔代数 。
由本定理可直接得到下面推论：
|B|=2|A|
由此又可推出，若两个有限布尔代数中的集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因此可得到如下定理：
定理 9.4.7 每个有限布尔代数的集合基数均为 2的方幂，具有同样集合基数的布尔代数都是同构的。
9.5 布尔代数 Br2
为了书写方便,用 Bn表示具有 n个元素的布尔代数 <Bn,?,⊙,’ >,即 Bn=<Bn,?，
⊙,’ >。 根据定理 9.4.7可知,n必为 2的方幂 。
因此,,最小,的布尔代数即是二元布尔代数
B2=<B2,?,⊙,’ >,其中 B2={0,1}。 B2的运算表如表 9.1.1所示 。 下面再给出,次最小,
的布尔代数 B4=<B4,?,⊙,’ >的运算表 9.5.1，
其中 B4={0,α,β,1}。
特别令人感兴趣的代数结构是
B2× B2× … × B2(r个 ),即 r个相同的布尔代数 B2
的直积 。 该系统记作 Br2,且其运算符号仍与 B2
中的?,⊙ 和 ’ 相同,即 Br2=<Br2,?,⊙,’,
0r,1r>。 对任意 <σ1,σ2,…,σr>和 <δ1,
δ2,…,δr>∈ Br2,其中 σi,δj∈ {0,1},i,j=1，
2,…,n。
<σ1,σ2,…,σr>?<δ1,δ2,…,
δr>=<σ1?δ1,σ2?δ2,…,σr?δr>
<σ1,σ2,…,σr>⊙ <δ1,δ2,…,
δr>=<σ1⊙ δ1,σ2⊙ δ2,…,σr⊙ δr>
<σ1,σ2,…,σr>’ =<σ1’,σ2’,…,σr’>
0’=<0,0,…,0>和 1’=<1,1,…1>
由积代数的理论可知,Br2保持 B2中重要性质，于是断言,Br2是布尔代数，并且由定理
9.4.7能得到下面定理：
定理 9.5.1 布尔代数 <,?,⊙,’ >
与
<Br2,?,⊙,’ >是同构的，并且每个布尔代数同构于某布尔代数 Bk2=<Bk2,?，
⊙,’ >。
综上所述可知,每个布尔代数同构于某布尔集合代数 。
9.6 布尔表达式及其范式定理本节中先给出布尔表达式或布尔函数的定义,后讨论布尔表达式的范式定理 。
定义 9.6.1 给定布尔代数 <B,?,⊙,’,
0,1>及 n个变元 x1,x2,…,xn,则在 <B,?，
⊙,’,0,1>上由 n个变元产生的布尔表达式可归纳定义如下：
(1) (基础 )。 B中的任何元素和变元 xi(i=1，
2,…,n)都是一个布尔表达式。
(2) (归纳步 )。若 e1和 e2是布尔表达式，那么 e’1,(e1)?(e2)和 (e1)⊙ (e2)也是布尔表达式。
注意，当约定 ⊙ 先于?运算时，可适当省略表达式中的园括号。
如果限定 n个变元 x1,x2,…,xn都取值于
B中的元素,那么在布尔代数 <B,?,⊙,’,
0,1>上由变元 x1,x2,…,xn所产生的布尔表达式的值便表示 B中的元素 。 因此,这些表达式便是一个函数 f∈ Bn,这里 f(x1,x2,…,xn)对任意变元 x1,x2,…,xn可由布尔代数 <B,?，
⊙,’,0,1>中关于?,⊙,’ 的运算来确定 。
因此,有时将在 <B,?,⊙,’,0,1>上由变元 x1,x2,…,xn产生的布尔表达式称为在 <B，
,⊙,’,0,1>上的 n元布尔函数 (以下简称布尔函数 )。
定义 9.6.2 形如 ⊙ ⊙ … ⊙ 的布尔表达式称为由变元 x1,x2,…,xn产生的小项,
其中 δi∈ {0,1},用 x1i表示 xi,x0i表示 xi’,i∈ {1，
2,…,n},并用 表示该小项 。
形如…? 的布尔表达式称为由变元 x1,x2,…,xn产生的大项,其中
σi∈ {0,1},x1i表示 x’i,x0i表示 xi,i∈ {1，
2,…,n},并用 表示该大项 。
为书写方便，将二进制数 δ1δ2… δn和
σ1σ2… σn分别化为十进制数 i和 j作为 m和 M的下标，即 mi和 Mj。
关于小项和大项有下列关系：
mi⊙ mj=0 (i≠j)
Mi?Mj=1 (i≠j)
这是显然的，因为对于两个不同的小项 (大项 )，必有一个变元 xk，使得这两个小项 (大项 )
之一含有 xk，而另一个含有 x’k。于是，
xk⊙ xk’=0,xk?xk’=1。因此上列关系成立。
使用归纳法不难证明下列关系：
mi=1
Mi=0
定理 9.6.1(范式定理 ) 在布尔代数 <B,?，
⊙,’,0,1>上由变元 x1,x2,…,xn产生的每个布尔表达式 f(x1,x2,…,xn)均可表成：
f(x1,x2,…,xn)= (ck⊙ mk) (1)
f(x1,x2,…,xn)= (Cl?Ml) (2)
这里,k和 l分别取遍 2n个所有可能的组态
δ1δ2… δn和 σ1σ2… σn，并且
=f(δ1,δ2,…,δn)
=f(σ1,σ2,…,σn) (3)
由本定理可知,布尔代数 <B,?,⊙,’,
0,1>上的由变元 x1,x2,…,xn产生的每个布尔表达式均可表为所有小项的带,权,的并,
或者所有大项的带,权,的交,其中这些
,权,(即 cδ1δ2… δn或 Cσ1σ2… σn)是 B中的元素,它可用布尔表达式用公式 (3)计算得到 。 由于这些权是唯一的,故上述公式 (1)和 (2)便是唯一的,
并称 (1)为小项范式或析取范式,称 (2)为大项范式或合取范式 。
布尔表达式的范式也可由下面算法 9.6.1
（ 或 9.6.2） 得到 。
算法 9.6.1（ 或 9.6.2）
本算法可求出 <B,?,⊙,’ >上的布尔表达式 f(x1,x2,…,xn)范式,其具体步骤是：
(1)使用定律和定理把 f(x1,x2,…,xn)表示成形如 c⊙ ⊙ ⊙ ···⊙ （或 C?
···? ）的不同交（或并）的并（或交），其中 c,C?B且 i1<i2<··<ik。
( 2 )若每个交 （ 或并 ） 是形如 c⊙ m（ 或
C?M）,其中 c?B（ 或 C?B）,m是小项 （ 或
M是大项 ）,则增加项 (0⊙ m1)?(0⊙ m2)?···（ 或增加项 ( 1? M 1 ) ⊙ ( 1? M 2 ) ⊙ ···）,其中
m1,m2,··（ 或 M1,M2,··） 是表达式中缺乏的小项
（ 或 大 项 ）,否 则 转 到 ( 3 ) 。
(3)从最后得到的表达式中，选取形如 c⊙
⊙ ⊙ ···⊙ （或 C?
···? ）的交（或并），其中
k<n和对某个 h,（或 ）不出现，
则用
hihix?
再在新的交（或并）中按下标增加次序重新排列 （或 ），于是使用
(c1?c2?···) ⊙ m(或 (C1⊙ C2⊙ ··)?M代替
c1⊙ m,c2⊙ m,··（或 C1?M,C2?M,··）的交（或并）。转到 (2)。
因为在 <B,?,⊙,’ >上的布尔表达式 f(x1,x2,…,xn)是由 2n个权唯一确定,又因为每个权是 B中的元素,所以在
<B,?,⊙,’ >上共有 个不同布尔表达式 。
另一方面，形如 f? 的不同函数共有 个
。可见，当 |B|>2时，形如 f? 的函数中确有那些函数，它不是布尔函数。而且可以精确计算 - 个函数不是布尔函数。
例如对于 S={0,?,?,1}，函数 f? 的定义中有
f(0,0)=0,f(0,1)=1,f(1,0)=f(1,1)=?，
f(0,?)=?
则 f不是布尔函数，为什么？读者从上面的说明中是不难给出正确地回答。
