第八章 格与布尔代数 8.1 引 言集合代数：（(S)，） 对A,B,C(S)，运算，满足： v等幂律 AA = A， AA = A，v交换律 AB = BA， AB = BA，v结合律 A（BC） = （AB）C， A（BC） = （AB）C，v分配律 A（BC） =（AB）（AC）， A（BC）=（AB）（AC），v吸收律 A（AB）=A， A（AB）=A， 若引进余集的概念，有De Morgan定律:命题代数（S，）对A,B,CS，运算，满足： v等幂律 AA = A， AA = A， ，v交换律 AB = BA，AB = BA v结合律 A（BC）=（AB）C，A（BC） = （AB）C v分配律 A(BC)=(AB)(AC)，A（BC） = （AB） （AC） v吸收律 A(AB)=A，A（AB）=A， 若引进否定的概念，有De Morgan定律:(AB )= AB, (AB )= AB, 8.2 格 的 定 义 半序格定义A 给出一个部分序集（L，）, 如果对于任意a，bL，L的子集a，b 在L中都有一个最大下界(记为infa，b) 和一个最小上界（记为supa，b），则 称（L，）为一个格。 半序格的例例. S是任意一个集合，(S)是S的幂集合，则，部分序集(S)，)是一个格。 因为对A,B(S)， supA,B=AB(S),infA,B=AB(S) 例.设I+是所有正整数集合，D是I+中的“整除关系 ”，对任意a，bI+，aDb当且仅当a整除b，于 是，（I+，D）是一个格。 supa，b=a，b的最小公倍I+， infa,b= a，b的最高公因I+ 。 半序格的例 例. 设n是一个正整数，Sn是n的所有正因数的集 合，于是，（Sn，D）是格。因为 supa，b=a，b的最小公倍 Sn， infa,b= a，b的最高公因 Sn。 例. 设S是所有的命题集合，定义“ ” 如下：A B 当且仅当 B蕴涵A。 则（S， ）是一个格。因为supA，B=ABS， infA，B=ABS。 半序子格定义A 设（L，）是格，S L， 如果（S，）是格， 则称（S，）是格（L，）的子格。例.（S6，D）是（S24，D）的子格。 代数格代数格定义B 设L是一个集合，是L上两个 二元代数运算，如果这两种运算对于L中元 素满足：（1）交换律：ab=ba，ab=ba。（2）结合律：a（bc）=（ab）c，a（bc）=（ab）c。（3）吸收律：a（ab）=a，a （ab）=a。 则称此代数系统（L，）为一个格。 note: 定义B中由， 满足吸收律可推出它们 一定满足等幂律。 证明：任取L中元素a，由，满足吸收律知， a（aa）=a， a （aa）=a。故 aa=a（a（aa）， aa=a（a（a a）。又由，满足吸收律知，上面两式的等式右 端都等于a。因此， aa = a， a a = a。 即， 定义B中的， 运算亦满足等幂律。 代数格的例 例. 设S是一个集合,(S)是S的幂集合，于是， (S),)是一个代数格。而(S)，)是半序 格。易见对A,B(S)， A B AB = A AB = B。 例. 设I+是所有正整数集合,两个正整数的最高公 因,最小公倍是I+上两个代数运算，于是,(I+, ,)是一个代数格。而（I+,D）是半序格,D是 整除关系。易见，对任意a，bI+, a D b ab = a ab = b。例. 设n是一个正整数,Sn是n的所有正因数的 集合,两个正整数的最高公因,最小公倍可 是Sn上两个代数运算,于是,(Sn,)是一个 代数格。 代数格与半序格的等价性定理8.2.1 定义A所定义的格和定义B所定义的 格是等价的，亦即，一个半序格必是一个代数 格；反之亦然。 证明：i）若(L,)是一个半序格,则对a,bL， 记 infa，b为ab； supa，b为ab。由于对任意a，b，其infa，b，supa，b是 唯一的，所以，如上定义的，是集合L上 的两种二元代数运算。不难证明,对于,满足交换律,结合律,吸收律。 则根据定义B,(L,)是一个代数格。 我们只证明吸收律：a（ab）=a为例，其它算律的证明留给读者。因为a(ab)是a与(ab)的最大下界，所以 a(ab)a另一方面，由于aa，aab，所以，a是a与ab的下界，故aa(ab)所以，a=a(ab)。证明证明ii）若代数系统（L，）是一个代数格，在 集合L上定义一个关系如下： 对任意a，bL， ab ab=a 往证：是一个半序关系。v反身性:因为aa=a(a(aa)= a,所以aa。v反对称性:若有ab,ba,则应有ab=a，ba=b ，而ab = ba，所以a=b。v传递性:若ab，bc，则有ab=a，bc=b，故 ac=(ab)c=a(bc)=ab=a,亦即, ac。证明证明往证：ab = a a b = b。 若ab = a，则ab = （ab） b = b。 若ab = b，则ab=a（ab）=a。 往证: 对任意a,bL,存在infa,b,supa,b. 由吸收律知 a（ab）= a，b（ab）= b， 故有a（ab），b（ab）。亦即，ab是 a，b的上界。证明若cL，且c是a，b的上界，亦即有 ac，bc，则应有 ac=c，bc=c， 于是， （ab）c =（ab）（cc）=（ac）（bc）= cc =c 故有（ab）c。 因此，（ab）是a，b的最小上界，即 supa，b=（ab）。 同理可证，infa，b=（ab）。 综上，（L，）为半序格。 代数子格定义B 设(L,)是一个代数格，S L， (S,)称为(L,)的一个代数子格，当且 仅当在运算,下，S是封闭的。结论：(S,)是格(L,)的子格的充 要条件是：SL且（S,）是一个格。 例.(Sn, ,)是(I+,)的代数子格，其中 ,分别是最高公因和最小公倍运算。代数子格与半序子格的关系设（L，）是一个半序格，与其等价的代数格为（L，），S L。若（S，）是（L，）的代数子 格，则（S，）是（L，）的半序子格；若（S，）是（L，）的半序子格， 则（S，）不一定是（L，）的代 数子格。 a6a3a1a2a4a5a8a7设L=a1,a2,a3,a4,a5,a6,a7,a8,（L,）是格。取S1=a1,a2,a4,a6,则（S1,）是（L,）的半 序子格，也是（L,）的代数子格。取S2=a1,a2,a4,a8,则(S2 ,)是(L,)的半序 子格,但(S2,)不是(L,)的代数子格。 因为:a2a4=a6,而a6S2,即,S2在下不封闭。