格与布尔代数ppt课件.ppt

《格与布尔代数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章格与布尔代数§8.1引言在第一章中我们介绍了关于集合的理论。如果将ρ（S）看做是集合S的所有子集组成的集合，于是，ρ（S）中两个集合的并集A∪B，两个集合的交集A∩B，就可以看做是ρ（S）上的两个代数运算，因此，（ρ（S），∪，∩）可看做是一个代数，这就是通常所说的集合代数。在集合代数中，对运算∪，∩满足：(1) 等幂律A∩A=A，A∪A=A，(2) 交换律A∩B=B∩A，A∪B=B∪A，(3) 结合律A∩（B∩C）=（A∩B）∩C，A∪（B∪C）=（A∪B）∪C，(4) 分配律A∩（B∪C）=（A∩B）∪（A∩C），A∪（B∩C）=（A∪B）∩（A∪C）

2、，(5) 吸收律A∩（A∪B）=A，A∪（A∩B）=A，等等。在第二章中我们介绍了命题逻辑。如果将S看做是所有命题的集合，于是，逻辑连结词∨，∧就可以看做是集合S上的两个代数运算，因此，（S，∧，∨）可看做是一个代数。这就是通常所说的命题代数。在命题代数中，运算∧，∨也满足（1）等幂律A∧A=A，A∨A=A，（2）交换律A∧B=B∧A，A∨B=B∨A，（3）结合律A∧（B∧C）=（A∧B）∧C，A∨（B∨C）=（A∨B）∨C，（4）分配律A∧（B∨C）=（A∧B）∨（A∧C），A∨（B∧C）=（A∨B）∧（A∨C），（5）吸收律A∧（A∨B）=A，A∨（A∧B）

3、=A，等等。如果在集合代数中引进余集ˉ的概念，在命题代数中引进否定的概念，则在这两种代数中都有类似的所谓DeMorgan定律。即，=∪，=∩，(A∧B)=A∨B，(A∨B)=A∧B。从代数的观点出发，我们是否能对一种更为抽象的代数系统进行研究，而这种抽象的代数系统又具有象集合代数，命题代数那样具体的代数系统所具的一些最本质的性质？回答是肯定的，这种抽象的代数系统就是格（Lattice）和布尔代数（BooleanAlgebra）§8.2格的定义定义A给出一个部份序集(L，≤），如果对于任意a，b∈L，L的子集{a，b}在L中都有一个最大下界（记为in

4、f{a，b}）和一个最小上界(记为sup{a，b}),则称（L，≤）为一个格，显然，一个序集是一个格，但是，不是所有部份序集都是格。下面给了一些格的例子，这些例子在本章中要经常用到。例8.2.1S是任意一个集合，ρ（S）是S的幂集合,于是,部份序集（ρ（S），）是一个格。对任意A,Bρ(S)sup{A，B}=A∪Bρ(S)，inf{A，B}=A∩Bρ(S)。当S仅有一个元素时，对应的格是包含两个元素的链。例8.2.2设I+是所有正整数集合，D是I+中的“整除关系”,亦即,对任意a，b∈I+，aDb当且仅当a整除b，于是，（I+，D）是一个格。不难说明，“

5、整除关系”是部份序关系，I+中子集{a，b}的最小上界就是a,b的最小公倍,子集{a,b}的最大下界就是a，b的最高公因。例8.2.3设n是一个正整数，Sn是n的所有正因数的集合。例如，S6={1，2，3，6}，S24={1,2,3,4,6,8,12,24}。设D是“整除关系”，于是,（S6，D）,（S8，D）,（S24，D）和（S30，D）都是格.例8.2.4设S是所有的命题集合，定义“”关系如下：AB当且仅当B蕴涵A。则（S，）是一个格。sup{A，B}=A∧BS，inf{A，B}=A∨BS。定义A′设（L，≤）是格,S是L的子集,即SL，如果（

6、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,×,）为一个格。定义中没有要求×,运算满足等幂律,实际上由×,满足吸收律即可推出它们一定满足等幂律.任取L中元素a，由×，满足吸收律知，a×（aa）=a，a（a×a）=a。故a×a=

7、a×（a（a×a）），aa=a（a×（aa））。又由×，满足吸收律知，上面两式的等式右端都等于a。因此，a×a=a，aa=a。即,定义B中的×，运算亦满足等幂律。例8.2.5设S是一个集合,ρ(S)是S的幂集合，集合的交（∩），并（∪）是ρ（S）上的两个代数运算，于是,（ρ（S），∩，∪）是一个格。而由例8.2.1知（ρ（S），）是半序格。易见对ABA∩B=AA∪B=B。例8.2.6设I+是所有正整数集合，两个正整数的最高公因×，最小公倍可看做是I+上两个代数运算，于是，（I+，×，）是一个格。而由例8.2.2知（I+，D）是半序格。易

8、见，对任意a，bI+，