格与布尔代数课件2.ppt

1、第六章第六章 格与布尔代数格与布尔代数1 1、格的基本概念、格的基本概念2 2、分配格、分配格3 3、有补格、有补格非本次期末考试内容非本次期末考试内容4 4、布尔代数、布尔代数5 5、布尔表达式、布尔表达式第1页，共28页。1 1 格的基本概念格的基本概念 图、三个偏序集哈斯图图、三个偏序集哈斯图1262324361246231123定义定义1 1：设：设是一个偏序集，若是一个偏序集，若A A中任意两个中任意两个 元素都有元素都有最大下界最大下界和和最小上界最小上界，则称，则称 为格。为格。格格格格不是格不是格第2页，共28页。例：判断例：判断I,D、P(S),、S,D 是否是格。是否是格。

2、其中其中:I:I+是正整数，是正整数，D D是整除关系，是整除关系，S Sn n =n=n的所有因子的所有因子 如：如：S S6 6=1,2,3,6=1,2,3,6、S S8 8=1,2,4,8=1,2,4,8、S S1212=1,2,3,4,6,12=1,2,3,4,6,12、S S3030=1,2,3,5,6,10,15,30=1,2,3,5,6,10,15,30解：解：是格是格 整除关系是偏序关系，对整除关系是偏序关系，对 a,b I，a、b的最小上界等于的最小上界等于a、b的最小公倍数，的最小公倍数，a、b的最大上界等于的最大上界等于a、b的最大公约数。的最大公约数。第3页，共28页。

3、是格是格 子集关系是偏序关系，对子集关系是偏序关系，对 a,b P(S)，a、b的最小上界等于的最小上界等于ab，a、b的最大上界等于的最大上界等于ab。是格，偏序关系的哈斯图如下：是格，偏序关系的哈斯图如下：12368421312641212351563010=,第4页，共28页。45312671234576这两个图是偏序关系，但不是格。这两个图是偏序关系，但不是格。第5页，共28页。定义定义2 2：格代数：格代数设设是一个格，若在是一个格，若在A A上定义两个二元运算上定义两个二元运算和和,使得对于使得对于 a,ba,b A,A,abab等于等于a a和和b b的最小上界的最小上界,ab,

4、ab等于等于a a和和b b的最大下界的最大下界,则称则称为由格为由格所诱导的代数系统。所诱导的代数系统。二元运算二元运算和和分别称为分别称为并运算并运算和和交运算交运算。显然，显然，所诱导的代数系统为所诱导的代数系统为 第6页，共28页。1 2 3 6 1 2 3 6 1 1 2 3 6 1 1 1 1 1 2 2 2 6 6 2 1 2 1 2 3 3 6 3 6 3 1 1 3 3 6 6 6 6 6 6 1 2 3 6S6=1,2,3,6，则，则是一个格是一个格1236下面的运算表表示的系统下面的运算表表示的系统就是由格就是由格所所诱导诱导的代数系统的代数系统第7页，共28页。定义定义

5、3 3：设：设是一个格，由格是一个格，由格所诱导的所诱导的代数系统为代数系统为。设。设B B A A且且B B ，如果运算，如果运算和和在在B B上封闭上封闭，则称，则称 是是的的子格子格。注：注：(1)可以证明子格必是格（证明略）可以证明子格必是格（证明略）(2)不能理解为：不能理解为：B A且且 是格，则是格，则 是是 的子格。应特别注意条件的子格。应特别注意条件:“运算运算和和在在B B上封闭上封闭”。(3)对于格对于格，B A且且B，则，则 一定是一定是 偏序集，但不一定是格。偏序集，但不一定是格。第8页，共28页。例：例：B1=1,2,3,6，B2=5,10,15,30，和和都是都是

6、 的子格。的子格。1 2 3 6 1 2 3 6 1 1 2 3 6 1 1 1 1 1 2 2 2 6 6 2 1 2 1 2 3 3 6 3 6 3 1 1 3 3 6 6 6 6 6 6 1 2 3 6可见运算可见运算和和在在B1上封闭，上封闭，B1 S30 且且B1 是是 的子格，同理可证的子格，同理可证是是 的子格的子格2315156301012365153010第9页，共28页。2315163010例：例：B3=1,2,3,6,10,15,30，显然，显然 是格。是格。但但1015=5 B3，即，即运算在运算在B3上不封闭，上不封闭，不是不是 的子格。的子格。23151563010

7、例：例：B4=2,3,6，则，则 是偏序集，是偏序集，不是格，更不是不是格，更不是的子格。的子格。236第10页，共28页。对偶原理：对偶原理：设设P P是对任意格都为真的命题，如果在命题是对任意格都为真的命题，如果在命题P P中中把把换成换成，换成换成，换成换成，就得到另一个命题就得到另一个命题PP，把，把PP称为称为P P的的对偶命题对偶命题。则则PP对任意格也是真命题。（其中对任意格也是真命题。（其中“”是是“”的逆关系）的逆关系）若若是格，可证明是格，可证明也是一个格，也是一个格，且它们的哈斯图是上下颠倒的。且它们的哈斯图是上下颠倒的。2315156301030101562351的逆关

8、系的逆关系在在中任何两个元素的中任何两个元素的的结果值必然等于的结果值必然等于这两个元素在这两个元素在中中的结果值；的结果值；任何两个元素的任何两个元素的的结果值必然等于这两个元素在的结果值必然等于这两个元素在中中的结果值；反之亦然。的结果值；反之亦然。第11页，共28页。格的基本性质：格的基本性质：(除自反性、反对称性和传递性之外除自反性、反对称性和传递性之外)设设格，对格，对A A中的任意元素中的任意元素 a,b,ca,b,c，有：，有：(1)aab(1)aab、babbab、abaaba、abbabb(2)(2)如果如果abab且且cdcd，则，则acbdacbd，acbdacbd(3)

9、(3)若若bcbc，则，则 a a A A，有，有abacabac，abacabac （保序性）（保序性）(4)(4)交换律：交换律：ab=baab=ba、ab=baab=ba 结合律：结合律：a(bc)=(ab)ca(bc)=(ab)c、a(bc)=(ab)ca(bc)=(ab)c 幂等律：幂等律：aa=aaa=a、aa=aaa=a 吸收律：吸收律：a(ab)=aa(ab)=a、a(ab)=aa(ab)=a第12页，共28页。(5)ab (5)ab ab=a ab=a ab=b ab=b(6)(6)分配不等式：分配不等式：a(bc)(ab)(ac)a(bc)(ab)(ac)、(ab)(ac)

10、a(bc)(ab)(ac)a(bc)格的基本性质：格的基本性质：(除自反性、反对称性和传递性之外除自反性、反对称性和传递性之外)第13页，共28页。(1)aab(1)aab、babbab、abaaba、abbabb证明：证明：ab是是a和和b的的最小上界最小上界 aab、bab，由由对偶原理对偶原理，有，有aba、abb(2)(2)如果如果abab且且cdcd，则，则acbdacbd，acbdacbd证明：证明：ab，由，由(1)得得bbd，由传递性得：，由传递性得：abd cd，由，由(1)得得dbd，由传递性得：，由传递性得：cbd bd是是a和和c的一个上界，而的一个上界，而ac是是a和

11、和c的最小上界，的最小上界，acbd 同理可证：同理可证：acbd第14页，共28页。(3)(3)若若bcbc，则，则 a a A A，有，有abacabac，abacabac证明证明:bc，aa，由性质，由性质(2)得：得：abac，abac(4)(4)交换律：交换律：ab=baab=ba、ab=baab=ba 结合律：结合律：a(bc)=(ab)ca(bc)=(ab)c、a(bc)=(ab)ca(bc)=(ab)c 幂等律：幂等律：aa=aaa=a、aa=aaa=a 吸收律：吸收律：a(ab)=aa(ab)=a、a(ab)=aa(ab)=a证明：幂等律证明：幂等律 aa，a是是a的上界，而

12、的上界，而aa是是a的最小上界，的最小上界，aaa，又，又 aa a，由反对称性得：由反对称性得：aa=a 由对偶原理得，由对偶原理得，aa=a第15页，共28页。证明：吸收律证明：吸收律 a a a b a a(a b)aa，a(a b)a 又又aa(a b),a(a b)=a由对偶原理得，由对偶原理得，a(ab)=a证明：结合律证明：结合律 b(a b)c,c(a b)c bc(a b)c，又，又aa b(a b)c,a(bc)(a b)c同理可证同理可证(a b)ca(bc)，a(bc)=(ab)c由对偶原理得，由对偶原理得，a(bc)=(ab)c第16页，共28页。(5)ab (5)a

13、b ab=a ab=a ab=b ab=b证明：证明：ab ab=a ab=b ab (1)ab,aa a ab，又，又aba ab=a (2)ab=(ab)b=b (3)aab a b 第17页，共28页。引理：设引理：设是代数系统，其中是代数系统，其中,都是都是二元运算且满足二元运算且满足吸收律吸收律，则，则和和都满足都满足幂等律幂等律.证明：证明：a,b A,满足吸收律，则有满足吸收律，则有 (1)a(ab)=a,(2)a(ab)=a 由由 b 的任意性的任意性，在，在(1)式中令式中令 b=ab，代入，代入(2)得得 aa=a 同理可证：同理可证：aa=a第18页，共28页。定理定理1

14、 1：设：设是代数系统，其中是代数系统，其中,都是二元都是二元运算且满足运算且满足交换律、结合律和吸收律交换律、结合律和吸收律，则，则A A上存在上存在偏序关系偏序关系，使，使是一个格。是一个格。证明：在证明：在A上定义一个二元关系上定义一个二元关系为：为：对于对于 a,ba,b A,aA,ab b当且仅当当且仅当 ab=aab=a 首先证明首先证明是偏序关系是偏序关系 (1)a,b,c A，,满足吸收律满足吸收律,满足幂等律满足幂等律 即对即对 a A，有，有a a=a a a 自反自反 (2)若若a b且且b a，则，则ab=a且且ba=b，即有即有a=ab，b=ab，a=b，反对称反对称

15、 (3)若若a b且且bc，则，则ab=a且且bc=b，ac=(ab)c=a(bc)=ab=a ac 传递传递 是偏序关系是偏序关系第19页，共28页。其次证明其次证明A A中任意两个元素中任意两个元素a,ba,b都有最小上界和最大下界。都有最小上界和最大下界。先证先证abab是是a a和和b b的最大下界的最大下界 由由 的定义知：的定义知：(ab)a=ab，(ab)b=ab ab a,ab b，即，即ab是是a和和b的下界的下界 设设c是是a和和b的任一下界，即的任一下界，即c a，c b，于是有，于是有 ca=c，cb=c，而，而c(ab)=(ca)b=cb=c c ab，即证明了，即证

16、明了ab是是a和和b的最大下界的最大下界 再证再证ab ab 是是a a和和b b的最小上界的最小上界 a,b A，a(ab)=(aa)b=ab aab b(ab)=a(bb)=ab bab ab 是是a和和b的上界的上界 设设c是是a和和b的任一上界，即的任一上界，即ac，bc，于是有，于是有 ac=c，bc=c，而，而(ab)c=a(bc)=ac=c abc，即证明了，即证明了ab是是a和和b的最小上界的最小上界 是格是格第20页，共28页。说明：说明：该定理可以作为格的另一个定义，即该定理可以作为格的另一个定义，即设设是代数系统，其中是代数系统，其中,都是二元运算且满足交换律、都是二元运

17、算且满足交换律、结合律和吸收律，则结合律和吸收律，则是一个格。是一个格。第21页，共28页。定义：定义：A 和和A 是两个格，由它们诱导是两个格，由它们诱导的代数系统分别是的代数系统分别是A ，如果存在一个从如果存在一个从A A1 1到到A A2 2的映射的映射f f，使得对，使得对 a,ba,b A A，有有f(af(a1 1b b)=f(a)=f(a)2 2f(b)f(b)，f(af(a1 1b b)=f(a)=f(a)2 2f(b)f(b)，则称则称f f为由为由A 到到A 的一个格同态；的一个格同态；称称f(A 是是A 的格同态象；的格同态象；当当f f是双射时，称是双射时，称A 和和

18、A 是同构的是同构的。注：注：同构的两个格的哈斯图是一样的，只是各结点的标记不同而已。同构的两个格的哈斯图是一样的，只是各结点的标记不同而已。第22页，共28页。例：设例：设A A1 1=a,b,c,A=a,b,c,A2 2=P(A=P(A1 1),A),(是小于等于是小于等于)和和A(是子集关系是子集关系)都是格，如下图所示。定义都是格，如下图所示。定义 f:Af:A1 1A A2 2，f(x)=y|yf(x)=y|yx,yx,y AA，证明，证明f f是格同态。是格同态。其中其中c b a，A2=P(A1)=,a,b,c,a,b,a,c,b,c,a,b,cacb,cba,ca,b,ca,b

19、abc第23页，共28页。证明：证明：诱导的代数系统是诱导的代数系统是 诱导的代数系统是诱导的代数系统是 x1,x2 A1f(x11x2)=f(minx1,x2)=y|yminx1,x2 =y|yx1 y|yx2=f(x1)2 f(x2)f(x11x2)=f(maxx1,x2)=y|ymaxx1,x2 =y|yx1 y|yx2=f(x1)2 f(x2)存在一个从存在一个从A1到到A2的映射的映射f，使得对，使得对 x1,x2 A，有有f(x11x2)=f(x1)2f(x2)，f(x11x2)=f(x1)2f(x2)f 是是 A1 到到 A2 的格同态。的格同态。第24页，共28页。定理定理2

20、2：设：设f f是由格是由格A 到格到格A 的格同态，的格同态，则对则对 x,yx,y A A1 1，如果，如果x x 1 1 y y，必有，必有f(x)f(x)2 2 f(y)f(y)。证明：证明：x 1 y 由公式由公式(5)ab ab=a x1y=x f(x)=f(x1y)=f(x)2f(y)f(x)2 f(y)注：注：该定理说明该定理说明 格同态格同态保序保序，但反之不一定成立，即，但反之不一定成立，即保序不一定能推出格同态。保序不一定能推出格同态。第25页，共28页。例：例：S S1212=1,2,3,4,6,12=1,2,3,4,6,12，S,D和和S)都是格都是格3126412

21、3211264定义定义双射双射函数函数f:S12S12，f(x)=x，a,b S12，若，若 a/b，则有，则有 a(小于等于小于等于)b，即，即 f(a)(小于等于小于等于)f(b)到到是保序的。是保序的。但但 213=1,f(213)=f(1)=1 而而 f(2)2 f(3)=223=2 f(213)f(2)2f(3)f 不是格同态（即保序不一定能推出格同态）不是格同态（即保序不一定能推出格同态）格同态格同态保序保序，但反之不一定成立，即，但反之不一定成立，即保序不一定能推出格同态。保序不一定能推出格同态。第26页，共28页。定理定理3 3：设：设f f是由格是由格A 到格到格A 的格同构

22、，的格同构，当且仅当对当且仅当对 a,ba,b A A1 1，有有aa1 1b b f(a)f(a)2 2f(b)f(b)。证明：证明：(1)设设f是是到到的格同构的格同构 由定理由定理2，a,b A1，有，有 a 1 b f(a)2 f(b)反之，若反之，若f(a)2 f(b)，则，则f(a)2 f(b)=f(a)，于是有于是有 f(a 1 b)=f(a)，由于，由于 f 是双射是双射 a1 b=a，a 1 b a 1 b f(a)2 f(b)。第27页，共28页。证明：证明：(2)设设 a,b A1，有，有 a 1 b f(a)2 f(b)a 1 b 1 a，a 1 b 1 b，由已知有，由已知有f(a 1 b)2 f(a)，f(a 1 b)2 f(b)f(a 1 b)2 f(a)2 f(b)设设f(a)2 f(b)=f(d)，则，则f(d)2 f(a),f(d)2 f(b)，由已知得，由已知得:d 1 a，d 1 b，于是，于是d 1 a 1 b，由已知得，由已知得:f(d)2 f(a 1b)f(a)2 f(b)2 f(a 1 b)f(a 1 b)=f(a)2 f(b)类似可证明类似可证明 f(a 1 b)=f(a)2 f(b)f是是到到的格同态的格同态由于由于 f 是双射是双射 f是是到到的格同构的格同构第28页，共28页。