《离散数学第09章》由会员分享，可在线阅读，更多相关《离散数学第09章（70页珍藏版）》请在金锄头文库上搜索。
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等同于中gl
2、b 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，则ca
3、*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)*ca(bc)=(ab)c （结合律） a*(ab)=aa(a*b)=a （吸收律）,定理9.1.3 设是格，对任意a,b,cL，有 若ab和cd，则a*cb*d，acbd。 若ab
4、，则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*1=
5、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，则a的
7、补元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=0ab=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和+是封闭的，且满足交换律、结合律和吸收律。 格积的阶等于两个格的阶乘积。由于是一个格，故又可以与另一个格作直积，这样，利用格的直积可用较小阶的格构造出阶越来越大的格。但反之，较大阶的格，并不都能表示成较小阶的格直积。,9.2 布
10、尔代数,前已指出，布尔代数是有补分配格，常记为。对任意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)(a*b
11、=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 设是一代数结构，其中和*是B上
12、的二元运算，是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 布尔代数的原子表示,在布尔集合代数中，每个子集可表成单元集的并，而且这种表示在不计项的次序情况下是唯一的。对于任何有限布尔代数，也将有同样的结果，这里起着单元集作用的那些元素，称它们是原子。,定义9.4.1 给定布尔代数且0aB，则a为原子：=(x)(xBax=aax=0) 因为ax=aax，所以上述定义又可表为 a为原子：=(x)(xSaxax=0) 若a为原子且xa，则x=0或x=a。这表明原子在偏序图中是那些紧位于零元之上的元素。,
