第六章格与布尔代数

第六章格和布尔代数1在第一章我们介绍了命题逻辑。当时被侧重的只是形式系统。如果视P为全体命题的集合，于是逻辑联词∨，∧就可以被看作P上的两个二元代数运算。因而，(P,∨,∧)是一个代数,即通常所说的命题代数。在命题代数中，运算∨,∧满足幂等律，交换律，结合律，分配律和吸收律。格与布尔代数2在第三章我们介绍了集合的最为一般的一些理论，被关心的只是集合的基本概念，集合的运算和基数等方面的事实。如果我们令S＝2A，对于X,YS,则都有X∪Y，X∩YS。在这两种二元运算下，(S,∪,∩)是代数,即所谓幂集代数。3在幂集代数中,运算∪,∩满足幂等律,交换律,结合律,分配律和吸收律.在幂集代数中引进了补集的概念和在命题代数中引进了否定的概念之后,则在这两种代数中,都具有了DeMorgan律.4从代数的观点出发，我们是否能对一种更为抽象的代数系统进行研究,使得幂集代数,命题代数仅仅是它的特例?回答是肯定的.这种抽象的代数系统就是格和布尔代数.研究布尔代数首先要研究格,因为布尔代数是一种特殊的格.5格作为数学中一个很有特色的分支,大体上说形成于二十世纪的三十到四十年代.格作为一种理论,它不只是代数学的一个部分,而且在近代解析几何,半序空间等方面也都有重要的作用.布尔代数的问世比格要早,在十九世纪中叶,由英国数学家乔治·布尔研究并提出。6格和布尔代数在计算机科学中有广泛的应用，象有限自动机理论,开关网络理论，逻辑设计等领域都直接地应用了格和布尔代数的结论。7一个布尔代数是一个有补分配格.一个格是这样的一个偏序集,在这个偏序集中,每两个元素都有唯一一个最小上界和唯一一个最大下界.可见,我们首要的任务是讨论偏序和确界的一些有关的性质,以作为我们本章要讲述内容的基础.86-1格的概念定义6-1.1设<A，>是一个偏序集，如果A中任意两个元素都有最小上界(上确界)和最大下界(下确界)，则称<A，>为格。1格的定义

9说明：由于确界唯一，所以在格<A，>中，对A中任意元素a,b，求其上确界或下确界的结果是<A，>中唯一的元素.从代数的意义上说，求上确界和下确界都是格<A，>中的二元运算。由定义6-1.1及全序定义,有:任何一个全序集都是格.

但是任何一个偏序集并非总是格.这其实也是明显的。从逻缉的角度讲，格定义在偏序集上，其内涵的增加必然导致外延的缩小。

10例：考查下面Hasse图（哈斯图）:是偏序集但非格的Hasse图中,总有元素a,b,使得{a,b}没有上确界或下确界。11(a)链是格;(b)偏序,格;(c)偏序,格;(d)偏序,格;(e)偏序,非格;(f)偏序,非格.12例1设S是任意集合,则<P(S),⊆>是格。|S|=1时和|S|=2时,此格的Hasse图为:13例2设I+为正整数集,偏序关系为整除｜,则<I+,｜>是格,此时对a,b∈I+,a、b的上确界是[a,b](最小公倍数)，a、b的下确界是(a,b)(最大公因数)。14例设n为正整数,Sn是n的全部正因数的集合,则<Sn,｜>是格.<S24,｜>和<S30,|>的Hasse图如下:152格诱导的代数系统

定义6-1.2

设<A，>是一个格，如果在A上定义两个二元运算∨和∧，使得对于任意的a，b∈A，a∨b等于a和b的最小上界，a∧b等于a和b的最大下界，那么，就称<A，∨，∧>为由格<A，>所诱导的代数系统。二元运算∨和∧分别称为并运算和交运算。

16例3给定S＝{a，b}，P(S)＝{φ，{a}，{b}，{a，b}}，那么，格<P(S)，⊆>如图6-1.3所示。

17由格<P(S)，⊆>所诱导的代数系统为<P(S)，∨，∧>，其中运算∨是集合的并，运算∧是集合的交。故∨和∧的运算表可分别由表6-1.1的(a)和(b)所示。

183子格

定义6-1.3

设<A，>是一个格，由<A，>诱导的代数系统为<A，∨，∧>，设B⊆A且B≠φ，如果A中的这两个运算∨和∧关于B是封闭的，则称<B，>是<A，>的子格。

可以证明子格必成为格。19注意：对于格<A，>，设B是A的非空子集，尽管<B，>必定是一个偏序集，然而<B，>不一定是格，而且即使<B，>是格，也不一定是<A，>的子格。

20例5设<S,>是一个格，其中S={a,b,c,d,e,f,g,h}，如图所示。取S1={a,b,d,f,}S2={c,e,g,h}S3={a,b,c,d,e,g,h}从图6-1.4上容易看出，<S1，>和<S2，>都是<S，>的子格，而<S3，>虽然是格，但它不是<S，>的子格，这是因为b∧d＝fS3

21例题1

设<S，>是一个格，任取a∈S，构造S的子集T为：T＝{x|x∈S且xa}

则<T，>是<S，>的一个子格。对于任意的x，y∈T,必有xa和ya

解：所以

x∨ya，

x∧ya

故

x∨y∈T，

x∧y∈T因此，<T，>是<S，>的一个子格。

224对偶

在命题代数、集合代数中,我们应用了对偶原理。在比命题代数和集合代数更为一般的格与布尔代数中,我们也将应用对偶原理。对偶原理是很重要的概念，它出现在许多不同的场合和领域。下面是两个生活中的例：人体镜面成像中,如果人体(或镜中的像)X能将左手覆于右臂之上,那么X的像(或原像)X*就能将右手覆于左臂之上。

23国内汽车交通规则,司机座在驾驶室左侧,并规定汽车前行要沿马路右侧,超车须从左边道,红灯禁行时汽车可以右转弯;英国汽车,司机座在驾驶室右侧,英国交通规则规定汽车前行要沿马路左侧,超车要从右边道,红灯禁行时汽车可以左转弯.在这里,左和右的概念都作互相交换;交换的结果形成了各自的交通规则。

左和右就是一种对偶概念24格<A,>上偏序关系作为二元关系,自然可逆，我们称这一个逆关系为的对偶关系,记为。偏序关系的逆,把<A,

>的Hasse图作了上下的翻转.于是,对集合A的任意子集B,B在偏序<A,>中的上确界,便成了B在偏序<A,>中的下确界;B在<A,>中的下确界,就是B在<A,>中的上确界.<A,>之所以可称之为偏序集,是因为二元关系的逆关系，保持原关系的自反、反对称和传递性不变,即偏序关系之逆关系仍为偏序关系.从以上分析,我们可以断言:若<A,>是格,则<A,>也是格,当然反之亦真.并称格<A,>与格<A,>为对偶的格.

25设P是对任意格都为真的命题，如果在命题P中把换成，∨换成∧，∧换成∨，就得到另一个命题P′，把P′称为P的对偶命题，则P′对任意格也是真的命题。

265格的基本性质

格是偏序集,具有偏序集的性质.<A,>是格，对a,b,cA,则:(1)aa;(自反性)(2)若ab且ba则a=b;(反对称性)(3)若ab且bc则ac;(传递性)27证明：28证明：29格的保序性

30定理6-1.3设<A，>是一个格，由格<A，>所诱导的代数系统为<A，∨，∧>，则对任意的a，b，c，d∈A，有

(1)a∨b=b∨aa∧b=b∧a（交换律）

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

(3)a∨a=aa∧a=a(4)a∨(a∧b)=aa∧(a∨b)=a（幂等律）

（吸收律）31证明：(1)格中任何两个元素a，b的最小上界（最大下界）当然等于b，a的最小上界（最大下界），故a∨b=b∨a（a∧b=b∧a）32其它结论利用对偶原理可证33例6设<N，≤>是一个偏序集合，这里N是自然数集，≤是普通的数与数之间的“小于等于”关系．因为对于任意的a，b∈N，有a∨b＝max(a，b)，a∧b＝min(a，b)，所以，<N，≤>是一个格，由这个格所诱导的代数系统是<N，∨，∧>。

分析：在此代数系统中，任意两个数a和b的最大值(最小值)与b和a的最大值(最小值)是相等的，因此，并运算和交运算都是可交换的；又因为max(max(a，b)，c)和max(a，max(b，c))都是三个数a，b，c中的最大值，所以在<N，∨，∧>中并运算是可结合的，同理min(min(a，b)，c)＝min(a，min(b，c))，说明交运算的可结合性；由于max(a，a)＝min(a，a)＝a，所以幂等性成立；又由于max(a，max(a，b))＝a和min(a，max(a，b))＝a，因此，吸收性也成立。346从代数系统到格引理6-1.1

设<A,∨,∧>是一个代数系统，其中∨，∧都是二元运算且满足吸收律，则∨和∧都满足幂等律。

证明：因为运算∨和∧满足吸收律，即对任意a，b∈A，有a∨(a∧b)=a(1)a∧(a∨b)=a(2)将(1)式中的b取为a∨b，便得a∨(a∧(a∨b))=a再由(2)，即得a∨a=a同理可证a∧a=a35证明：363738证明a∨b是a和b的最小上界。

397格的性质

证明：40证明：41证明：4243448格同态

45证明：定理6-1.8说明格同态是保序的

46定理6-1.8的逆命题不一定成立。

例7设<S，>是一个格，其中S={a，b，c，d，e}，如图所示。

我们知道，<P(S)，⊆>也是一个格

作映射f：S→P(S)

4748证明：4950作业：P243(5)(8)516-2分配格

1分配格的定义

5253图(a)中：

b∧(c∨d)=b∧a=b而(b∧c)∨(b∧d)=e∨e=e所以b∧(c∨d)≠(b∧c)∨(b∧d)

5455注意：

在分配格的定义中，必须是对任意的a，b，c∈A都要满足分配等式，因此，决不能验证格中的某些元素满足分配等式就断定该格是分配格。

56例2中给出的两个具有五个元素的格是很重要的，因为有一个定理证明了如下的结论：一个格是分配格的充要条件是该格中没有任何子格与这两个五元素格中的任一个同构。572分配格的性质

定理6-2.1

如果在一个格中交运算对于并运算可分配，则并运算对于交运算也一定是可分配的。反之亦然。

证明：58定理6-2.2每个链是分配格。

证明：

5960证明：

613模格

62证明：636465证明：66定理6-2.6

分配格必定是模格。

证明：因此

676-3有补格

1有界格

68证明:697071定义6-3.3

如果一个格中存在全下界和全上界，则称该格为有界格。

证明：72注意：由a∨0=0∨a=a和a∧1=1∧a=a说明0和1分别是关于运算∨和∧的幺元。另外，0和1分别是关于运算∧和∨的零元。

732有补格

定义6-3.4设<A，>是一个有界格，对于A中的一个元素a，如果存在b∈A，使得a∨b=1和a∧b=0，则称元素b是元素a的补元。

说明：在定义6-3.4中，a和b是对称的，即如果a是b的补元，则b也是a的补元，因此，a和b这两个元素是互补的。对于元素a∈A，可以存在多个补元，也可以不存在补元。在有界格中，0是1的唯一补元，1是0的唯一补元。74例3在如图所示的有界格中，因为d∨c=1和d∧c=0，所以，d和c是互补的。但是b是没有补元的。此外，a和d都是e的补元；c和e都是d的补元。

75定义6-3.5

在一个有界格中，如果每个元素都至少有一个补元素，则称此格为有补格。例4图6-3.3中给出了一些有补格。

76定理6-3.4

在有界分配格中，若一个元素有补元素，则必是唯一的。

证明：

设a有两个补元素b和c，即有a∨b=1

a∧b=0a∨c=1

a∧c=0由定理6-2.3即得b=c。这就证明了a的补元素是唯一的。773有补分配格

定义6-3.6

一个格如果它既是补格，又是分配格，则称它为有补分配格。有补分配格中任一元素a的唯一补元记为。

786-4布尔代数

1布尔格

定义6-4.1一个有补分配格称为布尔格。

注明：792布尔代数

8081证明：823一些概念

834原子

例2如图所示的格中，d，e都是原子且d∧e=0，说明原子不是唯一的。1盖住a，b，c；a盖住d；c盖住e；b盖住d，e，这说明一个元素可以盖住多个元素。84证明：85说明：865布尔代数的性质

证明：87证明：8889证明:9091证明：926布尔代数的同构形式

证明：93949596现分别证明如下：

979899100推论6-4.1有限布尔格的元素个数必定等于2n，其中n是该布尔格中所有原子的个数。

推论6-4.2任何一个具有2n个元素的有限布尔代数都是同构的。1016-5布尔表达式

1布尔表达式及其值

定义6-5.1设<A，∨，∧，－>是一个布尔代数，在这个布尔代数上定义布尔表达式如下：1.A中任何元素是一个布尔表达式。2.任何变元是一个布尔表达式。3.如果e1和e2是布尔表达式，那么，

，(e1∨e2)和(e1∧e2)也都是布尔表达式。4.只有通过有限次运用规则2和3所构造的符号串是布尔表达式。102例2设<{0，1，2，3}，∨，∧，－>是一个布尔代数。

布尔表达式：

含有单个变元x1的布尔表达式

含有两个变元x1，x2的布尔表达式含有三个变元x1，x2，x3的布尔表达式103定义6-5.2

一个含有n个相异变元的布尔表达式，称为含有n元的布尔表达式。记为E(x1，x2，…，xn)，其中x1，x2，…，xn为变元。

定义6-5.3

布尔代数<A，∨，∧，－>上的一个含有n元的布尔表达式E(x1，x2，…，xn)的值是指：将A中的元素作为变元xi(i＝1，2，…，n)的值来代替表达式中相应的变元(即对变元赋值)，从而计算出表达式的值。

1041052布尔表达式的等价

106如：107说明：由于布尔代数是有补分配格，当对布尔表达式赋值后，表达式中运算∨对于运算∧是可分配的，运算∧对于运算∨也是可分配的。因此，如果将布尔表达式中的变元看作是已经赋值的，那么，上例中的E1和E2的等价性可以直接写为

108对于布尔代数<A，∨，∧，－>上的任何一个布尔表达式，E(x1，x2，…，xn)。由于运算∨，∧，－在A上的封闭性，所以对于任何一个有序n元组<x1，x2，…，xn>，xi∈A，可以对应着一个表达式E(x1，x2，…，xn)的值，这个值必属于A。由此可见，可以说布尔表达式E1(x1，x2，…，xn)确定了一个由An到A的函数。109例：110不是任意一个从An到A的函数都一定能列出一个在<A，∨，∧，－>上的布尔表达式。1113布尔函数及合取范式、析取范式

定义6-5.5设<A，∨，∧，－>是一个布尔代数，一个从An到A的函数，如果它能够用<A，∨，∧，－>上的n元布尔表达式来表示，那么，这个函数就称为布尔函数。

定理6-5.1对于两个元素的布尔代数<{0,1}，∨，∧，－>，任何一个从{0,1}n到{0，1}的函数都是布尔函数。

112证明：

一个在<{0，1}，∧，∨，－>上的布尔表达式，如果它能表示成小项的并，则称这个布尔表达式为析取范式。

113114例5讨论表6-5.3所给的函数f的析取范式和合取范式。

115116117118正因为任何一个从{0，1}n到{0，1}的函数，它的函数值只可能是1或0，因此，总可以用上述方法得到该函数所对应的析取范式、合取范式。

1194析取范式、合取范式的进一步讨论

120定理6-5.2设E(x1，x2，…，xn)是布尔代数<A，∨，∧，－>上的任意一个布尔表达式，则它一定能写成析取范式。

证明：

令E(xi＝a)＝E(x1，x2，…，xi-1，a，xi+1，…，xn