北京大学：《离散数学》离散数学之二《代数结构与组合数学》第19章 格与布尔代数（1/2）

第十九章格与布尔代数 191格的定义与性质 192子格、格同态与格的直积 193特殊的格 194布尔代数

1 第十九章 格与布尔代数 „ 19.1 格的定义与性质 „ 19.2 子格、格同态与格的直积 „ 19.3 特殊的格 „ 19.4 布尔代数

19.1格的定义和性质 格的定义 格的基本性质 对偶原理 格中的基本等式与不等式 格中的基本等价条件 格中的算律 ■格的代数定义 格中的不等式

2 „ 格的定义 „ 格的基本性质 „ 对偶原理 „ 格中的基本等式与不等式 „ 格中的基本等价条件 „ 格中的算律 „ 格的代数定义 „ 格中的不等式 19.1 格的定义和性质

格的定义 格的偏序集定义: ,S的任何二元子集都有最大下界、最小上界. 求最大下界、最小上界构成格中的运算∧八 格与导出的代数系统的对应关系 格的实例: n的正因子格Sn 幂集格P(B) 子群格L(G)

3 格的偏序集定义： , S 的任何二元子集都有最大下界、最小上界. 求最大下界、最小上界构成格中的运算∧,∨ 格与导出的代数系统的对应关系 格的实例： n 的正因子格 Sn 幂集格 P(B) 子群格 L(G) 格的定义

格的实例 例1设n是正整数,S是n的正因子的集合.D为整除关 系,则偏序集和 30 8421 (S3D) (S6,D)

4 格的实例 例1 设n是正整数，Sn是n的正因子的集合. D为整除关 系，则偏序集构成格. ∀x,y∈Sn，x∨y 是 lcm(x,y)，即 x 与 y 的最小公倍数. x∧y 是 gcd(x,y)，即 x 与 y 的最大公约数. 下图给出了格，和

格的实例(续) 例2判断下列偏序集是否构成格,并说明理由. (1),其中Z是整数集,≤为小于或等于关系. (2)偏序集的哈斯图分别在下图给出 q u b t (1)是格. (2)都不是格

5 例2 判断下列偏序集是否构成格，并说明理由. (1) ，其中Z是整数集，≤为小于或等于关系. (2) 偏序集的哈斯图分别在下图给出. 格的实例（续） (1) 是格. (2) 都不是格

格的性质—一对偶原理 对偶命题:设P是由格中元素,,等表示的命题, 若将P中的≤,>,八,V分别替换成≥≤,得到的命题称为 P的对偶命题,记作P 实例: P:a∧b=b∧a P: avb=bva 性质:(D)=P 对偶原理:如果P对于一切格为真,则P也对一切格为真

6 对偶命题：设 P 是由格中元素,≼,≽,=,∧,∨等表示的命题， 若将 P 中的≼,≽,∧,∨分别替换成≽≼,∨,∧得到的命题称为 P 的对偶命题，记作 P*. 实例： P: a ∧ b = b ∧ a P*：a ∨ b = b ∨ a 性质：(p*)*= P 对偶原理：如果 P 对于一切格为真，则 P*也对一切格为真. 格的性质——对偶原理

格的性质(续) 格中的基本不等式和等式 a ab,a>C→a>bvc n<bb<a→a=b

7 格的性质（续） 格中的基本不等式和等式 a ≼ a a ≼ b, b ≼ c ⇒ a ≼ c a ∧ b ≼ a, a ∧ b ≼ b a ≼ a ∨b, b ≼ a ∨ b a ≼ b, a ≼ c ⇒ a ≼ b ∧ c a ≽ b, a ≽ c ⇒ a ≽ b ∨ c a ≼ b, b ≼ a ⇒ a = b

格的性质(续) 格中的基本等价条件 a<b分ab=a冷b=b 证:①→② n≤a,a≤b→a<Ab →∧b=a a∧b<a ②→③ barb l=入b<b,6<b→mMWb=b ③→① aavb= b

8 格的性质（续） a ≼ b ⇔ a ∧ b = a ⇔ a ∨ b = b ①② ③ 格中的基本等价条件 证： ② ⇒ ③ b ≼ a ∨ b ③ ⇒ ① a ≼ a ∨ b = b a ∧ b ≼ a ⇒ a ∧ b = a a = a ∧ b ≼ b, b ≼ b ⇒ a ∨ b ≼ b ⇒ a ∨ b = b ① ⇒ ② a ≼ a, a ≼ b ⇒ a ≼ a ∧ b

格的性质(续) 格中交换律、结合律、幂等律、吸收律 证(1)a∧b是{anb}的下界, b∧是{b,a}的下界, {a,b}={b,a}→Ab=b∧ (2)(ab)Acanka (anb)Canbo b)∧ca∧b∧C (anb)Acc (入bcb入c 同理,a^(b入C)<(aAb)/c 所以,aA(bC)=(aAb)c

9 格的性质（续） 证 (1) a ∧ b 是{ a , b }的下界， b ∧ a 是{ b , a }的下界 , { a , b }={ b , a } ⇒ a ∧ b = b ∧ a 格中交换律、结合律、幂等律、吸收律 (2) ( a ∧ b ) ∧ c ≼ a ∧ b ≼ a ( a ∧ b ) ∧ c ≼ a ∧ b ≼ b ( a ∧ b ) ∧ c ≼ c 同理， a ∧ ( b ∧ c) ≼ ( a ∧ b ) ∧ c ( a ∧ b ) ∧ c ≼ b ∧ c 所以， a ∧ ( b ∧ c) = ( a ∧ b ) ∧ c ( a ∧ b ) ∧ c ≼ a ∧ ( b ∧ c )

格的代数定义 引理是具有两个二元运算的代数系统 如果六。运算满足交换、结合、吸收律, 则(1)+满足幂等律 (2)a*b=a分ab=b 证() aa=a aola a=a 同理,aoa=a (2)“∈”a*b=a(ob) “→”aob=(*b)b=b

10 引理 是具有两个二元运算的代数系统. 如果*,◦运算满足交换、结合、吸收律， 则 (1) *,◦满足幂等律 (2) a*b = a ⇔ a◦b = b 证 (1) a*a = a*(a◦(a*a)) = a 同理，a◦a = a (2) “⇐” a*b = a*(a◦b) = a “⇒” a◦b = (a*b)◦b = b 格的代数定义