东南大学：《离散数学》课程教学资源（PPT课件讲稿）第十一章 格与布尔代数

第十一章:格与布尔代数 豪 第一节:格的定义与性质 数 第二节:分配格、有补格与布尔代

1 第十一章: 格与布尔代数 第一节：格的定义与性质 第二节：分配格、有补格与布尔代 数

9第十一章:格与布尔代数 豪 第一节:格的定义与性质 2

2 第十一章: 格与布尔代数 第一节：格的定义与性质

引言 豪 口格和布尔代数都是抽象的代数系统,与前面不 同的是在于格和布尔代数中次序关系具有重要 的意义 口格首先在偏序集合的基础上进行讨论,然后将 讨论代数系统格,对代数系统的格施加某些限 制可得到布尔代数。布尔代数是一种特殊的代 数系统,而且是一种特殊的格 口格也是一类非常重要的代数结构

3 引言 ❑格和布尔代数都是抽象的代数系统，与前面不 同的是在于格和布尔代数中次序关系具有重要 的意义 ❑格首先在偏序集合的基础上进行讨论，然后将 讨论代数系统格，对代数系统的格施加某些限 制可得到布尔代数。布尔代数是一种特殊的代 数系统，而且是一种特殊的格 ❑格也是一类非常重要的代数结构

11.1格的定义与性质 豪 口格:偏序集合,满足 令每一对元素abeL都拥有一个最小上界和最 大下界 符号 ◆最大下界:∧ ◇最小上界:V

4 11.1 格的定义与性质 ❑格：偏序集合，满足 ❖每一对元素a,bL都拥有一个最小上界和最 大下界 ❑符号： ❖最大下界：∧ ❖最小上界：∨

11.1格的定义与性质 豪 (b) 5

5 (a) (b) (c) (d) 11.1 格的定义与性质

11.1格的定义与性质 豪 (f) g a b 6

6 (f) (g) a b (h) a b c d (i) 11.1 格的定义与性质

11.1格的定义与性质 豪 例设S是一集合PS)是S的幂集则<PS),≌是一个 偏序集ⅤAB∈P(S)易证明, A∧B=AnB∈P(S),AVB=A∪B∈P(S) ∴<P(S)≌是一个格。 la, by a, b,c (a, b]. 向c{b, {a}b} [b] S=a] s=a, b] S=a, b, c) 7

7 例:设S是一集合,P(S)是S的幂集,则是一个 偏序集,A,B∈P(S),易证明, A∧B=A∩B∈P(S), A∨B=A∪B∈P(S) ∴是一个格。 {a}  S={a}  {a,b} {a} {b} S={a,b} {a,b,c } { b,c} {c}  {a} {a,b} {b} {a,c} S={a,b,c} 11.1 格的定义与性质

11.1格的定义与性质 豪 例:I是正整数集合,D是整除关系, 是偏序集,va,b∈I, a∧b=最大公约数,ab=最小公倍数 证明:若c是{a,b}的下界,则ca,c≤b,即c 能整除a,能整除b,所以c是a,b的公约数。 若c是{a,b}的最大下界,则c是a,b的最大公 约数。反之,同样可证。 因此,是格,因为a,b∈I都有最大 公约数和最小公倍数。 8

8 例：I+是正整数集合，D是整除关系， 是偏序集，a，b∈I+， a∧b=最大公约数，a∨b=最小公倍数 证明：若c是{a，b}的下界，则c≤a，c≤b，即c 能整除a，能整除b，所以c是a，b的公约数。 若c是{a，b}的最大下界，则c是a，b的最大公 约数。反之，同样可证。 因此，是格，因为a，b∈I+都有最大 公约数和最小公倍数。 11.1 格的定义与性质

11.1格的定义与性质 豪 所形成的表达式称为的对偶式记 口对偶式:格中元素用运算符∧,连接起来的的 个表达式f,如将f中的^换成v,将换成A 口对偶命题:两个表达式9用关系符≤≥连接成为 命题:将表达式千q用fq代替,≤与≥互换,形 成的命题称为原命题的对偶命题 口例:f=(avb)∧c<C, f=(ab)vc≥c

9 ❑对偶式：格中元素用运算符∧,∨连接起来的的一 个表达式f ，如将f中的∧换成∨ ，将∨换成∧ ， 所形成的表达式称为f的对偶式记作f * ❑对偶命题：两个表达式f,g用关系符≤,≥连接成为 命题，将表达式f,g用f * ,g*代替，≤与≥互换，形 成的命题称为原命题的对偶命题 ❑例：f=(a∨b)∧c≼c， f *=(a∧b)∨c≽c 11.1 格的定义与性质

11.1格的定义与性质 豪 对偶原聖设f是含有格中元素以及符号=,≤,≥ ,V,∧等的命题。若对一切格为真,则f的对 偶命题f也对一切格为真 口例:如果对一切格L,Vab∈Layb)∧c≤C 则f=a入b)c≥C 10

10 设f是含有格中元素以及符号＝，≼，≽ ，∨，∧等的命题。若f对一切格为真，则f的对 偶命题f *也对一切格为真 ❑例：如果对一切格L，a,b L,(a∨b)∧c≼c 则f *=(a∧b)∨c≽c 11.1 格的定义与性质