離散數(shù)學(xué)第六章第二節(jié)

1第6-2講分配格和有補(bǔ)格1.分配格2.有界格3.有補(bǔ)格4.有補(bǔ)分配格5.

課堂練習(xí)6.第6-2講作業(yè)21、分配格(1)

格中任意三個(gè)元素a,b,c存在分配不等式:a(bc)

(a

b)(ac)a(bc)

(a

b)(ac)是否有成立分配等式的格呢?來(lái)看幾個(gè)簡(jiǎn)單的例子：

右圖所示三個(gè)偏序集都是格,它們都滿足分配不等式，而且(1)和(2)還能使分配等式成立。(3)的情況就有些不同。例如在(1)中：a(bc)=ab=b;(a

b)(ac)=bc=b

在(3)中：a(bc)=aa=a;(a

b)(ac)=bc=a

但b(dc)=ba=b;(b

d)(bc)=ee=e31、分配格(2)定理1如果格中運(yùn)算

對(duì)運(yùn)算可分配，則運(yùn)算

對(duì)運(yùn)算可分配。反之亦然。定義1設(shè)<A,,>是由格<A,

>誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意a,b,cA，滿足

a(bc)=(a

b)(ac)a(bc)=(a

b)(ac)則稱(chēng)<A,

>是分配格。證：設(shè)a,b,c是格中任意元素，如果

a(bc)=(a

b)(ac)

則(a

b)(ac)=((a

b)a)((a

b)c)=a((a

b)c)=a((ac)(bc))=(a(ac))(bc)=a(bc)類(lèi)似可證

a(bc)=(a

b)(ac)a(bc)=(a

b)(ac)41、分配格(3)例1判斷下列各圖是否為分配格？解：(1)、(4)是分配格。(2)、(3)不是分配格。在(2)中，

b(cd)=b

e=b,(b

c)(bd)=aa=a在(3)中，

d(bc)=b

e=b,(d

b)(dc)=ac=c51、分配格(4)定理2鏈?zhǔn)欠峙涓瘛?2)ba且ca。這時(shí)必有bca(上界)。進(jìn)而有

a(bc)=bc(格的性質(zhì)8)另一方面，由ba且ca可得：(ab)(ac)=bc

所以，

a(bc)=(ab)(ac)

證：設(shè)<A,

>是鏈，則<A,

>是格。對(duì)任意a,b,cA，可分兩種情況討論：(1)ab或ac。這時(shí)，不論bc還是cb,應(yīng)有

a(bc)=a和(a

b)(ac)=a所以，a(bc)=(a

b)(ac)61、分配格(5)定理3設(shè)<A,

>是分配格，則對(duì)任意a,b,cA，如果

a

b=a

c且ab=ac，則b=c。證：b=b(ba)

(吸收律)=b(ab)(交換律)

=b(ac)（已知a

b=a

c）

=(b

a)(bc)(結(jié)合律)=(a

c)(bc)（交換律，已知ab=ac）

=(a

b)c=(ac)c=c(ca)=c72、有界格(1)

格的全下界常記為0，全上界常記為1。定義2設(shè)<A,

>是格，如果存在元素aA，對(duì)任意xA，都有ax(xa)，則稱(chēng)a為格<A,

>的全下界(全上界)。定理4格的全下界(全上界)如果存在必唯一。

證：假設(shè)格<A,

>有兩個(gè)全下界a和b，a,bA。那么按全下界的定義，應(yīng)有ab和ba同時(shí)成立，從而a=b。

例如，設(shè)S是有限集合，那么格<S,>是有界格，其全下界是

，全上界是S。定義3具有全下界和全上界的格稱(chēng)為有界格。82、有界格(2)

證：因<A,

>是有界格，對(duì)任意aA，應(yīng)有0a1，由此式及格的性質(zhì)8即可得上述四式。定理5設(shè)<A,

>是有界格，則對(duì)任意aA，必有

a1=1，a1=a；a0=a，a0=0。定義4設(shè)<A,

>是有界格，若對(duì)任意aA，存在bA，使ab=1，ab=0，則稱(chēng)b是a的補(bǔ)元。

例如，左圖所示有界格中，d和c、d和e、a和e、0和1互為補(bǔ)元，即a、c、d、e、0、1都有補(bǔ)元。但b沒(méi)有補(bǔ)元。93、有補(bǔ)格

證：設(shè)a有補(bǔ)元b、c，則有

ab=1，ab=0；ac=1，ac=0。那么，ab=ac，ab=ac所以，b=c（定理3）。定義5若有界格中，每個(gè)元素至少有一個(gè)補(bǔ)元，則稱(chēng)為有補(bǔ)格。定理6在有界分配格中，若某元素有補(bǔ)元，則必唯一。

104、有補(bǔ)分配格定義6若一個(gè)格既是有補(bǔ)格，又是分配格，則稱(chēng)為有補(bǔ)分配格，也叫布爾格。將有補(bǔ)分配格中元素a的補(bǔ)元記作a’。115、課堂練習(xí)練習(xí)1指出下圖所示有界格中各元素的補(bǔ)元。解：（1）b、c是a的補(bǔ)元；a、c是b的補(bǔ)元；

a、b是c的補(bǔ)元；0、1互為補(bǔ)元。（2）a、b的補(bǔ)元是c；c的補(bǔ)元是a、b；0、1互為補(bǔ)元。12第6-2講作業(yè)P2492P2521，6人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書(shū)，