引言8.2格的定义(离散数学)

《引言8.2格的定义(离散数学)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章格与布尔代数§8.1引言集合代数：（ρ(S)，∪，∩）对A,B,C∈ρ(S)，运算∪，∩满足：等幂律A∩A=A，A∪A=A，交换律A∩B=B∩A，A∪B=B∪A，结合律A∩（B∩C）=（A∩B）∩C，A∪（B∪C）=（A∪B）∪C，分配律A∩（B∪C）=（A∩B）∪（A∩C），A∪（B∩C）=（A∪B）∩（A∪C），吸收律A∩（A∪B）=A，A∪（A∩B）=A，若引进余集ˉ的概念，有DeMorgan定律:命题代数（S，∧，∨）对A,B,C∈S，运算∧，∨满足：等幂律A∧A=A，A∨A=A，，交换律A∧B=B∧A，A∨B=B∨A结合律A

2、∧（B∧C）=（A∧B）∧C，A∨（B∨C）=（A∨B）∨C分配律A∧(B∨C)=(A∧B)∨(A∧C)，A∨（B∧C）=（A∨B）∧（A∨C）吸收律A∧(A∨B)=A，A∨（A∧B）=A，若引进否定的概念，有DeMorgan定律:(A∧B)=A∨B,(A∨B)=A∧B,§8.2格的定义半序格定义A给出一个部分序集（L，≤）,如果对于任意a，b∈L，L的子集{a，b}在L中都有一个最大下界(记为inf{a，b})和一个最小上界（记为sup{a，b}），则称（L，≤）为一个格。半序格的例例.S是任意一个集合，ρ(S)是S的幂集合，则

3、，部分序集(ρ(S)，)是一个格。因为对A,B∈ρ(S)，sup{A,B}=A∪B∈ρ(S),inf{A,B}=A∩B∈ρ(S)例.设I+是所有正整数集合，D是I+中的“整除关系”，对任意a，b∈I+，aDb当且仅当a整除b，于是，（I+，D）是一个格。sup{a，b}=a，b的最小公倍∈I+，inf{a,b}=a，b的最高公因∈I+。半序格的例例.设n是一个正整数，Sn是n的所有正因数的集合，于是，（Sn，D）是格。因为sup{a，b}=a，b的最小公倍∈Sn，inf{a,b}=a，b的最高公因∈Sn。例.设S是所有的命题集合，定义“”如

4、下：AB当且仅当B蕴涵A。则（S，）是一个格。因为sup{A，B}=A∧B∈S，inf{A，B}=A∨B∈S。半序子格定义A′设（L，≤）是格，SL，如果（S，≤）是格，则称（S，≤）是格（L，≤）的子格。例.（S6，D）是（S24，D）的子格。代数格定义B设L是一个集合，×，⊕是L上两个二元代数运算，如果这两种运算对于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⊕b）=a，a⊕（a×b）=a。则称此代数系统（L，×，）为一个格

5、。note:定义B中由×，⊕满足吸收律可推出它们一定满足等幂律。证明：任取L中元素a，由×，⊕满足吸收律知，a×（a⊕a）=a，a⊕（a×a）=a。故a×a=a×（a⊕（a×a）），a⊕a=a⊕（a×（a⊕a））。又由×，⊕满足吸收律知，上面两式的等式右端都等于a。因此，a×a=a，a⊕a=a。即，定义B中的×，运算亦满足等幂律。代数格的例例.设S是一个集合,ρ(S)是S的幂集合，于是，(ρ(S),∩,∪)是一个代数格。而(ρ(S)，)是半序格。易见对A,B∈ρ(S)，ABA∩B=AA∪B=B。例.设I+是所有正整数集合,两个正整数的最高

6、公因×,最小公倍⊕是I+上两个代数运算，于是,(I+,×,⊕)是一个代数格。而（I+,D）是半序格,D是整除关系。易见，对任意a，b∈I+,aDba×b=aa⊕b=b。例.设n是一个正整数,Sn是n的所有正因数的集合,两个正整数的最高公因×,最小公倍⊕可是Sn上两个代数运算,于是,(Sn,×,⊕)是一个代数格。代数格与半序格的等价性定理8.2.1定义A所定义的格和定义B所定义的格是等价的，亦即，一个半序格必是一个代数格；反之亦然。证明：i）若(L,≤)是一个半序格,则对a,b∈L，记inf{a，b}为a×b；sup{a，b}为a⊕b。由于对任

7、意a，b，其inf{a，b}，sup{a，b}是唯一的，所以，如上定义的×，⊕是集合L上的两种二元代数运算。不难证明,对于×,⊕满足交换律,结合律,吸收律。则根据定义B,(L,×,⊕)是一个代数格。我们只证明吸收律：a×（a⊕b）=a为例，其它算律的证明留给读者。因为a×(a⊕b)是a与(a⊕b)的最大下界，所以a×(a⊕b)≤a另一方面，由于a≤a，a≤a⊕b，所以，a是a与a⊕b的下界，故a≤a×(a⊕b)所以，a=a×(a⊕b)。证明证明ii）若代数系统（L，×，⊕）是一个代数格，在集合L上定义一个关系≤如下：对任意a，b∈L，a≤ba×

8、b=a①往证：≤是一个半序关系。反身性:因为a×a=a×(a⊕(a×a))=a,所以a≤a。反对称性:若有a≤b,b≤a,则应有a×b=a，b×a=b