离散数学第09章.ppt

1、第九章 格与布尔代数,9.1 格 9.2 布尔代数 9.3 子布尔代数、积布尔代数 和布尔代数同态 9.4 布尔代数的原子表示 9.5 布尔代数Br2 9.6 布尔表达式及其范式定理,退出,9.1 格,1格作为偏序集 定义9.1.1 设是一个偏序集，若对任意a,b,L，存在glba,b和luba,b，则称为格，并记为a*b=glba,b，ab=luba,b，称和分别为L上的交（或积）和并（或和）运算。称为所诱导的代数结构的格。若L是有限集合，称为有限格。,格的对偶性原理是成立的： 令是偏序集，且是其对偶的偏序集。若是格，则也是格，反之亦然。这是因为，对于L中任意a和b，中luba,b等同于中g

2、lb a,b，中glba,b等同于中的luba,b。若L是有限集，这些性质易从偏序集及其对偶的哈斯图得到验证。,从上讨论中，可知两格互为对偶。互为对偶的两个和有着密切关系，即格中交运算正是格中的并运算，而格中的并运算正是格中的交运算。因此，给出关于格一般性质的任何有效命题，把关系换成（或者换成），交换成并，并换成交，可得到另一个有效命题，这就是关于格的对偶性原理。 定义9.1.2 设是格，且SL。若对任意a,bS，有a*bS和abS，则称是格的子格。,2格的基本性质 在证明格的性质前，回忆一下a*b和ab的真正含义是有好处的。 a*ba和abb，则表明a*b是a和b的下界。 若ca和cb，则c

3、a*b，这表明a*b是a和b的最大下界。 aab和bab，则表明ab是a和b的上界。 若ac，且bc，则abc，这表明ab是a和b的最小上界。,定理9.1.1 设是格，对任意a,bL，有 ab=bab a*b=aab a*b=aab=b 亦即 abab=ba*b=a,定理9.1.2 设是格，对任意a,bL，有 a*b=a, aa=a。 （幂等律） a*b=b*a, ab=ba。 （交换律） a*(b*c)=(a*b)*c a(bc)=(ab)c （结合律） a*(ab)=a a(a*b)=a （吸收律）,定理9.1.3 设是格，对任意a,b,cL，有 若ab和cd，则a*cb*d，acbd。

4、若ab，则a*cb*c，acbc。 ca和cb ca*b ac和bc abc,定理9.1.4 设是格，对任意的a,b,cL，有 a(b*c)(ab)*(ac) (a*b)(a*c)a*(bc) 通常称上二式为格中分配不等式。,定理9.1.5 设是格，对任意的a,b,cL，有 aca(b*c) (ab)*c 推论：在格中，对任意的a,b,cL，有 (a*b)(a*c)a*(b(a*c) a(b*(ac)(ab)*(ac),3特殊的格 定义9.1.3 设是格，若L中有最大元和最小元，则称为有界格。一般把格中最大元记为1，最小元记为0。 由定义可知，对任意aL，有 0a1 a*0=0, a0=a a

5、*1=a, a1=1,定理9.1.6 设是有限格，其中L=a1,a2,an，则是有界格。,定义9.1.4 设是有界格，对于aL，存在bL，使得 a*b=0，ab=1 称b为a的补元，记为a。 由定义可知，若b是a的补元，则a也是b的补元，即a与b互为补元。 显然，0=1和1=0，且易证补元是唯一的。 一般说来，一个元素可以有其补元，未必唯一，也可能无补元。,定义9.1.5 设是格，对任意的a,b,cL，有 a*(bc)=(a*b)(a*c) a(b*c)=(ab)*(ac) 则称为分配格，称和为格中分配律。,定义9.1.6 设是格，对任意的a,b,cL，有 aca(b*c)=(ab)*c 称为

6、模格。 定理9.1.7 分配格是模格 定理9.1.8 每个链都是分配格。,定理9.1.9 一个格为分配格，当且仅当它不含有任何子格与这两个五元素格中任一个同构。 定理9.1.10 设是分配格，对任意a,b,cL，有 (a*b=a*c)且(ab=ac)b=c 定理9.1.11 设是有界分配格，若aL，且补元存在，则其补元是唯一的。,定义9.1.7 设是格，若L中每个元素至少有一补元，则称为有补格。 由于补元的定义是在有界格中给出的，可知，有补格一定是有界格。 定义9.1.8 若一格既是有补又是分配的，则称该格为有补分配格，或布尔格，或布尔代数。,定理9.1.12 设是有补分配格，若任意元素aL，

7、则a的补元a是唯一的。 该定理9.1.11的直接推论，因为有补分配格当然是有界分配格。 由于有补分配格中，每个元素a都有唯一的补元a，因此可在L上定义一个一元运算补运算“”。这样，有补分配格可看作具有两个二元运算和一个一元运算的代数结构，习惯上称它为布尔代数，记为，其中B=L。,定理9.1.13 设是有补分配格，对任意a,bL，则 (a)=a (a*b)=ab (ab)=a*b 后两式称为格中德摩根律。,定理9.1.14 设是有补分配格，对任意a,bL，有 aba*b=0 ab=1 格同态，格直积等概念可以接下来定义和研究，但这里不打算这样做，因为如此进行会相对较繁，而是将格作为一个代数结构而

8、引入它们。,4格是代数结构 能自然地把代数结构中有关子代数、同态、积代数等概念，引入到格中。 定义9.1.9 设是一代数结构，其中和*是L上满足交换律、结合律和吸收律的二元运算，且对任意a,bL，定义关系如下： aba*b=a 则是格，称为代数系统所诱导的偏序集确立的格。,定义9.1.10 设和是格。存在函数f:LS，若对任意a,bL，有 f(ab)=f(a)f(b)，f(a*b)=f(a)f(b) 则称f是从到的格同态。 下述定理说明格同态是保序的。 定理9.1.15 设和是格，而和分别是给定两个格所诱导的偏序集确立的格。若f:LS是格同态，则对任意a,bL，且ab，必有f(a)f(b)。,

9、在定义9.1.10中，若f是双射函数，则称f是格同构。或称和两个格同构。由于同构是相互的，又是保序的，故对任意a,bL，有 abf(a)f(b) 和 f(a)f(b)ab 这表明同构的两个格的哈斯图是一样的，只是各结点的标记不同而已。,定义9.1.11 设和是格，定义一个代数结构如下： 对任意，LS，有 += o= 称是格和的直积。,两个格的直积也是格。这是因为在LS上，运算o和+是封闭的，且满足交换律、结合律和吸收律。 格积的阶等于两个格的阶乘积。由于是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。,

10、9.2 布尔代数,前已指出，布尔代数是有补分配格，常记为。对任意a,b,cB，有, 是格，且为B上由或*所定义的偏序关系，满足 (L-1) ab=luba,b， a*b=glba,b (L-2) abab=ba*b=a (L-3) aa=a， a*a=a （等幂律） (L-4) ab=ba， a*b=b*a （交换律） (L-5) (ab)c=a(bc)，(a*b)*c=a*(b*c) （结合律） (L-6) a(a*b)=a，a*(ab)=a （吸收律）, 是分配格，满足 (D-1) a(b*c)=(ab)*(ac)， a*(bc)=(a*b)(a*c) （分配律） (D-2) (ab=ac

11、)(a*b=a*c)b=c (D-3) (ab)*(bc)*(ca)=(a*b)(b*c)(c*a), 是有界格，满足 (B-1) 0a1 (B-2) a0=a，a*a=a （幺律） (B-3) a1=1，a*0=0 （零律） 是有补格，满足 (C-1) aa=1，a*a=0 （互补律） (C-2) 1=0，0=1, 是有补分配格，满足 (CD-1) (ab)=a*a，(a*b)=ab （德摩根律） (CD-2) abab=1a*b=0ba 注意，上述公式并非都是独立的，可从中选出一些公式作为基本公式，用它们推出其余的公式，而且可以用基本公式定义布尔代数。,定义9.2.1 设是一代数结构，其中

12、和*是B上的二元运算，是B上的一元运算。0,1B。若对任意a,bB，有 ab=ba，a*b=b*a （交换律） a(b*c)=(ab)*(ac)，a*(bc)=(a*b)(a*c) （分配律） a0=a，a*1=a （幺律） aa=1，a*a=0 （互补律）,则称是布尔代数，称、*和分别是B上的并、交和补运算，0和1分别称为和*的零元和幺元。 代数结构满足定义9.2.1的条件，所以它是布尔代数，它是二元布尔代数。二元布尔代数其哈斯图是链的唯一布尔代数。,9.3 子布尔代数、积布尔代数和布尔代数同态,把子代数、积代数和同态的概念应用到布尔代数上，便得到了相应论题，本节不准备详尽叙述它，仅就其特点

13、讨论之。,定义9.3.1 给定布尔代数，TB，若T对所有运算封闭，且0，1T，则称是子布尔代数。 显然，和是子布尔代数。,应该指出，没有必要对所有三个运算，和都要检查封闭性，也没有必要验证0与1是否在T中，只要对运算集合，或，检查其封闭性即可。这可从布尔代数中这两个运算集合是全功能集得出。因为对任意x，yS，有xy=(xy)，0=(xx)，1=xx，故对于和的封闭便保证了的封闭以及0，1T。,对于，可用同样论证。 显然，每个子布尔代数都是布尔代数。 布尔代数的子集可以是个布尔代数，但也可能不是布尔代数，因为这可从它对运算是否封闭而定。,定义9.3.2 给定两个布尔代数和，则两个布尔代数的积也是

14、布尔代数，称为积布尔代数，记作，其中对任意，B1B2，有,3= 3= = 03=，13= 可见，积布尔代数能够生成新的布尔代数。,定义9.3.3 给定两个布尔代数和，则 ：=(f)(fTB(x)(y)(x，yS(f(x+y)=f(x) f(y)f(xy)=f(x)f(y)f(x)= f(0)=f(1)=) 并称f为从到的布尔同态映射。,如前所述，同态的定义仍可简化成：若保持运算，或，则fTB为布尔同态映射。又若f为双射，则f为布尔同构映射。 定理9.3.1 若f为从到的布尔同态映射，且|f(B)|2，其中f(B)=y|f(x)=yTxB，则是布尔代数。,9.4 布尔代数的原子表示,在布尔集合代

15、数中，每个子集可表成单元集的并，而且这种表示在不计项的次序情况下是唯一的。对于任何有限布尔代数，也将有同样的结果，这里起着单元集作用的那些元素，称它们是原子。,定义9.4.1 给定布尔代数且0aB，则a为原子：=(x)(xBax=aax=0) 因为ax=aax，所以上述定义又可表为 a为原子：=(x)(xSaxax=0) 若a为原子且xa，则x=0或x=a。这表明原子在偏序图中是那些紧位于零元之上的元素。,定理9.4.1 若a1和a2为布尔代数的原子，且a1a20，则a1=a2。 定理9.4.2 若x是有限布尔代数的非零元，则存在原子aS，使得ax。 定理9.4.3 若a，a1，a2，an为有

16、限布尔代数的原子，则 aa1a2an(i)(i1，2，na=ai),定理9.4.4 设有限布尔代数的所有原子是a1，a2，an，且yB，则 y=0(i)(i1，2，nyai=0),定理9.4.5(原子表示定理) 给定布尔代数，0 xB以及i=1，2，n，aix，则x=ai，且不计原子的次序表示式是唯一的。,定理9.4.6 (斯通(Stone)定理) 设是有限布尔代数，且A表示该代数中的所有原子的集合，则同构于幂集代数。 本定理说明了，能够用布尔代数的各原子，完全确定该布尔代数，并且可用布尔集合代数表示这一布尔代数。,由本定理可直接得到下面推论： |B|=2|A| 由此又可推出，若两个有限布尔代

17、数中的集合有相同的基数，则它们的原子集合也有相同的基数。于是该二个布尔代数是同构的。因此可得到如下定理： 定理9.4.7 每个有限布尔代数的集合基数均为2的方幂，具有同样集合基数的布尔代数都是同构的。,9.5 布尔代数Br2,为了书写方便，用Bn表示具有n个元素的布尔代数，即Bn=。根据定理9.4.7可知，n必为2的方幂。因此，“最小”的布尔代数即是二元布尔代数B2=，其中B2=0，1。B2的运算表如表9.1.1所示。下面再给出“次最小”的布尔代数B4=的运算表9.5.1，其中B4=0，1。,特别令人感兴趣的代数结构是B2B2B2(r个)，即r个相同的布尔代数B2的直积。该系统记作Br2，且其

18、运算符号仍与B2中的，和相同，即Br2=。对任意和Br2，其中i，j0，1，i，j=1，2，n。,= = = 0=和1=,由积代数的理论可知，Br2保持B2中重要性质，于是断言，Br2是布尔代数，并且由定理9.4.7能得到下面定理： 定理9.5.1 布尔代数与 是同构的，并且每个布尔代数同构于某布尔代数Bk2=。 综上所述可知，每个布尔代数同构于某布尔集合代数。,9.6 布尔表达式及其范式定理,本节中先给出布尔表达式或布尔函数的定义，后讨论布尔表达式的范式定理。 定义9.6.1 给定布尔代数及n个变元x1，x2，xn，则在上由n个变元产生的布尔表达式可归纳定义如下：,(1) (基础)。B中的任

19、何元素和变元xi(i=1，2，n)都是一个布尔表达式。 (2) (归纳步)。若e1和e2是布尔表达式，那么e1，(e1)(e2)和(e1)(e2)也是布尔表达式。 注意，当约定先于运算时，可适当省略表达式中的园括号。,如果限定n个变元x1，x2，xn都取值于B中的元素，那么在布尔代数上由变元x1，x2，xn所产生的布尔表达式的值便表示B中的元素。因此，这些表达式便是一个函数fBn，这里f(x1，x2，xn)对任意变元x1，x2，xn可由布尔代数中关于，的运算来确定。因此，有时将在上由变元x1，x2，xn产生的布尔表达式称为在上的n元布尔函数(以下简称布尔函数)。,定义9.6.2 形如 的布尔表

20、达式称为由变元x1，x2，xn产生的小项，其中i0，1，用x1i表示xi，x0i表示xi，i1，2，n，并用 表示该小项。 形如 的布尔表达式称为由变元x1，x2，xn产生的大项，其中i0，1，x1i表示xi，x0i表示xi，i1，2，n，并用 表示该大项。,为书写方便，将二进制数12n和12n分别化为十进制数i和j作为m和M的下标，即mi和Mj。 关于小项和大项有下列关系： mimj=0 (ij) MiMj=1 (ij),这是显然的，因为对于两个不同的小项(大项)，必有一个变元xk，使得这两个小项(大项)之一含有xk，而另一个含有xk。于是，xkxk=0，xkxk=1。因此上列关系成立。 使用归纳法不难证明下列关系： mi=1 Mi=0,定理9.6.1(范式定理) 在布尔代数上由变元x1，x2，xn产生的每个布尔表达式f(x1，x2，xn)均可表成： f(x1，x2，xn)= (ckmk) (1) f(x1，x2，xn)= (ClMl) (2),这里，k和l分别取遍2n个所有可能的组态12n和12n，并且 =f(1，2，n) =f(1，2，n) (3),由本定理可知，布尔代数上的由变元x1，x2，xn产生的每个布尔表达式均可表为所有小项的带“权”的并，或者所有大项的带“权”的交，其中这些“权”(即c12n或C12n)是B中的元素，它可用布尔表达式用公式(3