格和布尔代数精简

格和布尔代数精简2023/4/111第1页，共69页，2023年，2月20日，星期五第七章格与布尔代数7.1

格7.2

子格和格同态7.3

特殊的格7.4

布尔代数与布尔表达式2023/4/112第2页，共69页，2023年，2月20日，星期五7.1格格的定义：设<L,≤>是一个偏序集，如果集合L中的任意两个元素都有最小上界和最大下界，则称<L,≤>为格。2023/4/113第3页，共69页，2023年，2月20日，星期五7.1格【例题1】判断下图中所示各哈斯图代表的偏序集合是否是格？为什么？abcdefabcdeabcdefabcdabcdabcdefghabcdeabcde2023/4/114第4页，共69页，2023年，2月20日，星期五7.1格【例题2】设I+是正整数集合，定义I+上的二元关系“|”,任取a,b∈I+,a|b当且仅当a能整除b。证明:<I+,|>是一个格。证明：I+上的二元关系|是自反、反对称和传递的，因此<I+,|>是一个偏序集合。任取a,b∈I+,

a与b在偏序集合<I+,|>中的最小上界是其最小公倍数:lub{a,b}∈I+。任取a,b∈I+,a与b在偏序集合<I+,|>中的最大下界是其最大公约数：glb{a,b}∈I+。结论得证。2023/4/115第5页，共69页，2023年，2月20日，星期五7.1格【例题3】设S是任意集合，ρ(S)是S的幂集，偏序集合<ρ(S),>是否是格？解答:任取A,B∈ρ(S),

A与B在偏序集合<ρ(S),>中的最小上界是A∪B∈ρ(S),A与B在偏序集合

<ρ(S),>中的最大下界是A∩B∈ρ(S)。2023/4/116第6页，共69页，2023年，2月20日，星期五7.1格保交运算

a∧b=glb{a,b},求a,b的最大下界保联运算

a∨b=lub{a,b},求a,b的最小上界『定理』(格的对偶定理)如果<L,≤>是一个格，则<L,≥>也是一个格。设P是一个命题，P的对偶命题P*是将关系符≤换成≥，将保交∧与保联∨运算符互换所得的命题。若P中对一切格都为真，则P*对一切格也都为真。2023/4/117第7页，共69页，2023年，2月20日，星期五7.1格【例题】设<L,≤>是一个格,其哈斯图如下图所示，画出<L,≥>的哈斯图。解答：<L,≥>是<L,≤>的对偶格，因此其哈斯图可由<L,≤>旋转180°得到，如(b)图所示。(a)(b)2023/4/118第8页，共69页，2023年，2月20日，星期五7.1代数格代数格：设<L,≤>是一个格，a,b∈L。在L上可以定义两个运算*和：

a*b=glb{a,b}

也可写成a∧b=glb{a,b}

ab=lub{a,b}

也可写成a∨b=lub{a,b}

则称<L,*,>(或<L,∧,∨>)为格<L,≤>所诱导的代数系统，简称代数格。2023/4/119第9页，共69页，2023年，2月20日，星期五7.1代数格的性质『定理1』在一个格<A,≤>中，对任意的a,b∈A,都有

a≤a∨b,b≤a∨b

a∧b≤a,a∧b≤b证明：因为a和b的并是a的一个上界，所以

a≤a∨b

同理b≤a∨b

由对偶原理即得a∧b≤a,a∧b≤b2023/4/1110第10页，共69页，2023年，2月20日，星期五7.1代数格的性质『定理2』在一个格<A,≤>中，对于a,b,c,d∈A,如果a≤b

和c≤d

则a∨c≤b∨d

a∧c≤b∧d证明：因为b≤b∨d,d≤b∨d,由传递性可得a≤b∨d,c≤b∨d

这就表明b∨d是a和c的一个上界，而a∨c

是a和c的最小上界，所以，必有2023/4/1111第11页，共69页，2023年，2月20日，星期五7.1代数格的性质

a∨c≤b∨d

类似地可以证明a∧c≤b∧d2023/4/1112第12页，共69页，2023年，2月20日，星期五7.1代数格的基本性质由格诱导的代数系统满足以下性质：(1)自反性a≤a(2)反对称性(a≤b)且

(b≤a)a=b(3)传递性(a≤b)且

(b≤c)a≤c(4)a∧b≤a,a∧b≤b

a≤a∨b,b≤a∨b(5)(c≤a)

且(c≤b)c≤(a∧b),

(b≤c)且(a≤c)

c≥(a∨b)(6)交换律a∧b=b∧a

a∨b=b∨a2023/4/1113第13页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(7)结合律(a∧b)∧c=a∧(b∧c),

(a∨b)∨c=a∨(b∨c)(8)等幂律a∧a=a,

a∨a=a

(9)吸收律a∧(a∨b)=a,a∨(a∧b)=a(10)a≤ba∧b=aa∨b=b(11)a≤b

且d≤c

a∧d≤b∧c

a≤b

且d≤c

a∨d≤b∨c2023/4/1114第14页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(12)保序性b≤ca∧b≤a∧c,

b≤ca∨b≤a∨c(13)分配不等式a∨(b∧c)≤(a∨b)∧(a∨c)a∧(b∨c)≥(a∧b)∨(a∧c)

(14)模不等式a≤ca∨(b∧c)≤(a∨b)∧c证明：(7)由定理1可知

b≤b∨c≤a∨(b∨c)

和a≤a∨(b∨c)

2023/4/1115第15页，共69页，2023年，2月20日，星期五7.1代数格的基本性质由定理2可知

a∨b≤a∨(b∨c)

又因c≤b∨c≤a∨(b∨c)

说明a∨(b∨c)

是a∨b和c的上界,而(a∨b)∨c是a∨b和c的最小上界，因此

(a∨b)∨c≤a∨(b∨c)类似得可以证明

a∨(b∨c)≤(a∨b)∨c因此a∨(b∨c)=(a∨b)∨c

由对偶原理可得a∧(b∧c)=(a∧b)∧c

2023/4/1116第16页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(8)由定理1可知a≤a∨a由自反性可知a≤a由此可得a∨a≤a因此a∨a=a利用对偶原理可得a∧a=a(9)根据定理1可得a≤a∨(a∧b)因为a≤a,a∧b≤a

因此a∨(a∧b)≤a所以a∨(a∧b)=a利用对偶原理，即得a∧(a∨b)=a2023/4/1117第17页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(10)首先证明a≤ba∧b=a因为a≤b和a≤a,就有a≤a∧b,但由定理1可知a∧b≤a,由反对称性，得a∧b=a。这就证明了a≤ba∧b=a。反之，假定a∧b=a，则a=a∧b≤b,这就证明了a∧b=aa≤b因此a≤ba∧b=a用同样得方法可以a≤ba∨b=b2023/4/1118第18页，共69页，2023年，2月20日，星期五7.1代数格的基本性质最后证明a∧b=aa∨b=b根据定理1可知a∨b≥b,而a∧b≤b,因为a∧b=a,故a≤b,而b≤b,因此a∨b≤b,这样就得到了a∨b=b，即a∧b=aa∨b=b。反之，假定a∨b=b,由定理1可知a∧b≤a,因为a∨b=b，故b=a∨b≥a,而a≥a,因此a∧b≥a,这样就得到了a∧b=a,即a∨b=ba∧b=a

。因此得到a∧b=aa∨b=b2023/4/1119第19页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(13)由定理1可知a≤a∨b和a≤a∨c,由定理2可知

a≤(a∨b)∧(a∨c)(1)另外由于b∧c≤b≤a∨b,b∧c≤c≤a∨c,故b∧c≤(a∨b)∧(a∨c)(2)

因此由(1)、(2)可得：a∨(b∧c)≤(a∨b)∧(a∨c)

利用对偶原理，即得

a∧(b∨c)≥(a∧b)∨(a∧c)

2023/4/1120第20页，共69页，2023年，2月20日，星期五7.1代数格的基本性质(14)由性质(10)有a≤c(a∨c)=c

再由性质(13)有a∨(b∧c)≤(a∨b)∧(a∨c)

用c替代上式中的(a∨c)，即得

a∨(b∧c)≤(a∨b)∧c所以a≤ca∨(b∧c)≤(a∨b)∧c另外，若a∨(b∧c)≤(a∨b)∧c,则明显地有

a≤a∨(b∧c)≤(a∨b)∧c≤c所以a∨(b∧c)≤(a∨b)∧ca≤c

因此a≤ca∨(b∧c)≤(a∨b)∧c2023/4/1121第21页，共69页，2023年，2月20日，星期五7.1格『定理』设<A,∧,∨>是一个代数系统，其中运算∧和∨都满足吸收律，则运算∧和∨都满足等幂律。证明：由于∧和∨都满足吸收律，则任取a,b∈A,有a∧(a∨b)=a(1)

a∨(a∧b)=a(2)将(1)式中的b用(a∧b)替换得

a∧(a∨(a∧b))=a∧a=a

2023/4/1122第22页，共69页，2023年，2月20日，星期五7.1格将(2)式中的b用(a∨b)替换得到

a∨(a∧(a∨b))=a∨a=a

故∧和∨都满足等幂律。2023/4/1123第23页，共69页，2023年，2月20日，星期五7.1格『定理』设<A,∧,∨>是一个代数系统，其中∧和∨都是二元运算且满足交换律、结合律、吸收律，则A上存在偏序关系≤，使得<A,≤>是一个格。证明：在A上定义二元关系≤为：任取a,b∈A,a≤b

当且仅当a∧b=a。(i)证明≤是一个偏序关系。2023/4/1124第24页，共69页，2023年，2月20日，星期五7.1格任取a,b∈A,a∧a=a,根据≤的定义可知a≤a,因此a是自反的。设a≤b,b≤a,则a∧b=a=b,因此≤是反对称的。设a≤b,b≤c,则有

a∧b=a

和b∧c=ba∧c=(a∧b)∧c=a∧(b∧c)=a∧b=a则有a≤c。因此≤是传递的。因此可知<A,

≤>是一个偏序集合。

2023/4/1125第25页，共69页，2023年，2月20日，星期五7.1格(ii)证明任取a,b∈A,a和b存在最小上界和最大下界。因为(a∧b)∧a=a∧b∧a=a∧b(a∧b)∧b=a∧b∧b=a∧b因此a∧b≤a,a∧b≤ba∧b是a和b的下界。2023/4/1126第26页，共69页，2023年，2月20日，星期五7.1格设c是a和b的任意下界，即有c≤a且c≤b,则有

c∧a=c且c∧b=c而c∧(a∧b)=(c∧a)∧b=c∧b=c所以有c≤a∧b。由此可知，a∧b是a和b的最大下界。同理可证，a∨b是a和b的最小上界。由(i)、(ii)可知，<A,

≤>是一个格。2023/4/1127第27页，共69页，2023年，2月20日，星期五7.2子格子格：设<L,≤>是一个格，<L,∧,∨>是由<L,≤>所诱导的代数系统。SL且S≠,

如果L中的两个运算∧和∨在S上是封闭的，则称<S,≤>是<L,≤>的子格。

格<L,≤

>载体L的一个子集S如果对原保交和保联运算都封闭，称<S,≤>是<L,≤>的子格。子格是子代数的概念在格上的扩展。2023/4/1128第28页，共69页，2023年，2月20日，星期五7.2子格【例题】图(a)、(b)中所示的格<S’,≤>分别是格<S,≤>的子格吗？(a)abdcedeab<S,≤><S’,≤>(b)一个格中的部分元素在原偏序关系上构成一个格，不能说明它就是原格的子格。主要看该子集上的任意两个元素在原运算保交和保联下的结果是否也在该子集中。<S,≤>abecdffacd<S’,≤>e2023/4/1129第29页，共69页，2023年，2月20日，星期五7.2格同态格同态：设<L1,≤>和<L2,≤>是两个格，由它们所分别诱导的代数系统为<L1,∧,∨>和<L2,∧’,∨’>,其中∧和∧’是保交运算,∨和∨’是保联运算。如果存在一个从L1到L2的映射f,使得任取a,b∈L1满足

f(a∧b)=f(a)∧’f(b)f(a∨b)=f(a)∨’f(b)则称f为从<L1,≤>到<L2,≤>的格同态，称<f(L1),≤>为<L1,≤>的同态象。2023/4/1130第30页，共69页，2023年，2月20日，星期五7.2格同态【例题】设集合A={a,b,c},<A,≤>是一个格，其哈斯图如图(a)所示。集合B=(A),<B,>也是一个格，其哈斯图如图(b)所示。函数f:A→B,其中f(x)={y|y≤x}。证明:f是从<A,≤>到<B,>的格同态。(a)(b)abc{c}{b}2023/4/1131第31页，共69页，2023年，2月20日，星期五7.2格同态证明：<A,≤>是一个格，设其诱导的代数格为<A,∧,∨>，任取a,b∈A,因为<A,≤>是一个链，所以a∧b=min{a,b}a∨b=max{a,b}<B,>诱导的代数格为<B,∩,∪>。(i)A中元素在函数f下的象分别为

f(a)={a},f(b)={a,b},f(c)={a,b,c}故f是从A到B的单射函数。2023/4/1132第32页，共69页，2023年，2月20日，星期五7.2格同态(ii)f(x1∧x2)=f(min{x1,x2})={y|y≤min{x1,x2}}={y|y≤x1}∩{y|y≤x2}=f(x1)∩f(x2)

f(x1∨x2)=f(max{x1,x2})={y|y≤max{x1,x2}}={y|y≤x1}∪{y|y≤x2}=f(x1)∪f(x2)故f是从<A,≤>到<B,>的格同态。2023/4/1133第33页，共69页，2023年，2月20日，星期五7.2格同态性质『定理』(格同态的保序性)设f是从格

<L1,≤>到格<L2,≤’>的格同态，则对任意x,y∈L1,如果x≤y,必有f(x)≤’f(y)。

证明：因为x≤y，所以有x∧y=x,又

f(x∧y)=f(x)∧’f(y)=f(x)

故f(x)≤’f(y)。2023/4/1134第34页，共69页，2023年，2月20日，星期五7.2格同构格同构：设f是从格<L1,≤>到格<L2,≤’>的格同态，若f是双射函数，则称f为从

<L1,≤>到<L2,≤’>的格同构。具有一,二,三个元素的格,分别是一、二,三个元素的链,四个和五个元素对应表中同构格之一，如下表所示：2023/4/1135第35页，共69页，2023年，2月20日，星期五哈斯图1个元素的格2个元素的格3个元素的格4个元素的互不同构的格5个元素的互不同构的格2023/4/1136第36页，共69页，2023年，2月20日，星期五7.3特殊的格：分配格分配格：设<L,∧,∨>是由格<L,≤>所诱导的代数系统，如果对任意的a,b,c∈L,满足：

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

保交对保联可分配

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

保联对保交可分配

则称<L,≤>是分配格。2023/4/1137第37页，共69页，2023年，2月20日，星期五7.3分配格【例题】图(a)、(b)所示的格是分配格吗？为什么？分析：均不是分配格。考虑b∧(c∨d)与(b∧c)∨(b∧d)；考虑c∧(b∨d)与(c∧b)∨(c∧d)cabde(a)钻石格abcde(b)五角格2023/4/1138第38页，共69页，2023年，2月20日，星期五7.3分配格『定理』设<L,≤>是一个格，若∧运算对∨运算可分配，则∨对∧也可分配，反之亦然。证明：设∧运算对∨运算可分配，即任取a,b,c∈L,满足a∧(b∨c)=(a∧b)∨(a∧c)现要证a∨(b∧c)=(a∨b)∧(a∨c)(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)=a∨((a∨b)∧c)

2023/4/1139第39页，共69页，2023年，2月20日，星期五7.3分配格

=a∨((a∧c)∨(b∧c))=a∨(a∧c)∨(b∧c)=a∨(b∧c)由此可知，∨运算对∧运算也可分配。同理可证，若∨运算对∧运算可分配，则∧运算对∨运算也可分配。2023/4/1140第40页，共69页，2023年，2月20日，星期五7.3分配格『定理』每个链都是分配格。证明：设<L,≤>是一个链，则<L,≤>必是一个格。任取a,b,c∈L,讨论以下两种情况：(i)a≤b或a≤c无论是a≤b或a≤c都有

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

即a∧(b∨c)=(a∧b)∨(a∧c)

2023/4/1141第41页，共69页，2023年，2月20日，星期五7.3分配格(ii)b≤a且c≤a:由b≤a,c≤a知b∨c≤a，可得

a∧(b∨c)=b∨c

又因为(a∧b)∨(a∧c)=b∨c,所以有

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

由(i)、(ii)可知∧运算对∨运算可分配，于是∨运算对∧运算也可分配。故每个链都是分配格。2023/4/1142第42页，共69页，2023年，2月20日，星期五7.3分配格『定理』设<L,≤>是一个分配格，那么对于任意a,b,c∈L,如果有a∧b=a∧c和a∨b=a∨c成立，则必有b=c。证明：b=b∨(a∧b)=b∨(a∧c)=(b∨a)∧(b∨c)=(a∨c)∧(b∨c)=(a∧b)∨c=(a∧c)∨c=c2023/4/1143第43页，共69页，2023年，2月20日，星期五7.3分配格『定理』一个格是分配格，当且仅当它不存在与钻石格和五角格同构的子格。『定理』分配格的子格是分配格。2023/4/1144第44页，共69页，2023年，2月20日，星期五7.3有界格全上界(全下界)：如果格<L,≤>中存在一个元素a,对于任何元素b∈L,均有b≤a(a≤b),则称a为格<L,≤>的全上界(全下界)。通常将全上界记为“1”，而将全下界记为“0”。『定理』一个格<L,≤>若有全上界(全下界)，则是唯一的。2023/4/1145第45页，共69页，2023年，2月20日，星期五7.3有界格有界格：如果一个格既有全上界又有全下界，则称该格为有界格。『定理』设<A,≤>是一个有界格，则对任意a∈A,必有

a∨1=1,a∧1=aa∨0=a,a∧0=0『定理』每个有限格都是有界格。2023/4/1146第46页，共69页，2023年，2月20日，星期五7.3有补格补元：设<L,≤>是一个有界格，对于L中一个元素a,如果存在元素b∈L,使得a∧b=0,a∨b=1,则称元素b是a的补元，记为a’=b。同时，a也是b的补元，即b’=a。2023/4/1147第47页，共69页，2023年，2月20日，星期五7.3有补格【例题】写出下图所示的各有界格中所有元素的补元。1abc0c1bd0(b)(c)(d)(a)1a010abc2023/4/1148第48页，共69页，2023年，2月20日，星期五7.3有补格有补格：在一个有界格中，若每个元素至少有一个补元，则称此格为有补格。【例题】下图中各哈斯图所表示的格是否是有补格？为什么？01abcde10abcd10abcd01abcdef(a)(b)(c)(d)2023/4/1149第49页，共69页，2023年，2月20日，星期五7.3布尔格布尔格：若一个格既是有补格又是分配格，则称此格为布尔格。『定理』布尔格<L,≤>中，每一个元素都有唯一的补元。证明：<L,≤>是布尔格，因此L中的每一个元素都有补元。设a∈L,a有两个补元b,c∈L,根据补元的定义有：a∧b=0,a∧c=0a∨b=1,a∨c=1根据分配格的性质可知：b=c。2023/4/1150第50页，共69页，2023年，2月20日，星期五7.3布尔格【例题】设S是非空有限集合,证明

<ρ(S),>是一个布尔格。证明：<ρ(S),>是一个格，它诱导的代数格为<ρ(S),∩,∪>。因为<ρ(S),∩,∪>,有全上界S和全下届，因此它是有界格。任取T∈ρ(S),=S–T是T的补元，因此它是有补格。∩和∪是相互可分配的，因此它是分配格。综上所述，<ρ(S),>是一个布尔格。2023/4/1151第51页，共69页，2023年，2月20日，星期五7.4布尔代数与布尔表达式布尔代数：由布尔格<B,≤>可以诱导出一个代数系统<B,∧,∨,’>，该代数系统称为布尔代数。布尔格上的每个元素都有且仅有一个补元，因此布尔格诱导的代数系统有三个运算：保交、保联和补运算，其中求补运算是一元运算。2023/4/1152第52页，共69页，2023年，2月20日，星期五7.4布尔代数【例题】求由布尔格<ρ(S),>所诱导的布尔代数系统。解答：<ρ(S),∩,∪,>是由布尔格<ρ(S),>所诱导的一个布尔代数，其中∩、∪和分别是集合的交、并和补运算。2023/4/1153第53页，共69页，2023年，2月20日，星期五7.4布尔代数有限布尔代数：载体含有有限个元素的布尔代数称为有限布尔代数。布尔代数的性质：设<B,∧,∨,’>是一个布尔代数，任取a,b,c∈B都有性质成立：(1)交换律a∨b=b∨a,a∧b=b∧a(2)结合律a∨(b∨c)=(a∨b)∨c,a∧(b∧c)=(a∧b)∧c2023/4/1154第54页，共69页，2023年，2月20日，星期五7.4布尔代数的性质(3)等幂律a∨a=a,a∧a=a(4)吸收律a∨(a∧b)=a,a∧(a∨b)=a(5)分配律a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)(6)同一律a∨0=a,a∧1=a(7)零一律a∧0=0,a∨1=1(8)互补律a∨a’=1,a∧a’=0(9)对合律(a’)’=a(10)德.摩根律(a∨b)’=a’∧b’,(a∧b)’=a’∨b’2023/4/1155第55页，共69页，2023年，2月20日，星期五7.4布尔代数的性质证明:(10)(a∨b)∨(a’∧b’)=(a∨b∨a’)∧(a∨b∨b’)=(b∨(a∨a’))∧(a∨(b∨b’))=(b∨1)∧(a∨1)=1∧1=1

(a∨b)∧(a’∧b’)=(a∧a’∧b’)∨(b∧a’∧b’)=((a∧a’)∧b’)∨((b∧b’)∧a’)=(0∧b’)∨(0∧a’)=0∨0=0所以有(a∨b)’=a’∧b’。同理可证(a∧b)’=a’∨b’。2023/4/1156第56页，共69页，2023年，2月20日，星期五7.4布尔代数『定理』设<B,∧,∨>是一个代数系统，∧和∨是B上的二元运算，如果对任意a,b,c∈B

均满足以下四条性质，则称

<B,∧,∨>是一个布尔代数。(1)交换律a∨b=b∨a,a∧b=b∧a(2)分配律a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)2023/4/1157第57页，共69页，2023年，2月20日，星期五7.4布尔代数(3)同一律B中存在两个元素1和0，并且对B中任意元素a,满足

a∧1=a,a∨0=a(4)互补律对B中每个元素a都存在唯一元素a’∈B，满足

a∧a’=0,a∨a’=1

2023/4/1158第58页，共69页，2023年，2月20日，星期五7.4有限布尔代数的原子表示本小节研究有限布尔代数的一个重要性质，就是任何有限布尔代数<B,∧,∨,’>都同构于某有限集合S的幂代数<(S),∩,∪,>,这说明有限布尔代数有以下结构特征：(1)任何有限布尔代数，其载体元素个数是2的幂次。(2)对每个正整数n,都存在具有2n个元素的布尔格。(3)对于元素个数相同的布尔代数都是同构的。2023/4/1159第59页，共69页，2023年，2月20日，星期五7.4有限布尔代数的原子表示覆盖：设a,b是一个格中的两个元素，如果b≤a且b≠a,即b<a,并且在此格中再没有别的元素c,使得b<c和c<a,则称元素a覆盖元素b。原子：设<A,≤>是一个格，且具有全下界0,如果有元素a∈A,a盖住0，则称元素a为原子。2023/4/1160第60页，共69页，2023年，2月20日，星期五7.4有限布尔代数的原子表示『定理』设<B,∧,∨,’>是一个布尔代数，a和b是该布尔代数的两个原子，且有a≠b,则a∧b=0。证明：(