離散數(shù)學(xué)及其應(yīng)用-第2版 課件 第12章 格和布爾代數(shù)

第12章格和布爾代數(shù)1離散數(shù)學(xué)及其應(yīng)用12.1格12.1.1格的基本概念定義12.1.1設(shè)<L，≤>是一個偏序集，如果L中的任何兩個元素構(gòu)成的子集都有上確界和下確界，則稱<L，≤>為格（lattice）。

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

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

，

>，其中Z表示整數(shù)集，

表示Z上的小于等于關(guān)系，(3)偏序集<Sn,D>,其中Sn是n的所有因子的集合，D是整除關(guān)系。解（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的最小公倍數(shù)；x

y＝gcd（x,y）,即x與y的最大公約數(shù).所以偏序集<Sn,D>是格。3例題判斷下圖中哈斯圖表示的偏序集是否構(gòu)成格？說明理由。

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

（1），（2），（3）是格，每個圖中的任何兩個元素的集合都存在上確界和下確界。（4），（5）不是格，（4）中的{a,b}有兩個下界元素，但是沒有下確界，（5）中的{a,b}沒有下界元素，沒有下確界。4

格的對偶原理定義12.2.1設(shè)P是含有格中元素及符號=，≤，≥，

和

的命題。將P中符號

換成

，

換成

，≤換成≥，≥換成≤后得到公式P*，稱P*為P的對偶命題。例如P=a

（b

c）的對偶命題為P*=a

（b

c），而且P和P*互為對偶命題。格的對偶原理設(shè)P是含有格中元素及符號=，≤，≥，

和

的命題，若P對一切格為真，則P的對偶命題P*對一切格也為真。

例如，如果對所有L，命題“

a,b

L,a

b≤a”成立，根據(jù)對偶原理，對所有L，命題“

a,b

L,a

b≥a”也成立。5定理12.1.1設(shè)<L,≤>為格，那么對L中任意元素a,b,c

有

（1）冪等律：a

a=a

，a

a＝a

（2）交換律：a

b=b

a

，a

b=b

a

（3）結(jié)合律：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由偏序關(guān)系“≤“的反對稱性，a

（b

c）=（a

b）

c。

（4）顯然，a

（a

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

，a≤a

b故而a≤a

（a

b）

于是有a

(a

b)=a根據(jù)格的對偶原理，a

(a

b)=a也成立。7定理12.1.2設(shè)<L,

,

>是代數(shù)系統(tǒng)，

,

是二元運算，且滿足冪等律、結(jié)合律、交換律和吸收律，在L上定義一種關(guān)系“≤”為：對

a,b

L,a≤b

當(dāng)且僅當(dāng)a

b=b,

則<L,≤>是格。

8子格定義12.1.3設(shè)<L,

,

>是代數(shù)系統(tǒng)，

,

是二元運算，如果

和

滿足結(jié)合律、交換律和吸收律，則<L,

,

>構(gòu)成格。定義12.1.4設(shè)<L,

,

>是格，S是L的非空子集，若S關(guān)于L

中的運算

,

仍構(gòu)成格，則稱S是L的子格。9例題例12.1.3 設(shè)格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設(shè)<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設(shè)<L，∨,∧>是格，則L是分配格的充分必要條件L中不含有與鉆石格或五角格同構(gòu)的子格。證明略。推論（1）小于5元的格都是分配格。任何一條鏈都是分配格。13說明下圖的格是否是分配格。解答：都不是14

定理12.1.4設(shè)<L，∨,∧>為分配格，那么對L中任意元素a，b，c，有

a∧b=a∧c并且a∨b=a∨c當(dāng)且僅當(dāng)b=c

證明

充分性是顯然的。

現(xiàn)證必要性。由于

（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設(shè)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設(shè)<L，∨,∧,0,1>為有界格，a

L，如果存在b

L，使得

a∨b=1和a∧b=0稱b為a的補元或補（complements）。應(yīng)當(dāng)注意補元的下列特點：補元是相互的，即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設(shè)<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互為補元。設(shè)a也是1的補元，那么a∧1=0,即a=0。因此1的補元僅為0。同樣可證0的補元僅為1。20定理12.1.6

21定理12.1.7

22定義12.1.9設(shè)<L，

，?>為格，如果對L中任意元素a，b，c，只要a≤c，就有a?(b?c)=(a?b)?c,則稱<L，

，?>為模格。

由定義可知，分配格一定是模格，但模格不一定是分配格。2312.2.1布爾代數(shù)定義12.2.1如果一個格是有補分配格，則稱它為布爾格或布爾代數(shù)（Boolean

algebra）。

布爾代數(shù)中的每一個元素都存在補元，所以還有一個一元運算----求補運算。通常用<B，

，?，ˉ，0，1>來表示布爾代數(shù)，其中ˉ為一元求補運算。24例題設(shè)A是任意集合，證明冪集格<P(A)，∪，∩，ˉ，

,A>（其中ˉ為一元求補集的運算）為布爾代數(shù)，稱為集合代數(shù)。證明

P(A)關(guān)于

和

構(gòu)成格，因為

和

運算滿足交換律、結(jié)合律和吸收律。由于

對

運算和是

對

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

,全上界是集合A。取全集為A。根據(jù)絕對補的定義，對任意x

P(A)，x的補元是A-x。因此P(A)是有補分配格，即是布爾代數(shù)。25布爾代數(shù)滿足的運算律對任意a,b,c

L，有26布爾代數(shù)滿足的運算律（續(xù)）27布爾代數(shù)

28布爾同態(tài)定義12.2.3：設(shè)f：A→B為布爾代數(shù)<A，

，?，ˉ，0，1>到布爾代數(shù)<B，

，?，ˉ，0，1>的同態(tài)映射，即對任何元素a，b，

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

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

（3）那么稱f為A到B的布爾同態(tài)。當(dāng)f是雙射時，稱布爾代數(shù)<A，

，?，ˉ，0，1>和<B，

，?，ˉ，0，1>同構(gòu)。

29布爾表達(dá)式與布爾函數(shù)定義12.2.4設(shè)<B，

，?，ˉ>為布爾代數(shù)，如下遞歸地定義B上布爾表達(dá)式（Boolean

expressions）：

（1）布爾常元(取值于B的常元)是一個布爾表達(dá)式。

（2）布爾變元(取值于B的變元)是一個布爾表達(dá)式。

（3）如果e1,e2為布爾表達(dá)式，那么

也是布爾表達(dá)式．

（4）只有有限次使用規(guī)則（l），（2）（3）生成的表達(dá)式才是布爾表達(dá)式。

為了省略括號，我們約定運算ˉ的優(yōu)先級高于運算

，?，并約定表達(dá)式最外層括號省略．30定義12.2.5含有n個不同變元x1,x2,…,xn

的布爾表達(dá)式稱為n元布爾表達(dá)式，記做f(x1,x2,…,xn)。

設(shè)<{0,a,b,1}，

，?，ˉ>為布爾代數(shù)，那么都是布爾表達(dá)式，分別稱為含有單個變元x1的布爾表達(dá)式、含有2個變元x1

、x2的布爾表達(dá)式和含有3個變元x1

、x2

、x3的布爾表達(dá)式。31布爾函數(shù)定義12.2.6設(shè)<B，

，?，ˉ>為布爾代數(shù)，Bn={(x1,x2,…,xn)|xi

{0,1},0

i

1},如果一個從Bn到B的函數(shù)f:Bn→B能夠用<B，

，?，ˉ>上的n元布爾表達(dá)式f(x1,x2,…,xn)來表示，稱函數(shù)f:Bn→B為n元布爾函數(shù)（Booleanl

functions）。設(shè)B={0,1}，變元x僅從B中取值，則稱該變元為布爾變元。

每個布爾表達(dá)式都表示一個布爾函數(shù)，布爾函數(shù)的值可以通過用0和1替換表達(dá)式中的變元得到。32例題計算由

表示的布爾函數(shù)。

解：表示的布爾函數(shù)的值可以由下表來表示。

33xyz000100100101011010011