第十一章： 格与布尔代数.pptx

第十一章:格与布尔代数;第十一章:格与布尔代数;引言;11.1格的定义与性质;;;例:设S是一集合,P(S)是S的幂集,则P(S),?是一个偏序集,?A,B∈P(S),易证明,

A∧B=A∩B∈P(S),A∨B=A∪B∈P(S)

∴P(S),?是一个格。;例：I+是正整数集合，D是整除关系，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的最大公约数。反之，同样可证。

因此，I+，D是格，因为?a，b∈I+都有最大公约数和最小公倍数。;对偶式：格中元素用运算符∧,∨连接起来的的一个表达式f，如将f中的∧换成∨，将∨换成∧，所形成的表达式称为f的对偶式记作f*

对偶命题：两个表达式f,g用关系符≤,≥连接成为命题，将表达式f,g用f*,g*代替，≤与≥互换，形成的命题称为原命题的对偶命题

例：f=(a∨b)∧c?c，

f*=(a∧b)∨c?c

;设f是含有格中元素以及符号＝，?，?，∨，∧等的命题。若f对一切格为真，则f的对偶命题f*也对一切格为真

例：如果对一切格L，?a,b?L,(a∨b)∧c?c

则f*=(a∧b)∨c?c

;定理：设L,?是一格，则对于所有的a,b∈L

a?b?a∧b=a?a∨b=b

定理：设L,?是一格，则对于所有的a,b，c,d∈L

a?b且d?c?(a∨d)?(b∨c)

a?b且d?c?(a∧d)?(b∧c);定理：设L,≤是一格，则对于所有的a,b,c∈L有：

（1）交换律：a∨b=b∨a，a∧b=b∧a

（2）结合律：(a∨b)∨c=a∨(b∨c)

(a∧b)∧c=a∧(b∧c)

（3）幂等律：a∨a=a，a∧a=a

（4）吸收律：a∨(a∧b)=a，a∧(a∨b)=a;证明结合律：(a∨b)∨c=a∨(b∨c)

(a∨b)∨c?a∨b?a

(a∨b)∨c?a∨b?b

(a∨b)∨c?c∴(a∨b)∨c?b∨c

∴(a∨b)∨c?a∨(b∨c)

同理a∨(b∨c)?(a∨b)∨c

因为≥的反对称性，(a∨b)∨c=a∨(b∨c);从现在开始讨论代数系统的格，把格看成是一个特

殊类型的代数系统。

格的另一种定义：设L,*,?是一个代数系统，L是一非空集合，*和?是L上的二个二元运算。若*和?满足交换???，结合律，幂等律，吸收律，则称此代数系统为格

;设L,*,?是一个代数系统格，则在L中一定存在一个偏序关系?，并在?的作用下，对任一a,b∈L，

a?b=a∨b，a*b=a∧b

由上述定理可得以下结论：

（1）在L,*,?的代数系统格中，可以定义一个L上的偏序关系?，即

a?b?a*b=a?a?b=b

（2）在格L,?中，可以定义二个运算*和?，有

a?b=a∨b，a*b=a∧b;设L,*,?是一个代数系统格，则在L中一定存在一个偏序关系?，并在?的作用下，对任一a,b∈L，

a?b=a∨b，a*b=a∧b

证明：定义二元关系?：?a，b?L

a?b?a?b＝b

需要证明?是L上的偏序,且L,?为格;证明?是L上的偏序（a?b?a?b＝b）

自反性：根据幂等律，?a?L，a?a＝a，

故a?a

反对称性：?a，b?L

a?b且b?a?a?b＝b且b?a＝a

?a＝b?a＝a?b＝b(?适合交换律）

传递性：?a，b，c?L

a?b且b?c?a?b＝b且b?c＝c

?a?c＝a?(b?c)?a?c＝(a?b)?c

?a?c＝b?c=c?a?c;证明L,?为格（a?b?a?b＝b）

最小上界存在性：?a，b?L

a?（a?b)＝(a?a)?b＝a?b

b?（a?b)＝a?(b?b)＝a?b

?a?a?b且b?a?b，故a?