《第07章格与布尔代数课件》由会员分享，可在线阅读，更多相关《第07章格与布尔代数课件（81页珍藏版）》请在金锄头文库上搜索。
1、引言 7.1格 7.2分配格 7.3有补格 7.4布尔代数 7.5布尔表达式,第七章 格与布尔代数,对于计算机科学来说，格与布尔代数是两个重要的代数系统。 在开关理论计算机的逻辑设计，及其它一些科学领域中，都直接应用了格与布尔代数。,引 言,引 言,格的结构是基于偏序关系。 偏序：自反、反对称、传递。 布尔代数是特殊的格。命题代数和集合代数都是布尔代数的特例。 此两个系统有一个重要特点：强调次序关系。,7.1格,一、格的定义 1、概念 2、对偶原理 3、基本性质 二、格是代数系统 1、作为代数系统的格的定义 2、偏序集合的格、代数集合的格的关系 三、子格 1、子格 2、格同态,一、格的定义,(
2、1)若集合A上的二元关系满足自反性、反对称性、传递性，称A为偏序集合。aRb记为ab, 它可用哈斯图表示。,1、偏序集合的一些概念,(2) 设A,是偏序集合，B是A的子集。 若bB，ba，则a是子集B的上界。,若a也是B的上界，有aa，称a是子集B的最小上界，记为lub (B);,若 bB，ab，则a是子集B的下界。,若a也是B的下界，有aa，称a是子集B的最大下界，记为glb(B)。,(3)最大下界、最小上界若存在，则唯一。,设A,是偏序集，若a,bA，都有最大下界、最小上界；则称A,是个格，且记 glb(a,b)=ab， lub(a,b)=ab, 并称它们为交和并。,注1：由于最大下界、最
3、小上界若存在则唯一，所以交、并是二元运算；,注2：称为由格所诱导的代数系统。,一、格的定义,例1：设n是正整数，Sn是n的正因子的集合。D为整除关系，则偏序集构成格。x, ySn，xy是lcm(x,y)，即x与y的最小公倍数。xy是gcd(x,y)，即x与y的最大公约数。,1、格的实例,例2：判断下列偏序集是否构成格，并说明理由。 (1) ，其中(B)是集合B的幂集。 (2) ，其中Z是整数集，为小于或等于关系。 (3) 偏序集的哈斯图分别在图中给出。,1、格的实例,解： (1) 是格。 x,y (B)，xy就是xy，xy就是xy。 由于和运算在(B)上是封闭的，所以xy，xy (B)。称，为
4、B的幂集格。 (2) 是格。 x,yZ,xymax(x,y)，xymin(x,y)，它们都是整数。 (3) 都不是格。 (a) 中的a,b没有最大下界。 (b) 中的b,d有两个上界c和e，但没有最小上界。 (c) 中的b,c有三个上界d,e,f，但没有最小上界。 (d) 中的a,g没有最大下界。, 集合S的偏序关系的逆关系也是偏序关系，若AS, 其中 的glb(A) 对应于 的lub(A), 的lub(A) 对应于 的glb(A), 所以，若是格，则也是格， 称这两个格互为对偶。,2、格的对偶原理, 因为的交是的并， 的并是的交， 所以，关于格的一般性质的任意命题， 如用替换，用替换，用替换
5、， 格的一般性质的任意命题仍成立，这称为格的对偶原理。,2、格的对偶原理,1）自反性 aa 对偶：aa 2）反对称性 ab ba a=b 对偶：ab ba a=b 3）传递性 ab bc ac 对偶：ab bc ac,3、格的基本性质,4）最大下界描述之一 aba 对偶：aba abb 对偶：abb 5）最大下界描述之二 ca,cb cab 对偶：ca,cb cab,3、格的基本性质,6）结合律 a(bc)=(ab)c 对偶：a(bc)=(ab)c 证：令R=a(bc)，R=(ab)c 则由4） Ra, Rbc Ra, Rb, Rc Rab, Rc R(ab)c RR 同理可证：RR 所以 R
6、=R 注：格的证明思路总是利用反对称性。,3、格的基本性质,7）等幂律 aa=a 对偶： aa=a,8）吸收律 a(ab)=a 对偶： a(ab)=a,证：因为 aab, aa 所以 aa(ab) 又 aa(ab) 所以 a = a(ab),3、格的基本性质,证：） ab aa, ab aab 又 aab a=ab ） ab=a 若ba且ba, 则与ab=a 矛盾 若a,b不可比较，则与ab=a 矛盾 ab,9)ab ab=a ab ab=b,3、格的基本性质,证： aba, ac abc abb, bd abd abcd 同理可证： ac, bd abcd,10) ac,bd abcd ab
7、cd,3、格的基本性质,证：因为aa, bc 由性质10) 知 abac # 同理可证： abac,11）保序性 bc abac abac,3、格的基本性质,证： aab, aac a(ab)(ac) bab, cac bc(ab)(ac)（性质10） a(bc)(ab)(ac),12）分配不等式 a(bc)(ab)(ac) 对偶：a(bc)(ab)(ac),3、格的基本性质,证：）若ac 则ac=c 代入分配不等式 a(bc)(ab)(ac)=(ab)c ）若a(bc)(ab)c 因为aa(bc)(ab)c c 所以ac,13）模不等式 ac a(bc)(ab)c,3、格的基本性质,（可用代
8、数系统的有关概念应用于格）,1、作为代数系统的格的定义,设是个代数系统，, 是L上二个二元运算，若二元运算,均满足结合律、交换律、吸收律(a(ab)=a，a(ab)=a)、等幂律(aa=a，aa=a)，称是格。,注：定义中的等幂律可以消除，因它可由吸收律推得。 aa= a( a( aa)=a,二、格是代数系统,定理4：若是一个格（作为代数系统），那么，L中存在一偏序关系，使a,bL，有： ab=lub(a,b), ab=glb(a,b)。,2、偏序集合的格、代数系统的格二者定义是等价的。,二、格是代数系统,分三步： 1) 证明是L上的偏序关系 2）证明 a,bL, a,b的下确界存在， 且 a
9、b = glb(a,b)。 3）a,bL, a,b的上确界存在，且 lub(a,b) ab 具体证法见后面,偏序集合的格、代数系统的格二者定义是等价的证明 证：在集合L上定义的二元关系如下： a,bL，若ab ab = a,1) 证明是L上的偏序关系 自反性：aL 由等幂律 aa=a, aa 反对称性：a,bL, 若ab, ba 则 ab=a, ba=b a = ab = ba = b 传递性：a,b,cL, 若 ab,bc 则ab=a, bc=b ac=(ab)c = a(bc)= ab=a ac,2）证明 a,bL, a,b的下确界存在， 且 ab=glb(a,b)。,b) 设c 是a,b
10、 的任一下界， 即cb, ca 则cab 因为 c(ab)= (ca)b=cb=c cab ab 是a,b的下界。,a) 因为(ab)a =(aa)b=ab aba 同理abb ab 是a,b的下界。,3) 同理可证：a,bL, a,b的上确界存在， 且lub(a,b)=ab,由1）2）3）知：是一个格。 以后可根据需要，随意使用这二种定义和记法。,1、子格定义： 是个格，SL，若S对运算和封闭，则称是的子格。,子格是个格，因结合律、交换律、吸收律是继承的。,三、子格、格同态,例：设格L如图所示。令 S1=a，e，f，g， S2=a，b，e，g 则S1不是L的子格，S2是L的子格。因为对于e和
11、f，有ef=c，但cS1,2、格同态定义： ，是二个格，f：SL 且a,bS 有f(a*b)=f(a)f(b) f(ab)=f(a)f(b) 称f是到的格同态；若f是双射则称和是同构的。,三、子格、格同态,例： (1)设L1=2n|nZ+， L2=2n+1|nN 则L1和L2关于通常数的小于或等于关系构成格。 令 f：L1L2，f(x)=x-1 不难验证f是L1到L2的同态映射，因为对x, yL1有： f(xy)=f(max(x, y)=max(x, y)-1 f(x)f(y)=(x-1) (y-1)=max(x-1, y-1)=max(x, y)-1 f(xy)=f(min(x, y)=mi
12、n(x, y)-1 f(x)f(y)=(x-1)(y-1)=min(x-1, y-1)=min(x, y)-1 即： f(xy) = f(x)f(y)， f(xy) = f(x)f(y) 成立。,定理：若a,bL，ab 则f(a)f(b),证： ab a*b=a f(a)f(b)=f(a*b)=f(a) f(a)f(b),注1：保序的函数不一定是同态的。, 格同态是保序的,三、子格、格同态,S12，整除* S12，小于等于 f: S12 S12，f(x)=x， 则f是保序的。 即ab f(a)f(b) 但f不是同态映射: f(3*2) f(3)f(2) ( f(3*2)=f(1)=1 ，f(3
13、)f(2)=2 ),例1：,三、子格、格同态,证：）f是格同构 由“格同态是保序的”知：ab f(a)f(b) 反之，设f(a)f(b) 则：f(a)=f(a)*f(b)=f(ab) 因为f是双射, a= ab ab,例2：设f是双射，则f是到的格同构，当且仅当a,bA1，ab f(a)f(b),）已知a,bA1, ab f(a)f(b) 需证f是同构, 即证：f(ab)= f(a)*f(b) 证：令 c= ab 则 ca f(c)f(a) cb f(c)f(b) f(c)f(a)*f(b) 令 f(a)*f(b)=f(d) 则 f(d)f(a) da f(d)f(b) db dab=c f(
14、d)f(c) f(c)=f(d) f(ab)=f(a)*f(b)证毕,由此看出，同构的二个格，其哈斯图相同。,三、子格、格同态,因为，三个元素的偏序集合（同构意义下）仅有：,例3：具有一、二、三个元素的格，分别同构于一、二、三元素的链。,四个元素的偏序集合（同构意义下） 仅有：,三、子格、格同态,三、子格、格同态,同理，五个元素的格仅为：,7.2分配格,一、定义 二、性质,7.2分配格,一般格只满足分配不等式： a(bc)(ab)(ac),设是格，若a,b,cL，有： (1) a(bc)=(ab)(ac), (2) a(bc)=(ab)(ac), 则称 为分配格。,注：(1)(2)是互相等价的
15、，由对偶原理，从一式可推得另一式。,一、定义,例：,L1和L2是分配格，L3和L4不是分配格。 在L3中：b(cd)=be=b， (bc)(bd)=aa=a 在L4中：c(bd)=ca=c， (cb)(cd)=ed=d 称L3为钻石格，L4为五角格。,7.2分配格,二、性质 1、设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构的子格。 由于该定理的证明比较繁且已超出本课程的范围，故此略去，只要掌握它的应用就行了。 小于五元的格都是分配格。,2、任何一条链是分配格。 证：设是一个链，a,b,cL (1) ab 或ac 则：a(bc)=a, (ab)(ac)=a (2) ba 且 ca bc a 则有：a(bc)=bc 和 (ab)(ac)=bc 即：a(bc)=(ab)(ac) 是分配格。,7.2分配格,7.2分配格,证：(ab)c=(ac)c=c (ac)(bc)=(ab)(bc) =(ba)(bc) =b(ac) =b(ab) =b,3、设是分配格，则 a,b,cL (ab=ac)(ab=ac) b=c,7.3有补格,1、全上（全下界）定义 2、有界格 3、补元 4、有补格 5、有补分配格,7.3有补格,1、全上界（全下界）定义 给定格，若存在aL，使bL,有ba (ab)，称 a为的全上界（全下界）。,证：若存在两个全上界a,b，则有： a是全上界，
