离散数学及其应用-第2版 课件 第12章 格和布尔代数

第12章格和布尔代数1离散数学及其应用12.1格12.1.1格的基本概念定义12.1.1设<L，≤>是一个偏序集，如果L中的任何两个元素构成的子集都有上确界和下确界，则称<L，≤>为格（lattice）。

2(1)（2）例题判断下列偏序集是否是格？说明理由。（1）偏序集<P（A），

>，其中P（A）是集合A的幂集，（2）偏序集<Z

，

>，其中Z表示整数集，

表示Z上的小于等于关系，(3)偏序集<Sn,D>,其中Sn是n的所有因子的集合，D是整除关系。解（1）对于

X，Y

P(A)，有X

Y＝X∪Y,X

Y＝X∩Y由于

和

运算在P(A)上是封闭的，所以X∪Y和X∩Y

P(A)，偏序集<P（A），

>是格，称为A的幂集格。（2）对于

m，n

Z，有m

n＝max（m,n），m

n＝min（m,n），所以偏序集<Z

，

>是格。（3）对于

x，y

Sn，有x

y＝lcm（x,y），即x与y的最小公倍数；x

y＝gcd（x,y）,即x与y的最大公约数.所以偏序集<Sn,D>是格。3例题判断下图中哈斯图表示的偏序集是否构成格？说明理由。

（1）(2)(3)（4）(5)解

（1），（2），（3）是格，每个图中的任何两个元素的集合都存在上确界和下确界。（4），（5）不是格，（4）中的{a,b}有两个下界元素，但是没有下确界，（5）中的{a,b}没有下界元素，没有下确界。4

格的对偶原理定义12.2.1设P是含有格中元素及符号=，≤，≥，

和

的命题。将P中符号

换成

，

换成

，≤换成≥，≥换成≤后得到公式P*，称P*为P的对偶命题。例如P=a

（b

c）的对偶命题为P*=a

（b

c），而且P和P*互为对偶命题。格的对偶原理设P是含有格中元素及符号=，≤，≥，

和

的命题，若P对一切格为真，则P的对偶命题P*对一切格也为真。

例如，如果对所有L，命题“

a,b

L,a

b≤a”成立，根据对偶原理，对所有L，命题“

a,b

L,a

b≥a”也成立。5定理12.1.1设<L,≤>为格，那么对L中任意元素a,b,c

有

（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

(a

b)=a

，a

(a

b)=a

6证明证明（1）a

a是{a}的最小上界，所以a

a=a.由对偶原理a

a＝a也成立。（2）a

b是{a,b}的最小上界，b

a是{b,a}的最小上界，{a,b}={b,a},所以a

b=b

a．由对偶原理a

b=b

a也成立。

（3）两个公式互为对偶，所以只证a

（b

c）=（a

b）

c。由最大下界定义有（a

b）

c

≤a

b

≤a（a

b）

c

≤a

b

≤b（a

b）

c

≤c从而（a

b）

c

≤b

c,进而（a

b）

c

≤a

（b

c）。同理可证

a

（b

c）≤（a

b）

c由偏序关系“≤“的反对称性，a

（b

c）=（a

b）

c。

（4）显然，a

（a

b）≤a；另一方面，由于a≤a

，a≤a

b故而a≤a

（a

b）

于是有a

(a

b)=a根据格的对偶原理，a

(a

b)=a也成立。7定理12.1.2设<L,

,

>是代数系统，

,

是二元运算，且满足幂等律、结合律、交换律和吸收律，在L上定义一种关系“≤”为：对

a,b

L,a≤b

当且仅当a

b=b,

则<L,≤>是格。

8子格定义12.1.3设<L,

,

>是代数系统，

,

是二元运算，如果

和

满足结合律、交换律和吸收律，则<L,

,

>构成格。定义12.1.4设<L,

,

>是格，S是L的非空子集，若S关于L

中的运算

,

仍构成格，则称S是L的子格。9例题例12.1.3 设格L如图所示，S1={a,b,c,d}，S2={a,f,b}，S1和S2是否是L的子格？

解S1是L的子格，S2不是L的子格，因为对b和f，b

f=d,而d

S2。10分配格定义12.1.5设<L，∨,∧>是一个格，如果对任意a,b,c

L，都有a∧（b∨c）=（a∧b）∨（a∧c）a∨（b∧c）=（a∨b）∧（a∨c）即运算满足分配津，则称<L，∨,∧>为分配格（distributive

lattice）。例如，格<P(A),

,

>是分配格，P(A)是集合A的幂集，因为对任意X，Y,Z

P(A),有X

(Y

Z)=(X

Y)

(X

Z)X

(Y

Z)=(X

Y)

(X

Z)即集合的交并运算满足分配律。11例题说明下图的格是否是分配格。

（1）(2)（3）(4)解

图中(1)(2)都不是分配格,(3)(4)

都是分配格。12

定理12.1.3设<L，∨,∧>是格，则L是分配格的充分必要条件L中不含有与钻石格或五角格同构的子格。证明略。推论（1）小于5元的格都是分配格。任何一条链都是分配格。13说明下图的格是否是分配格。解答：都不是14

定理12.1.4设<L，∨,∧>为分配格，那么对L中任意元素a，b，c，有

a∧b=a∧c并且a∨b=a∨c当且仅当b=c

证明

充分性是显然的。

现证必要性。由于

（a∧b）∨c＝（a∧c）∨c=c

（因a∧b=a∧c）

（a∧b）∨c=（a∨c）∧（b∨c）

（分配律）=（a∨b）∧（b∨c）(因a∨c＝a∨b)=b∨（a∧c）

（分配律）

＝b∨（a∧b）

（因a∧b=a∧c）=b故b=c

。15有界格定义12.1.6设L是格，如果存在a

L，使得对于

x

L

有a≤x，则称a为格L的全下界，记为0；如果存在b

L，使得对于

x

L

有x≤b，则称b为格L的全上界，记为1。存在全上界和全下界的格，称为有界格（bounded

lattice），记为<L，

，˄，0，1>。例如，对任意集合A的幂集P(A),<P(A),

,

>是有界格，因为格<P(A),

,

>存在全上界1=A，全下界0=

。16补元定义12.1.7设<L，∨,∧,0,1>为有界格，a

L，如果存在b

L，使得

a∨b=1和a∧b=0称b为a的补元或补（complements）。应当注意补元的下列特点：补元是相互的，即b是a的补元，那么a也是b的补元。0和1互为补元。并非有界格中每个元素都有补元，而一个元素的补元也未必唯一。17例题指出下图中各个元素的补元。

（1）（2）（3）（4）解

图（1）中元素a和d互为补元，a是全上界，d是全下界，c，b，e都没有补元；（2）中元素a

和e互为补元，a是全上界，e是全下界，b的补元是c和d,c的补元是b和d,d的补元是a和c

；（3）中元素a

和e互为补元，a是全上界，e是全下界，b有补元c和d，而c,d的补元同为b；(4)中元素a和c互为补元，a是全上界，c是全下界，b没有补元。18

有补格定义12.1.8设<L，

，˄，0，1>为有界格，如果L中每个元素都有补元，称L为有补格（complemented

lettice）。例12.1.7判断下图的格是否是有补格？(1)(2)(3)(4)解

图(1)不是有补格，因为存在元素没有补元；(2)和(3)中每个元素都有补元，都是有补格;(4)不是有补格，多于两个元素的链都不是有补格。19定理12.1.5有补格<L,

，˄，0,1>中元素0，1的补元是唯一的。证明

已知0，1互为补元。设a也是1的补元，那么a∧1=0,即a=0。因此1的补元仅为0。同样可证0的补元仅为1。20定理12.1.6

21定理12.1.7

22定义12.1.9设<L，

，˄>为格，如果对L中任意元素a，b，c，只要a≤c，就有a˅(b˄c)=(a˅b)˄c,则称<L，

，˄>为模格。

由定义可知，分配格一定是模格，但模格不一定是分配格。2312.2.1布尔代数定义12.2.1如果一个格是有补分配格，则称它为布尔格或布尔代数（Boolean

algebra）。

布尔代数中的每一个元素都存在补元，所以还有一个一元运算----求补运算。通常用<B，

，˄，¯，0，1>来表示布尔代数，其中¯为一元求补运算。24例题设A是任意集合，证明幂集格<P(A)，∪，∩，¯，

,A>（其中¯为一元求补集的运算）为布尔代数，称为集合代数。证明

P(A)关于

和

构成格，因为

和

运算满足交换律、结合律和吸收律。由于

对

运算和是

对

运算都是可分配的，所以P(A)是分配格，且全下界是空集

,全上界是集合A。取全集为A。根据绝对补的定义，对任意x

P(A)，x的补元是A-x。因此P(A)是有补分配格，即是布尔代数。25布尔代数满足的运算律对任意a,b,c

L，有26布尔代数满足的运算律（续）27布尔代数

28布尔同态定义12.2.3：设f：A→B为布尔代数<A，

，˄，¯，0，1>到布尔代数<B，

，˄，¯，0，1>的同态映射，即对任何元素a，b，

（1）f（a∨b）=f（a）∨f（b）

（2）f（a∧b）＝f（a）∧f（b）

（3）那么称f为A到B的布尔同态。当f是双射时，称布尔代数<A，

，˄，¯，0，1>和<B，

，˄，¯，0，1>同构。

29布尔表达式与布尔函数定义12.2.4设<B，

，˄，¯>为布尔代数，如下递归地定义B上布尔表达式（Boolean

expressions）：

（1）布尔常元(取值于B的常元)是一个布尔表达式。

（2）布尔变元(取值于B的变元)是一个布尔表达式。

（3）如果e1,e2为布尔表达式，那么

也是布尔表达式．

（4）只有有限次使用规则（l），（2）（3）生成的表达式才是布尔表达式。

为了省略括号，我们约定运算¯的优先级高于运算

，˄，并约定表达式最外层括号省略．30定义12.2.5含有n个不同变元x1,x2,…,xn

的布尔表达式称为n元布尔表达式，记做f(x1,x2,…,xn)。

设<{0,a,b,1}，

，˄，¯>为布尔代数，那么都是布尔表达式，分别称为含有单个变元x1的布尔表达式、含有2个变元x1

、x2的布尔表达式和含有3个变元x1

、x2

、x3的布尔表达式。31布尔函数定义12.2.6设<B，

，˄，¯>为布尔代数，Bn={(x1,x2,…,xn)|xi

{0,1},0

i

1},如果一个从Bn到B的函数f:Bn→B能够用<B，

，˄，¯>上的n元布尔表达式f(x1,x2,…,xn)来表示，称函数f:Bn→B为n元布尔函数（Booleanl

functions）。设B={0,1}，变元x仅从B中取值，则称该变元为布尔变元。

每个布尔表达式都表示一个布尔函数，布尔函数的值可以通过用0和1替换表达式中的变元得到。32例题计算由

表示的布尔函数。

解：表示的布尔函数的值可以由下表来表示。

33xyz000100100101011010011