新编第07章格与布尔代数课件

1、引言7.1格7.2分配格7.3有补格7.4布尔代数7.5布尔表达式第七章 格与布尔代数对于计算机科学来说，格与布尔代数是两个重要的代数系统。在开关理论计算机的逻辑设计，及其它一些科学领域中，都直接应用了格与布尔代数。引 言引 言格的结构是基于偏序关系。偏序：自反、反对称、传递。布尔代数是特殊的格。命题代数和集合代数都是布尔代数的特例。此两个系统有一个重要特点：强调次序关系。7.1格一、格的定义1、概念2、对偶原理3、基本性质二、格是代数系统1、作为代数系统的格的定义2、偏序集合的格、代数集合的格的关系三、子格 1、子格2、格同态一、格的定义(1)若集合A上的二元关系满足自反性、反对称性、传递性

2、，称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：由于最大下界、最小上界若存在则唯一，所以交、并是二元运算；注2：称为由格所诱

3、导的代数系统。 一、格的定义例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)。称，为B的幂集格。(2) 是格。 x,yZ,xymax(x,y)，xymin(x,y)，

4、它们都是整数。(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、格的对偶原理 因为的交是的并， 的并是的交， 所以，关于格的一般性质的任意命题， 如用替换，用替换，用替换， 格的一般性质的任意命题仍成立，这称为格的对偶原理。2、格的对偶原理1）自反性 aa 对偶：aa2

5、）反对称性 ab ba a=b 对偶：ab ba a=b3）传递性 ab bc ac 对偶：ab bc ac 3、格的基本性质4）最大下界描述之一 aba 对偶：aba abb 对偶：abb5）最大下界描述之二 ca,cb cab 对偶：ca,cb cab3、格的基本性质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=R注：格的证明思路总是利用反对称性。3、格的基本性质7）等幂律 aa=a 对偶： aa=a8）吸收律 a(ab)=a

6、 对偶： 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 矛盾 ab9)ab ab=a ab ab=b3、格的基本性质证： aba, ac abc abb, bd abd abcd同理可证： ac, bd abcd10) ac,bd abcd abcd3、格的基本性质证：因为aa, bc 由性质10) 知 abac #同理可证： abac11）保序性 bc abac abac3、格的基本

7、性质证： 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 所以ac13）模不等式 ac a(bc)(ab)c3、格的基本性质（可用代数系统的有关概念应用于格）1、作为代数系统的格的定义 设是个代数系统，, 是L上二个二元运算，若二元运算,均满足结合律、交换律、吸收律(a(ab)=a，a(ab)=

8、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的下确界存在， 且 ab = glb(a,b)。 3）a,bL, a,b的上确界存在，且 lub(a,b) ab 具体证法见后面偏序集合的格、代数系统的格二者定义是等价的证明证：在集合L上定义的二元关

9、系如下： a,bL，若ab ab = a1) 证明是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 的任一下界， 即cb, ca 则cab 因为 c(ab)= (ca)b=cb=c cab ab 是a,b的下界。a) 因为(ab)a =(aa)b=ab aba 同理abb ab 是a

10、,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和f，有ef=c，但cS12、格同态定义： ，是二个格，f：SL 且a,bS 有f(a*b)=f(a)f(b) f(ab)=f(a)f(b) 称f是到的格同态；若f是双射则称和是同构的。三、子格、格同态例：

11、 (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)=min(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

12、，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)f(2)=2 )例1：12421 6 31264231三、子格、格同态证：）f是格同构 由“格同态是保序的”知：ab f(a)f(b) 反之，设f(a)f(b) 则：f(a)=f(a)*f(b)=f(ab)因为f是双射

13、, 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(d)f(c) f(c)=f(d) f(ab)=f(a)*f(b)证毕由此看出，同构的二个格，其哈斯图相同。 三、子格、格同态 因为，三个元素的偏序集合（同构意义下）仅有： 例3：具有一、二、三个元素的格

14、，分别同构于一、二、三元素的链。 四个元素的偏序集合（同构意义下） 仅有： 三、子格、格同态三、子格、格同态同理，五个元素的格仅为：7.2分配格一、定义二、性质7.2分配格一般格只满足分配不等式： a(bc)(ab)(ac)设是格，若a,b,cL，有：(1) a(bc)=(ab)(ac), (2) a(bc)=(ab)(ac),则称 为分配格。注：(1)(2)是互相等价的，由对偶原理，从一式可推得另一式。一、定义例：L1和L2是分配格，L3和L4不是分配格。在L3中：b(cd)=be=b， (bc)(bd)=aa=a在L4中：c(bd)=ca=c， (cb)(cd)=ed=d称L3为钻石格，L

15、4为五角格。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) =

16、b3、设是分配格，则 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是全上界， ab， 又 b是全上界， ba 所以 b=a注：可以证明，一个格的全上界（全下界）是唯一的。7.3有补格2、有界格定义： 存在全上界和全下界的格，称为有界格；全上界记为1，全下界记为0，并称它们为格的界。记为：注：由定义知，0是的幺元，1是的幺元。不难

17、看出，有限格L一定是有界格。设L是n元格，且L=a1，a2，an，那么a1a2an是L的全下界，而a1a2an是L的全上界。因此L是有界格。对于无限格L来说，有的是有界格，有的不是有界格。如：集合B的幂集格，不管B是有穷集还是无穷集，它都是有界格。它的全下界是空集 ，全上界是B。而整数集Z关于通常数的小于或等于关系构成的格不是有界格，因为不存在最小和最大的整数。7.3有补格3、补元定义： 设是有界格，aL，若存在bL，有：ab=0，ab=1，称b为a的补元，记为a。注： 若a是b的补元，则b也是a的补元; 补元可以不存在，可以不唯一。例：a) a的补元是b,c b的补元是a,c, c的补元是a

18、,b b) a,b,c 均不存在补元 c) 有界格中，0，1互为补元证：因为01=0，01=1 所以0, 1互为补元。c1b0a1bc0 a7.3有补格例：考虑下图中的四个格。L1中的a与c互为补元，其中a为全下界，c为全上界，b没有补元。L2中的a与d互为补元，其中a为全下界，d为全上界，b与c 也互为补元。L3中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和d，c的补元是b和d，d的补元是b和c。b，c，d每个元素都有两个补元。L4中的a与e互为补元，其中a为全下界，e为全上界，b的补元是c和d，c的补元是b，d的补元是b。7.3有补格4、有补格定义： 若在一个有界格中，每个

19、元素至少有一个补元，则称此格为有补格。例：右图中的L2，L3和L4是有补格，L1不是有补格。右图中的L2和L3是有补格，L1不是有补格。7.3有补格5、有补分配格定义： 若一个格既是有补格，又是分配格，则此格称为有补分配格，又称布尔代数。 例：集合运算，命题运算，开关代数为布尔代数,(因为满足结合律、交换律、吸收律、分配律、存在补元及0，1）1）有补分配格中，任何元素的补元是唯一的。证明：设b，c都是a的补元，则 1）ab=0=ac，ab=1=ac 由分配格的可约性， b=c7.3有补格2）有补分配格满足德摩根定律，即（1）(ab)=ab （2）(ab)=ab证：(ab)(ab)=(aab)(

20、bab) =00=0 (ab)(ab)=(aba)(abb) =11=1 由有补分配格的补元唯一性，(ab)=ab 由对偶原理 (ab)=ab7.3有补格7.4 布尔代数一、布尔代数的定义二、布尔代数的子代数三、布尔代数的同态映射四、有限布尔代数的结构一、布尔代数的定义1、布尔代数作为的格的定义2、布尔代数的性质3、布尔代数作为代数系统的定义7.4 布尔代数7.4 布尔代数一、布尔代数的定义1、布尔代数作为格的定义如果一个格是有补分配格，则称它为布尔格或布尔代数。7.4 布尔代数例：设S110=1，2，5，10，11，22，55，110是110的正因子集合。令gcd，lcm分别表示求最大公约数

21、和最小公倍数的运算。 问是否构成布尔代数？为什么？ 解：容易验证x, yS110，有：gcd(x, y)S110和lcm(x, y)S110。且x,y,zS110有：gcd(x, y) = gcd(y, x) (交换律)lcm(x, y) = lcm(y, x)gcd(gcd(x, y), z) = gcd(x, gcd(y, z) (结合律)lcm(lcm(x, y), z) = lcm(x, lcm(y, z)gcd(x, lcm(x, y) = x(吸收律)lcm(x, gcd(x, y) = x因此，构成格。下面证明它是分配格。易验证x，y，zS110 有：gcd(x, lcm(y,

22、z)=lcm(gcd(x, y), gcd(x, z)1作为S110中的全下界，110为全上界，且：1和110互为补元，2和55互为补元，5和22互为补元，10和11互为补元，从而证明了为布尔代数。 例：设B为任意集合，证明B的幂集格构成布尔代数，称为集合代数。证：(B)关于和构成格，因为：和运算满足交换律、结合律、吸收律。由于和互相可分配，因此(B)是分配格，且全下界是空集，全上界是B。根据绝对补的定义，取全集为B，x(B)，xBx 是 x 的补元。从而证明(B)是有补分配格，即布尔代数。 2、布尔代数的性质【定理】设是布尔代数，则(1) aB，(a)=a 。(2) a，bB， (ab)=a

23、b， (ab)= ab【证】(1) (a)是a的补元。a也是a的补元。由补元的唯一性得(a)=a。双重否定律德摩根律(2) 对 a，bB有：(ab)(ab)=(aab)(bab) = (1b)( a1) = 11 = 1，(ab)(ab)=(aba)(abb) = (0b)(a0) = 00 = 0，所以ab是ab的补元，根据补元的唯一性有：(ab)=ab同理可证：(ab)= ab。定义：设是代数系统，*和是二元运算。若*和运算满足：(1) 交换律，即a，bB有：a*b=b*a， ab=ba (2) 分配律，即a，b，cB有： a*(bc)=(a*b) (a*c)， a (b*c)=(ab)*

24、(ac) (3) 同一律，即存在0，1B，使得aB有：a*1=a， a0=a (4) 补元律，即aB，存在aB使得a*a=0， aa=1 则称是一个布尔代数。3、布尔代数作为代数系统的定义 二、布尔代数的子代数定义：设是布尔代数，S是B的非空子集，若0, 1S，且S对, 和 运算都是封闭的，则称S是B的子布尔代数。二、布尔代数的子代数例1：设是布尔代数，a,bB，且ab。令Sx|xB，且axb称S为B中的区间，可简记为a,b。可以证明a,b是一个布尔代数。显然S是B的非空子集，且a和b分别为S的全下界和全上界对任意的x,yS都有 axb，ayb从而有 axyb, axybS关于和运算是封闭的。

25、易见和运算在S上适合交换律和分配律。对任意的 xS，令 y(ax)b (下面证明y为x得补元。)由于 aax，ab，故 a(ax)b。同时(ax)bb，因此 yS。又xy x(ax)b) x(ab)(xb)(分配律) xa(xb) (ab) x(xb) (ax) (xx)(xb) (分配律) 1(xb) (补元律) xb (交换律，同一律) b(xb) xy x(ax)b) x(ax) (xb,交换律) (xa)(xx) (分配律) (xa)0 (补元律) xa (同一律) a (ax) 根据定义(布尔代数作为代数系统的定义)，构成布尔代数。其全上界是a，全下界是b。 xa,b，x关于这个全上

26、界和全下界的补元是(ax)b。当a0且b1时，a,b是B的子布尔代数。但当a0或b1时，a,b不是B的子布尔代数。 二、布尔代数的子代数例2：考虑110的正因子集合：S110 = 1, 2, 5, 10, 11, 22, 55, 110S110关于gcd，lcm运算构成的布尔代数。它有以下的子布尔代数：1, 1101, 2, 55, 1101, 5, 22, 1101, 10, 11,1 101, 2, 5, 10, 11, 22, 55, 110 三、布尔代数的同态映射定义：设和是两个布尔代数。这里的，泛指布尔代数B2中的求最大下界，最小上界和补元的运算。和E分别是B2的全下界和全上界。f: B1B2。如果对于任意的a，bB1有：f(ab) = f(a)f(b)f(ab) = f(a)f(b)f(a) = f(a)则称 f是布尔代数B1到B2的同