您现在的位置:首页 > >

离散数学第09章 格和布尔代数

发布时间:

第九章 格与布尔代数
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 (fx(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,

?则n x=

ai,且不计原子的次序表示式是

i?1
唯一的。

定理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}。

表9.5.1 ?0??1 ⊙0??1 x x’
0 0??1 0 0000 0 1 ???11 ?0?0? ? ? ? ?1?1 ? 00?? ? ? 1 1111 1 0??1 1 0

特别令人感兴趣的代数结构是
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 布尔代数< B 2 r ,?,⊙,’>

<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元布尔函数(以下简称 布尔函数)。

x x 定义9.6.2 形如 1? 1 ⊙ 2 ?⊙2 …⊙ x n ? n的布
尔表达式称为由变元x1,x2,…,xn产生的小项,

其中δi∈{0,1},用x1i表示xi,x0i表示xi’,i∈{1,

x m 2,…,n},并用
形如 x1??1 x 2??2 …?

?1?表2??示n?的该n 布小尔项表。达式 n

称 为 由 变 元 x1 , x2 , … , xn 产 生 的 大 项 , 其 中

σi∈{0 , 1} , x1i 表 示 x’i , x0i 表 示 xi , i∈{1 ,

2,…,n},并用 M?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。因此上列关系成立。
使用归纳法不难证明下列关系:
2n ?1
? mi=1
i? 0
2n ?1
? Mi=0
i? 0

定理9.6.1(范式定理) 在布尔代数<B,?, ⊙,’,0,1>上由变元x1,x2,…,xn产生的 每个布尔表达式f(x1,x2,…,xn)均可表成:

11 ? 1

? f(x1,x2,…,xn)=

(ck⊙mk) (1)

k ? 00 ? 0

11 ? 1

? f(x1,x2,…,xn)=

(Cl?Ml) (2)

l ? 00 ? 0

这里,k和l分别取遍2n个所有可能的组态 δ1δ2…δn和σ1σ2…σn,并且

c?1? 2?? n =f(δ1,δ2,…,δn)

C ?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)表

x x x 示成形如c⊙

? i1⊙
i1

? i 2 ⊙···⊙ i2

? ik(或
ik

x x C?i1 ? i1

? i2
i2

x? ? ik ik

?···?

)的不同交(或并)的并(或

交),其中c,C?B且i1<i2<···<ik。

(2)若每个交(或并)是形如c⊙m(或 C?M),其中c?B(或C?B),m是小项(或 M是大项),则增加项 ( 0 ⊙ m 1 ) ? ( 0 ⊙ m 2 ) ? ···( 或 增 加 项 (1?M1)⊙(1?M2)⊙···),其中m1,m2,···(或 M1,M2,···)是表达式中缺乏的小项(或大项), 否则转到(3)。

(3)从最后得到的表达式中,选取形如c⊙

x x x x i1 ? i1⊙

?i2 i2 ⊙···⊙

ik ? ik (或C?

? i1 i1

x x ?

i2 ? i 2 ?···?

? ikxih?ih)的交(或并),其中
ik

x k<n和对某个h,

(? ih或
ih

x ? ih)不出现, ih

则用

再在新的交(或并)中按下标增加次序重

x x 新排列 i j ? i j(或

ik ? ik ),于是使用

(c1?c2?···)⊙m(或(C1⊙C2⊙···) ?M代替

c1⊙m,c2⊙m,···(或C1?M,C2?M,···)的交(或

并)。转到(2)。

因为在<B,?,⊙,’>上的布尔表

达式f(x1,x2,…,xn)是由2n个权唯一确

定,又因为每个权是B中的元素,所以在

<B,?,⊙,’>上| B共|2有n

个不同布尔

表达式。

B 另一方面,形如f? B n 的不同函数共有 个
S | B ||B。|n 可见,当|B|>2时,形如f? S n 的函数

中确有那些函数,它不是布尔函数。而且可以

精确计算 | S

||S |n

-| S

|2

n
个函数不是布尔函数。

B 例如对于S={0,?,?,1},函数f? B n 的定
义中有 f(0,0)=0,f(0,1)=1,f(1,0)=f(1,1)=?,
f(0,?)=? 则f不是布尔函数,为什么?读者从上面的
说明中是不难给出正确地回答。



热文推荐
猜你喜欢
友情链接: 幼儿教育 小学教案 初中教案 高中教案 职业教育 成人教育