第十章格与布尔代数 ·10.1格的定义与性质 ·1.定义 与群，环，域，不同，格与布尔代数的基集都是一 偏序 格是具有两个二元运算的代数系统， 是 一个 特殊的偏序集，布尔代数是一个特殊的格。 定义10.1：设<S,≤>是偏序集，若x,y∈S,{x,y} 都有上下确界，则称<S,≤>为格(Lattice) >()偏序集的任一子集并非都有上下确界， >(2)偏序集的某一子集的上下确界若存在，则唯一， 格的定义桶定了上下确東的存在性， >(3){x,y}的上确界记为xVy,下确界记为x∧y 173
1/73 第十章 格与布尔代数 • 10.1 格的定义与性质 • 1.定义 与群，环，域，不同，格与布尔代数的基集都是一 个偏序集，格是具有两个二元运算的代数系统， 是一个特殊的偏序集，布尔代数是一个特殊的格。 • 定义10.1：设<S, ≤>是偏序集，若 都有上下确界，则称<S, ≤>为格(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：设<L,≤>是格，则运算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：设<L, ≤>是格，则运算∨, ∧满足交 换律，结合律，幂等律，吸收律，即 * f * f * f 若：a,bL,ab a，则a,bL,ab 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,个，来像群，环，域，一样定义 格，即用<L,V,个>来定义格，可以证明这是 可行的。 定理10.2：设<S,*,0>是具有二个二元运算的代 数系统，且*，。运算满足交换律，结合律，吸收 律，则可以适当定义$中的偏序≤，使得<S,≤>构 成一个格，且a,b∈S,有aAb=a*b,avb=aob 4/73
4/73 10.1 格的定义与性质 ➢由定理10.1知，格的两个运算满足交换律，结合 律，幂等律，因此可以考虑用带有这4条性质的2 个二元运算∨, ∧，来像群，环，域，一样定义 格，即用<L, ∨, ∧ >来定义格，可以证明这是 可行的。 • 定理10.2：设<S,*,ο>是具有二个二元运算的代 数系统，且*,ο运算满足交换律，结合律，吸收 律，则可以适当定义S中的偏序≤，使得<S,≤>构 成一个格， 且a,bS，有ab = ab,ab = ab
10.1格的定义与性质 证：(1)先证：*，0满足幂等律（吸收律三幂等律） VaeS,由吸收律得：a*a=a*(ao(a*a)=a,同理aoa=a (2)定义S上的二元关系R,Va,b∈S,有<a,b>∈R台aob=b 台a≤b则，R为偏序关系，.a,b,c∈S,有， 自反性：aoa=a→<a,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) ( )