离散数学格与布尔代数市公开课一等奖省赛课获奖课件

第11章格与布尔代数离散数学中国地质大学本科生课程第1页本章内容11.1 格定义与性质11.2 分配格、有补格与布尔代数

本章总结

作业第2页11.1格定义与性质定义11.1设<S,≤>是偏序集，假如

x,y∈S，{x,y}都有最小上界和最大下界，则称S关于偏序≤作成一个格(lattice)。说明：因为最小上界和最大下界唯一性，能够把求{x,y}最小上界和最大下界看成x与y二元运算∨和∧。

x∨y：表示x与y最小上界

x∧y：表示x和y最大下界。

本章出现∨和∧符号只代表格中运算，而不再有其它含义。第3页格实例例11.1设n是正整数，Sn是n正因子集合。D为整除关系，则偏序集<Sn,D>组成格。

x,y∈Sn， x∨y是lcm(x,y)，即x与y最小公倍数。 x∧y是gcd(x,y)，即x与y最大条约数。 下列图给出了格<S8,D>，<S6,D>和<S30,D>。第4页例11.2例11.2判断以下偏序集是否组成格,并说明理由。 (1)<P(B),

>，其中P(B)是集合B幂集。 (2)<Z,≤>，其中Z是整数集,≤为小于或等于关系。 (3)偏序集哈斯图分别在下列图给出。第5页例11.2解答(1)是格。

x,y∈P(B)，x∨y就是x∪y，x∧y就是x∩y。 因为∪和∩运算在P(B)上是封闭，所以x∪y，x∩y∈P(B)。 称<P(B),

>,为B幂集格。(2)是格。

x,y∈Z,x∨y＝max(x,y)，x∧y＝min(x,y)，它们都是整数。(3)都不是格。 (a)中{a,b}没有最大下界。 (b)中{b,d}有两个上界c和e,但没有最小上界。 (c)中{b,c}有三个上界d,e,f,但没有最小上界。 (d)中{a,g}没有最大下界。第6页例11.3例11.3设G是群，L(G)是G全部子群集合。即 L(G)＝{H|H≤G} 对任意H1,H2∈L(G)，H1∩H2也是G子群，而<H1∪H2>是由H1∪H2生成子群（即包含着H1∪H2最小子群）。 在L(G)上定义包含关系

，则L(G)关于包含关系组成一个格，称为G子群格。 易见在L(G)中，H1∧H2就是H1∩H2，H1∨H2就是<H1∪H2>。第7页对偶原理定义11.2设f是含有格中元素以及符号＝、≤、≥、∨和∧命题。令f*是将f中≤替换成≥，≥替换成≤，∨替换成∧，∧替换成∨所得到命题。称f*为f对偶命题。比如 在格中令f是(a∨b)∧c≤c，则f*是(a∧b)∨c≥c。格对偶原理设f是含有格中元素以及符号＝、≤、≥、∨和∧命题。若f对一切格为真，则f对偶命题f*也对一切格为真。比如

对一切格L都有

a,b∈L，a∧b≤a (因为a和b交是a一个下界) 那么对一切格L都有

a,b∈L，a∨b≥a说明 许多格性质都是互为对偶命题。 有了格对偶原理，在证实格性质时，

只须证实其中一个命题即可。第8页格运算性质定理11.1设<L,≤>是格，则运算∨和∧适合交换律、结合律、幂等律和吸收律，即 (1)交换律

a,b∈L有 a∨b＝b∨a a∧b＝b∧a (2)结合律

a,b,c∈L有 (a∨b)∨c＝a∨(b∨c) (a∧b)∧c＝a∧(b∧c) (3)幂等律

a∈L有 a∨a＝a a∧a＝a (4)吸收律

a,b∈L有 a∨(a∧b)＝a a∧(a∨b)＝a第9页定理11.1(1)a∨b和b∨a分别是{a,b}和{b,a}最小上界。 因为{a,b}＝{b,a}，所以a∨b＝b∨a。 由对偶原理，a∧b＝b∧a得证。(2)由最小上界定义有 (a∨b)∨c≥a∨b≥a (13.1) (a∨b)∨c≥a∨b≥b (13.2) (a∨b)∨c≥c (13.3) 由式13.2和13.3有 (a∨b)∨c≥b∨c (13.4) 再由式13.1和13.4有 (a∨b)∨c≥a∨(b∨c) 同理可证 (a∨b)∨c≤a∨(b∨c) 依据偏序关系反对称性有 (a∨b)∨c＝a∨(b∨c) 由对偶原理，(a∧b)∧c＝a∧(b∧c)得证。第10页定理11.1(3)显然a≤a∨a, 又由a≤a可得 a∨a≤a。 依据反对称性有 a∨a＝a， 由对偶原理，a∧a＝a得证。(4)显然 a∨(a∧b)≥a (13.5) 又由a≤a，a∧b≤a可得 a∨(a∧b)≤a (13.6) 由式13.5和13.6可得

a∨(a∧b)＝a， 依据对偶原理，a∧(a∨b)＝a得证。第11页定理11.2定理11.2设<S,*,

>是含有两个二元运算代数系统，若对于*和

运算适合交换律、结合律、吸收律，则能够适当定义S中偏序≤，使得<S,≤>组成一个格，且a,b∈S有a∧b＝a*b，a∨b＝a

b。思绪

(1)证实在S中*和运算都适合幂等律。 (2)在S上定义二元关系R，并证实R为偏序关系。 (3)证实<S,≤>组成格。说明 经过要求运算及其基本性质能够给出格定义。第12页定理11.2a∈S，由吸收律得(1)证实在S中*和运算都适合幂等律。a*a＝a*(a

(a*a))＝a同理有a

a＝a。(2)在S上定义二元关系R，a,b∈S有<a,b>∈Rab＝b下面证实R在S上偏序。依据幂等律，a∈S都有a

a＝a，即<a,a>∈R，所以R在S上是自反。

a,b∈S有aRb且bRa

a

b＝b且b

a＝aa＝ba＝ab＝b(因为ab=ba)所以R在S上是反对称。第13页定理11.2a,b,c∈S有 aRb且bRc ab＝b且bc＝c ac＝a(bc) ac＝(ab)c ac＝bc＝c aRc 这就证实了R在S上是传递。 总而言之，R为S上偏序。 以下把R记作≤。第14页定理11.2(3)证实<S，≤>组成格。即证实a∨b＝a

b，a∧b＝a*b。a,b∈S有a(ab)＝(aa)b＝abb(ab)＝a(bb)＝ab依据≤定义有a≤ab和b≤ab，所以ab是{a,b}上界。假设c为{a,b}上界，则有ac＝c和bc＝c，从而有(ab)c＝a(bc)＝ac＝c这就证实了ab≤c，所以ab是{a,b}最小上界，即a∨b＝ab为证a*b是{a,b}最大下界，先证首先由ab＝b可知a*b＝a*(ab)＝a反之由a*b＝a可知ab＝(a*b)b＝b(b*a)＝b再由式(13.7)和≤定义有a≤ba*b＝a，依照前边证实,类似地可证a*b是{a,b}最大下界，即a∧b＝a*b。ab＝ba*b＝a (13.7)第15页格等价定义依据定理11.2，能够给出格另一个等价定义。定义11.3设<S,*,

>是代数系统，*和

是二元运算，假如*和

满足交换律，结合律和吸收律，则<S,*,

>组成一个格(lattice)。说明 格中幂等律能够由吸收律推出。 以后我们不再区分是偏序集定义格，

还是代数系统定义格，而统称为格L。第16页格性质定理11.3

设L是格，则

a,b∈L有 a≤b

a∧b＝a

a∨b＝b证实

先证a≤b

a∧b＝a 由a≤a和a≤b可知，a是{a,b}下界， 故a≤a∧b。显然又有a∧b≤a。 由反对称性得a∧b＝a。

再证a∧b＝a

a∨b＝b。 依据吸收律有b＝b∨(b∧a) 由a∧b＝a得b＝b∨a,即a∨b＝b。

最终证a∨b＝b

a≤b。 由a≤a∨b得a≤a∨b＝b。第17页格性质定理11.4设L是格，

a,b,c,d∈L，若a≤b且c≤d，则 a∧c≤b∧d， a∨c≤b∨d证实 a∧c≤a≤b a∧c≤c≤d 所以，a∧c≤b∧d。 同理可证a∨c≤b∨d。第18页例11.5

例11.5设L是格，证实

a,b,c∈L有 a∨(b∧c)≤(a∨b)∧(a∨c)证实 由a≤a，b∧c≤b得 a∨(b∧c)≤a∨b 由a≤a，b∧c≤c得 a∨(b∧c)≤a∨c 从而得到a∨(b∧c)≤(a∨b)∧(a∨c)说明 在格中分配不等式成立。 普通说来，格中∨和∧运算并不是满足分配律。第19页本节小结偏序集组成格条件：任意二元子集都有最大下界和最小上界。

格实例：正整数因子格，幂集格，子群格。格性质：对偶原理，格中算律（交换、结合、幂等、吸收），保序性，分配不等式。

格作为代数系统定义。格证实方法第20页子格定义11.4设<L,∧,∨>是格，S是L非空子集，若S关于L中运算∧和∨仍组成格，则称S是L子格。例11.6设格L如右图所表示。令S1＝{a,e,f,g}S2＝{a,b,e,g}则S1不是L子格，S2是L子格。因为对于e和f,有e∧f＝c，但c

S1。第21页11.2分配格、有补格与布尔代数普通说来，格中运算∨对∧满足分配不等式， 即

a,b,c∈L，有 a∨(b∧c)≤(a∨b)∧(a∨c) 不过不一定满足分配律。满足分配律格称为分配格。定义11.5设<L,∧,∨>是格，若

a,b,c∈L，有 a∧(b∨c)＝(a∧b)∨(a∧c) a∨(b∧c)＝(a∨b)∧(a∨c) 则称L为分配格。说明 上面两个等式互为对偶式。 在证实L为分配格时，只须证实其中一个等式即可。第22页例11.7L1和L2是分配格，L3和L4不是分配格。在L3中， b∧(c∨d)＝b∧e＝b(b∧c)∨(b∧d)＝a∨a＝a在L4中, c∨(b∧d)＝c∨a＝c(c∨b)∧(c∨d)＝e∧d＝d钻石格五角格第23页分配格判别定理11.5设L是格，则L是分配格当且仅当L中不含有与钻石格或五角格同构子格。证实 略。推论 (1)小于五元格都是分配格。 (2)任何一条链都是分配格。第24页例11.8说明下列图中格是否为分配格，为何？L1,L2和L3都不是分配格。{a,b,c,d,e}是L1子格，而且同构于钻石格。{a,b,c,e,f}是L2子格，而且同构于五角格。{a,c,b,e,f}是L3子格，也同构于钻石格。

第25页格全下界和全上界定义11.6设L是格， 若存在a∈L使得

x∈L有a≤x，则称a为L全下界； 若存在b∈L使得

x∈L有x≤b，则称b为L全上界。命题 格L若存在全下界或全上界，一定是唯一。证实 以全下界为例，假若a1和a2都是格L全下界, 则有a1≤a2和a2≤a1。 依据偏序关系反对称性必有a1＝a2。记法 将格L全下界记为0，全上界记为1。第26页有界格定义11.7设L是格，若L存在全下界和全上界，则称L为有界格，并将L记为<L,∧,∨,0,1>。说明 有限格L一定是有界格。举例设L是n元格，且L＝{a1,a2,…,an}，那么a1∧a2∧…∧an是L全下界，而a1∨a2∨…∨an是L全上界。所以L是有界格。对于无限格L来说，有是有界格，有不是有界格。如集合B幂集格<P(B),∩,∪>，不论B是有穷集还是无穷集，它都是有界格。它全下界是空集，全上界是B。整数集Z关于通常数小于或等于关系组成格不是有界格，因为不存在最小和最大整数。第27页有界格性质定理（补充）设<L,∧,∨,0,1>是有界格，则

a∈L有 a∧0＝0 a∨0＝a a∧1＝a a∨1＝1证实 由a∧0≤0和0≤a∧0可知a∧0＝0。说明 在有界格中， 全下界0是关于∧运算零元，∨运算单位元。 全上界1是关于∨运算零元，∧运算单位元。对偶原理对于包括到有界格命题，假如其中含有全下界0或全上界1，在求该命题对偶命题时，必须将0替换成1，而将1替换成0。比如 a∧0＝0和a∨1＝1互为对偶命题， a∨0＝a和a∧1＝a互为对偶命题。第28页有界格中补元定义11.8设<L,∧,∨,0,1>是有界格，a∈L， 若存在b∈L使得

a∧b＝0和a∨b＝1 成立，则称b是a补元。说明 若b是a补元，那么a也是b补元。 换句话说，a和b互为补元。第29页例11.9考虑下列图中四个格。L1中a与c互为补元，其中a为全下界，c为全上界，b没有补元。L2中a与d互为补元，其中a为全下界，d为全上界，b与c也互为补元。L3中a与e互为补元，其中a为全下界，e为全上界，b补元是c和d，c补元是b和d，d补元是b和c。b,c,d每个元素都有两个补元。L4中a与e互为补元。其中a为全下界。e为全上界。b补元是c和d，c补元是b，d补元是b。第30页有界格中补元说明在任何有界格中，全下界0与全上界1互补。对于其它元素，可能存在补元，也可能不存在补元。假如存在，可能是唯一，也可能是多个补元。对于有界分配格，假如它元素存在补元，一定是唯一。第31页有界分配格中补元唯一性定理11.6设<L,∧,∨,0,1>是有界分配格。 若a∈L，且对于a存在补元b，则b是a唯一补元。证实 假设c∈L也是a补元，则有 a∨c＝1，a∧c＝0 又知b是a补元，故 a∨b＝1，a∧b＝0 从而得到 a∨c＝a∨b，a∧c＝a∧b 因为L是分配格，依据定理13.7，b＝c。第32页有补格定义定义11.9设<L,∧,∨,0,1>是有界格，若L中全部元素都有补元存在，则称L为有补格。L2,L3和L4是有补格，L1不是有补格。L2和L3是有补格，L1不是有补格。第33页本节小结假如格中一个运算对另一个运算是可分配，称这个格是分配格。

分配格两种判别法： 不存在与钻石格或五角格同构子格； 对于任意元素a,b,c,有a∧b＝a∧c且a∨b＝a∨c

b＝c。

有界格定义及其实例。

格中元素补元及其性质（分配格中补元唯一性）。

有补格定义。第34页布尔代数定义11.10假如一个格是有补分配格，则称它为布尔格或布尔代数。说明 在布尔代数中，每个元素都存在着唯一补元。 能够把求补元运算看作是布尔代数中一元运算。 能够把一个布尔代数标识为<B,∧,∨,＇,0,1>，

＇为求补运算,

a∈B，a＇是a补元。第35页例11.10例11.10

设S110＝{1,2,5,10,11,22,55,110}是110正因子集合。令gcd,lcm分别表示求最大条约数和最小公倍数运算。问<S110,gcd,lcm>是否组成布尔代数？为何？解答

证实<S110,gcd,lcm>组成格。轻易验证

x,y,z∈S110，有gcd(x,y)∈S110 lcm(x,y)∈S110gcd(x,y)＝gcd(y,x)lcm(x,y)＝lcm(y,x)gcd(gcd(x,y),z)＝gcd(x,gcd(y,z))lcm(lcm(x,y),z)＝lcm(x,lcm(y,z))gcd(x,lcm(x,y))＝xlcm(x,gcd(x,y))＝x二元运算交换律结合律吸收律第36页例11.10证实<S110,gcd,lcm>是分配格。 易验证

x,y,z∈S110有 gcd(x,lcm(y,z))＝lcm(gcd(x,y),gcd(x,z))证实<S110,gcd,lcm>是有补格。 1为S110中全下界 110为S110中全上界 1和110互为补元，2和55互为补元， 5和22互为补元，10和11互为补元。总而言之，<S110,gcd,lcm>为布尔代数。第37页例11.10（2）例11.10（2）设B为任意集合,证实B幂集格<P(B),∩,∪,～,

,B>组成布尔代数，称为集合代数。证实 P(B)关于∩和∪组成格，因为 ∩和∪运算满足交换律、结合律和吸收律。 因为∩和∪相互可分配，所以P(B)是分配格， 且全下界是空集

,全上界是B。 依据绝对补定义，取全集为B，

x∈P(B)，～x是x补元。 从而证实P(B)是有补分配格，即布尔代数。第38页布尔代数性质定理11.7设<B,∧,∨,′,0,1>是布尔代数，则(1)

a∈B，(a＇)＇＝a(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇说明 (1)称为双重否定律。 (2)称为德摩根律。 命题代数与集合代数双重否定律与德摩根律实际上

是这个定理特例。 能够证实德摩根律对有限个元素也是正确。证实 (1)(a′)′是a′补元，a也是a′补元。 由补元唯一性得(a′)′＝a。第39页定理11.7(2)证实(2)

a,b∈B，(a∧b)＇＝a＇∨b＇,(a∨b)＇＝a＇∧b＇ (a∧b)∨(a＇∨b＇) ＝(a∨a＇∨b＇)∧(b∨a＇∨b＇) ＝(1∨b＇)∧(a＇∨1) ＝1∧1 ＝1

(a∧b)∧(a＇∨b＇) ＝(a∧b∧a＇)∨(a∧b∧b＇) ＝(0∧b)∨(a∧0) ＝0∨0＝0 所以a＇∨b＇是a∧b补元，依据补元唯一性有 (a∧b)＇＝a＇∨b＇ 同理可证(a∨b)＇=a＇∧b＇。第40页布尔代数作为代数系统定义定义11.11设<B,*,

>是代数系统，*和

是二元运算。 若*和°运算满足： (1) 交换律，即

a,b∈B有 a*b＝b*a， a

b＝b

a (2) 分配律，即

a,b,c∈B有 a*(b

c)＝(a*b)

(a*c) a

(b*c)＝(a

b)*(a

c)

(3) 同一律，即存在0,1∈B，使得

a∈B有 a*1＝a， a

0＝a (4) 补元律，即

a∈B,存在a′∈B，使得 a*a′＝0， a

a′＝1则称<B,*,

>是一个布尔代数。

第41页关于布尔代数定义说明所谓同一律就是指运算含有单位元性质，这里1是*运算单位元，0是运算

单位元。能够证实1和0分别也是

和*运算零元。

a∈B有 a1 ＝(a1)*1 （同一律） ＝1*(a1) （交换律） ＝(a

a′)*(a

1) （补元律） ＝a(a′*1) （分配律） ＝a

a′ （同一律） ＝1（补元律）同理可证a*0＝0。第42页关于布尔代数定义说明为证实以上定义<B,*,°>是布尔代数，只需证实它是一个格，即证实*和°运算满足结合律和吸收律。证实吸收律，

a,b∈B有

a(a*b) ＝(a*1)(a*b) （同一律） ＝a*(1b) （分配律） ＝a*1 （1是运算零元) ＝a （同一律）同理有a*(ab)＝a。第43页关于布尔代数定义说明为证结合律，先证以下命题：

a,b,c∈B，ab＝ac且ab＝acb＝c由ab＝ac且ab＝ac可得 (ab)*(ab)＝(ac)*(ac)由分配律和交换律得 (a*a)b＝(a*a)c由补元律得 0b＝0c由同一律和交换律得 b＝c第44页关于布尔代数定义说明使用这个命题，为证实(a*b)*c＝a*(b*c)，只需证实以下两个等式：(1)a((a*b)*c)＝a(a*(b*c))(2)a((a*b)*c)＝a(a*(b*c))先证实第一个等式，由吸收律有 a(a*(b*c))＝a a((a*b)*c) ＝(a(a*b))*(ac) (分配律) ＝a*(ac) (吸收律) ＝a所以(1)式成立。第45页关于布尔代数定义说明下面证实(2)式：a((a*b)*c)＝a(a*(b*c))

a(a*(b*c)) ＝(aa)*(a(b*c)) (分配律) ＝1*(a(b*c)) (交换律,补元律) ＝a(b*c) (交换律,同一律)

a((a*b)*c) ＝(a(a*b))*(ac)(分配律) ＝((aa)*(ab))*(ac) (分配律) ＝(1*(ab))*(ac) (交换律,补元律) ＝(ab)*(ac)(交换律,同一律) ＝a(b*c) (分配律)所以（2）式成立。第46页有限布尔代数结构定义11.12设L是格，0∈L，a∈L，若

b∈L有 0＜b≤a

b＝a 则称a是L中原子。考虑右图中几个格。L1原子是a。L2原子是a,b,c。L3原子是a和b。若L是正整数n全体正因子关于整除关系组成格，则L原子恰为n全体质因子。若L是集合B幂集合，则L原子就是由B中元素组成单元集。第47页有限布尔代数表示定理定理11.8(有限布尔代数表示定理)设B是有限布尔代数，A是B全体原子组成集合，则B同构于A幂集代数P(A)。证实 任取x∈B，令T(x)＝{a|a∈B,a是原子且a≤x} 则T(x)A，定义函数 ：B→P(A)，

(x)＝T(x)，

x∈B 下面证实

是B到P(A)同构映射。 任取x,y∈B，b有 b∈T(x∧y)

b∈A且b≤x∧y (b∈A且b≤x)且(b∈A且b≤y) b∈T(x)且b∈T(y) b∈T(x)∩T(y) 从而有T(x∧y)＝T(x)∩T(y)， 即

x,y

B有

(x∧y)＝

(x)∩

(y)。第48页定理11.8证实任取x,y∈B，设 x＝a1∨a2∨…∨an， y＝b1∨b2∨…∨bm是x,y原子表示，则 x∨y＝a1∨a2∨…∨an∨b1∨b2∨…∨bm由引理2可知 T(x∨y)＝{a1,a2,…,an,b1,b2,…,bm}又因为 T(x)＝{a1,a2,…,an}， T(y)＝{b1,b2,…,bm}所以 T(x∨y)＝T(x)∪T(y)即

(x∨y)＝

(x)∪

(y)第49页定理11.8证实任取x∈B，存在x

∈B使得 x∨x＝1，x∧x＝0所以有

(x)∪

(x

)＝

(x∨x

)＝

(1)＝A

(x)∩

(x

)＝

(x∧x

)＝

(0)＝

而和A分别为P(A)全下界和全上界，所以

(x

)是

(x)在P(A)中补元，即

(x

)＝〜

(x)总而言之，

是B到P(A)同态映射。第50页定理11.8证实下面证实

为双射。假设

(x)＝

(y)，则有 T(x)＝T(y)＝{a1,a2,…,an}由引理2可知x＝a1∨a2∨…∨an＝y于是

为单射。任取{b1,b2,…,bm}∈P(A)，令x＝b1∨b2∨…∨bm，则

(x)＝T(x)＝{b1,b2,…,bm}于是

为满射。定理得证。第51页例子考虑110正因子集合S110关于gcd,lcm运算组成布尔代数。它原子是2、5和11，所以原子集合A＝{2,5,11}。幂集P(A)＝{

,{2},{5},{11},{2,5},{