中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第三部分 代数结构 第十章 格与布尔代数

第十章格与布尔代数 ·10.1格的定义与性质 ·1.定义 与群，环，域，不同，格与布尔代数的基集都是一 偏序 格是具有两个二元运算的代数系统， 是 一个 特殊的偏序集，布尔代数是一个特殊的格。 定义10.1：设是偏序集，若x,y∈S,{x,y} 都有上下确界，则称为格(Lattice) >()偏序集的任一子集并非都有上下确界， >(2)偏序集的某一子集的上下确界若存在，则唯一， 格的定义桶定了上下确東的存在性， >(3){x,y}的上确界记为xVy,下确界记为x∧y 173

1/73 第十章 格与布尔代数 • 10.1 格的定义与性质 • 1.定义 与群，环，域，不同，格与布尔代数的基集都是一 个偏序集，格是具有两个二元运算的代数系统， 是一个特殊的偏序集，布尔代数是一个特殊的格。 • 定义10.1：设是偏序集，若 都有上下确界，则称为格(Lattice) ➢(1)偏序集的任一子集并非都有上下确界， ➢(2)偏序集的某一子集的上下确界若存在，则唯一， 格的定义确定了上下确界的存在性， ➢(3){x, y}的上确界记为x∨y，下确界记为x∧y x, y S,{x, y}

10.1格的定义与性质 定义10.2：设f是含有格中元素及符号=，≤，≥ V,∧的命题，令是将f中≤，≥，V,∧分别 替换为≥，≤，∧，V所得到的命题，则称是f 的对偶命题或称对偶式。 格的对偶原理：若对一切格为真，则∫°也对一切 格为真。 例：若：Va,b∈L,a∧b≤a,则Va,b∈L,avb≥a成立。 定理10.1：设是格，则运算V,∧满足交 换律，结合律，幂等律，吸收律，即Va,b,c∈L 1):aVb=bva,aAb=b∧a (2):(avb)vc=av(bvc),(anb)nc=an(bnc); 3):aVa=a,a∧a=a, (4):av(a∧b)=a,a∧(avb)=a. 2/73

2/73 10.1 格的定义与性质 •定义10.2：设f是含有格中元素及符号=, ≤,≥, ∨, ∧的命题，令 是将f中≤,≥, ∨, ∧分别 替换为≥, ≤,∧,∨所得到的命题，则称 是f 的对偶命题或称对偶式。 格的对偶原理：若f对一切格为真，则 也对一切 格为真。 例： • 定理10.1：设是格，则运算∨, ∧满足交 换律，结合律，幂等律，吸收律，即 * f * f * f 若：a,bL,ab  a，则a,bL,ab  a成立。 a,b,c L (4): ( ) , ( ) . (3): , ; (2):( ) ( ), ( ) ( ); (1): , ; a a b a a a b a a a a a a a a b c a b c a b c a b c a b b a a b b a   =   =  =  =   =     =    =   = 

10.1格的定义与性质 证：1)由定义知，成立： (2).由上确界定义，(avb)Vc≥avb≥b,(avb)vc≥c→ (aVb)vc≥bVc,又(avb)vc≥avb≥a, ∴.(avb)Vc≥av(bvc)同理：(avb)vc≤av(bVc) ∴.(avb)vc=av(bvc) 由偏序关系的对偶性知：(aAb)∧c=a∧(bAc) (3)由自反性，a≤a,则a是a的一个上界，而ava是a与a的一个 最小上界∴.ava≤a,而a≤ava∴.由反对称性：a=ava, 由对偶原理：a=a∧a (4).av(aAb)≥a,又a≤a,aAb≤a∴a是a与aAb的上界，而av(a∧b) 是a与aAb的最小上界，∴.av(aAb)≤a,由反对称性：av(aAb)=a 由对偶原理，得：a∧(avb)=a 3/73

3/73 10.1 格的定义与性质 a a b a a a b a a b a a a b a a a b a a a a b a a a a b a a b a a a a a a a a a a a a a a a a a a a a a b c a b c a b c a b c a b c a b c a b c a b c a b c b c a b c a b a a b c a b b a b c c   =        =           =        =      =      =                                ( ) ( ) ( ) (4). ( ) , ( ) (3). ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) , (2). ( ) ( ) (1). 由对偶原理，得： 是 与 的最小上界， ，由反对称性： ，又 是 与 的上界，而 由对偶原理： 最小上界 ，而 由反对称性： ， 由自反性， ，则 是 的一个上界，而 是 与 的一个 由偏序关系的对偶性知： 同理： ，又 由上确界定义， ， 证： 由定义知，成立；

10.1格的定义与性质 >由定理10.1知，格的两个运算满足交换律，结合 律，幂等律，因此可以考虑用带有这4条性质的2 个二元运算V,个，来像群，环，域，一样定义 格，即用来定义格，可以证明这是 可行的。 定理10.2：设是具有二个二元运算的代 数系统，且*，。运算满足交换律，结合律，吸收 律，则可以适当定义$中的偏序≤，使得构 成一个格，且a,b∈S,有aAb=a*b,avb=aob 4/73

4/73 10.1 格的定义与性质 ➢由定理10.1知，格的两个运算满足交换律，结合 律，幂等律，因此可以考虑用带有这4条性质的2 个二元运算∨, ∧，来像群，环，域，一样定义 格，即用来定义格，可以证明这是 可行的。 • 定理10.2：设是具有二个二元运算的代 数系统，且*,ο运算满足交换律，结合律，吸收 律，则可以适当定义S中的偏序≤，使得构 成一个格， 且a,bS，有ab = ab,ab = ab

10.1格的定义与性质 证：(1)先证：*，0满足幂等律（吸收律三幂等律） VaeS,由吸收律得：a*a=a*(ao(a*a)=a,同理aoa=a (2)定义S上的二元关系R,Va,b∈S,有∈R台aob=b 台a≤b则，R为偏序关系，.a,b,c∈S,有， 自反性：aoa=a→∈R aRb台aob=b 反对称： bRaboa-a →a=b 传递性： aoc-ao(hoe)(ash)ccboc- →aRc 记R为≤ 5/73

5/73 10.1 格的定义与性质    = = = =     =  =  =     =  = =            =    =   = =   记 为 传递性： 反对称： 自反性： 则， 为偏序关系， ，有， 定义 上的二元关系 ， ，有 ，由吸收律得： ，同理 证： 先证： ，满足幂等律 吸收律 幂等律 R aRc a c a b c a b c b c c bRc b c c aRb a b b a b bRa b a a aRb a b b a a a a a R a b R a b c S S R a b S a b R a b b a S a a a a a a a a a a                 ( ) ( ) , , , (2) , , ( ( )) (1) ( )

10.1格的定义与性质 (3)构成格： ta,b∈S, tofgob)-(aoaob-aob,bolaob)-ao(bob)-aob ∴.a≤aob,b≤aob,即aob是a,b的上界； 设c为{a,b的上界，则a≤c→aoc=c,b≤c→boc=c ∴.(aob)oc-ao(boc)=aoc=c∴.aob是{a,b的最小上界，即avb=aob aob=b→a*b=a*(aob)=a a*b=a→lab=(a*b)b=b→ab=6⊙a≤6台a*b=a (a*b)*a=(a*a)*b=a*b→a*b≤a (a*b)*b=a*(b*b)=a*b→a*b≤b ∴.a*b是a,b的下界； 设c为{a,b}的下界，则c*a=c,c*b=c ∴c*(a*b)=(c*a)*b=c*b=c∴c≤a*b,即a*b是{a,b的最大下界， 即ab=a*b 6/73

6/73 10.1 格的定义与性质 a b a b c a b c a b c b c c a b a b a b c a b c a c c b c a b a b a b b a b b a b a b b a b a a a b a b a b a a b b a b a b a a b a a b a b b b a b b a b a a b a a b c a b c a c c a b a b a b a b c a b a c a c c b c b c c a a b b a b a b a b a b S a a b a a b a b b a b a b b a b S  =     =   =  =      =  =     =   =       =   =      =     =     =  =  = =   =  =  = = =   =   =   =      = = = =    即 ，即 是 的最大下界， 设 为 的下界，则 ， 是 的下界； 是 的最小上界，即 设 为 的上界，则 ， ， ，即 是 的上界； ，有： ， 构成格： ( ) ( ) { , } { , } , , ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) { , } { , } , , ( ) ( ) ( ) ( ) (3) ,                           

10.1格的定义与性质 由定理10.1,10.2可知： 是格 诱导出 →代数系统∧，V满足交换，结合， 吸收（幂等）律 代数系统,*,满足交换，结合，吸收（幂等）律 诱导出 入 成一个格，且a∧b=a*b,aVb=aob 令：y={kL,>是格}，B={KL,*,o>是代数系统，*与。 是二元运算，且满足交换律，结合律，吸收（幂等）律} 定义映射fy→B,对廿∈yf()=,其中 是诱导出的代数系统， 定义映射g:B→y对H∈B,g()=，其中 是诱导出的格， 则有：∫og=1,g°∫=IB 773

7/73 10.1 格的定义与性质 由定理10.1,10.2可知： S a b a b a b a b S L L        =   =     ⎯⎯⎯→    ⎯⎯⎯→       成一个格，且 ， 代数系统 满足交换，结合，吸收 幂等 律 吸收 幂等 律 是格 代数系统 ， 满足交换，结合， 诱导出 诱导出 , , , , , ( ) ( ) , , ,           f g I g f I L g L g L L L L f L f L L L L L L L = =    →        =      →      =      =    =                 则有： ， 是 诱导出的格， 定义映射 ： ，对 ， ，其中 是 诱导出的代数系统， 定义映射 ： ，对 ， ，其中 是二元运算，且满足交换律，结合律，吸收 幂等 律 令： 是格 ， 是代数系统，与 , , , , ( , , ) , , , , ( , ) , , , , ( ) } { , | , } { , , | ,

10.1格的定义与性质 因此，根据定理10.1,10.2，可以用代数系统的方 式来定义格。 定义10.3：设是代数系统，*，0是二元 运算且满足交换律，结合律，吸收律（幂等律）， 则构成一个格。 •2.性质 ·定理10.3：设是格，则Va,b∈L,有 1)a≤aVb,b≤aVb,aAb≤a,aAb≤b; (2)a≤b,c≤d→aVc≤bvd,aAc≤bAd; (3)a≤b→aVc≤bVc,a∧c≤b∧c; (4)a≤b台aAb=a台avb=b;(5)av(b∧c)≤(avb)∧(avc): (6)a≤c台aV(b∧c)≤(aVb)Λc. 8/73

8/73 10.1 格的定义与性质 因此，根据定理10.1，10.2，可以用代数系统的方 式来定义格。 •定义10.3：设是代数系统， *,ο是二元 运算且满足交换律，结合律，吸收律(幂等律)， 则构成一个格。 • 2.性质 •定理10.3：设是格，则 a,b L ，有 (6) ( ) ( ) . (4) (5) ( ) ( ) ( ) (3) (2) (1) a c a b c a b c a b a b a a b b a b c a b a c a b a c b c a c b c a b c d a c b d a c b d a a b b a b a b a a b b           =   =                                ； ； ， ； ， ， ； ， ， ， ；

10.1格的定义与性质 证：(1)直接由定义； (2)a≤b,dm由)知：b≤bVd,d≤bVd,由≤的传递性，得 a≤bvd,c≤bvd,∴.bvd是a与c的一个上界，而avc是a,c的 最小上界，.avc≤bvd,同理aAc≤bAd; (3)a≤b,c≤c,由(2)得：aVc≤bVc,a∧c≤bAc; (4)(→)：q≤b,而a≤a,由(2)得：aAa=a≤a∧b, 同时由(1)4Ab≤a∴.a=aAb (=):a=aAb,则avb=(aAb)vb=b,而a≤aVb=b;即a≤b 另一方面，a=aAb→avb=b,即avb=b 且b=avb,得：aAb=aA(avb)=a ∴.a≤b台a∧b=a台avb=b; 9/73

9/73 10.1 格的定义与性质 ； 且 ，得： 另一方面， ，即 ： ，则 ，而 ，即 同时由 ： ，而 ，由 得： ， ， ，由 得： ， ； 最小上界， ，同理 ； ， ， 是 与 的一个上界，而 是 的 ， ，由 知： ， ，由 的传递性，得 证： 直接由定义； a b a b a a b b b a b a b a a b a a a b a b b a b b a a b a b a b b b a a b b a b a b a a a b a b a a a a a a b a b c c a c b c a c b c a c b d a c b d a b d c b d b d a c a c a c a b c d b b d d b d     =   = =   =   = =    =  =  =   =   =   =     =      =                                ( ) ( ) ( ) (1) (4)( ) (2) (3) (2) , (2) (1) (1)

10.1格的定义与性质 (5)a≤a,bAc≤b由(2)得：av(bAc)≤avb, a≤a,b∧c≤c由(2)得：aV(b∧c)≤aVc, ∴.av(b∧c)=(av(b∧c)∧(av(bAc)≤(avb)A(aVc): (6(=):aV(bAc)≤(aVb)Ac,而a≤av(bAc),(avb)Ac≤c .由传递性：a≤c (→)：a≤c,则avc=c,代入(5)得： aV(b∧c)≤(avb)∧(aVc)=(aVb)∧c. 10/73

10/73 10.1 格的定义与性质 ( ) ( ) ( ) ( ) . ( ) (5) (6)( ) ( ) ( ) ( ) ( ) ( ) ( ( )) ( ( )) ( ) ( ) (2) ( ) (5) (2) ( ) a b c a b a c a b c a c a c c a c a b c a b c a a b c a b c c a b c a b c a b c a b a c a a b c c a b c a c a a b c b a b c a b       =      =                  =                        ： ，则 ，代入 得： 由传递性： ： ，而 ， ； ， 由 得： ， ， 由 得：