格的定義(共39張PPT)

格

的

定

義·格是任二元都(在其中)有g(shù)lb和lub的偏序集，具體說(shuō)：偏序集<S,≤稱為格，如果VaVb(a,b

∈S→glb{a,b}

∈S

△lub{a,b}

∈S).·

我們知道：glb或lub若存在必唯一，故glb:SxS→

S,lub:SxS→S是映射，從而定義格S中的兩個(gè)二元運(yùn)算，我們分別把它們記為a*b=glb{a,b}

和

a④b=lub{a,b}

并分別稱為的

a與b保交與保聯(lián).·

對(duì)有限偏序集常用它的Hasse

圖驗(yàn)證它是否組

成一個(gè)格，例如教本p215的圖7.1-1(a)

一(e)是

格，7.2c)不是格(后者左右肩兩點(diǎn)的glb不存

在).格

的

舉

例①每個(gè)線性序集，例如(R,≤)及其子集，都是格，glb{a,b}=min{a,b};lub{a,b}=max{a,b}.②集S的界集p(S)

和包含關(guān)系組成偏序集，對(duì)任意

A,B

∈p(S),glb{A,B}=A^B

∈p(S);lub{A,B}=AUB∈p(S).

因此，<p(S),C)是格.例如<p({a,b,c}),C>的Hasse圖在圖7.1-1(c)中畫(huà).③正董數(shù)集I

與蓋除關(guān)系組成偏序集，對(duì)任意a,b

∈I,,glb{a,b}=GCD(a,b)

∈I.;lub{a,b}=LCM(a,b)∈I.因此，(I,

|)是格.特別，對(duì)任意正

莖數(shù)n

∈I,

令S,記n的所有正因子的集，則<S,

|)是格.出·<S,≤)是格，a*b=min(a,b);a田b=max(a,b).·

一

般地，任何線性序集都是格，7.1#2

S={1,2,3,4,5},<S,≤)是格嗎?32p

57.1#3畫(huà)出格(S?

,

|)的Hasse圖72=2332;x=2i3j,i=0,1,2,3;j=0,1,2.Sr?={72,36,24,18,12,9,8,6,4,3,2,1}98格的對(duì)偶原理●

因

偏

序

≤

的

逆

關(guān)

系

≥

也

是

偏

序

；

故B=<S,≤)是格?

B'=<S,≥)是格；對(duì)任意AcB,lub(A)=glb'(A),glb(A)=lub'(A);

('記格B'中的對(duì)應(yīng)運(yùn)算)特別對(duì)任意a,b∈S,a*b=a田'b,a田b=a*'b.·

對(duì)偶原理：對(duì)于格<S,≤)中任何有效公式，把*與田；≤與≥互換后仍為有效公式

.格

的

基

本

公

式

及

其

證

明⑥

交換律：a*b=b*a;a

田b=b田a.

(其中a,b

∈S

為任意元素，下同)證

：

由

對(duì)

偶

原

理

只

須

證

其

中

一

個(gè)

即

可

，

例如

第

一

個(gè)a*b=glb{a,b}=glb{b,a}=b*a.⑦結(jié)合律：

(a*b)*c=a*(b*c);(a

田b)田c=(a

田b)

田c.證：w=(a*b)*c≤a*b和c?w≤a,b和c→w≤a和b*c

→w≤a*(b*c),即

(a*b)*c=w≤a*(b*c).同理可得

a*(b*c)≤(a*b)*c.⑧等界律：a*a=a;a④a=a.證：a≤a→a≤a*a,又按*定義有

a*a≤a.所以a*a=a.格

的

基

本

公

式

及

其

證

明

續(xù)⑨

吸收律：

a*(a+b)=a;a

田(a*b)=a.證：

a≤aAa≤a④b

→

a≤a*(a田b);

此外又有a*(a④b)≤a,故結(jié)論成立.⑩

重要公式：

a*b=a

?

a≤b

?

a+b=b.證

：

因a≤b

?

a*b=a

(1)的對(duì)偶為：a≥

b

?a④b=a,故只須證(1)即可.

事實(shí)上

a≤b

→a≤a*b.又a*b≤a,

得證a*b=a.顯然

a*b=a

→

a≤b,故(1)成立.格

的

基

本

公

式

及

其

證

明

續(xù)(11)a≤dAb≤c→a*b≤d*c.(可證其對(duì)偶為

a≥d△b≥c

→

a④b≥d田c)證：因a*b≤a≤d,a*b≤b≤c,故

a*b≤d*c.(12)

保序性：

b≤c

→

a*b≤a*c△a田b≤a④c.證：因恒有a≤a,故

當(dāng)b≤c時(shí)

令d=a

結(jié)論由(11)推出.(13)

分配不等式：

a

田(b*c)≤(a

田b)*(a田c)

(

還

有

對(duì)偶式)證：因b*c≤b;b*c≤c,

故由保序性推出：a

田(b*c)≤a

田b和a

田(b*c)≤a

田c,

故結(jié)論成立

.(14)

模不等式：a≤c

?

a田(b*c)≤(a

田b)*c.證

：a

田(b*c)≤(a

田b)*c→a≤a

田(b*c)≤(a

田b)*c≤c.

反

之a(chǎn)

≤c→a

田c=c,

故結(jié)論由(13)推出.7

.

1#8元素不多于3個(gè)的格全是鏈設(shè)(S,≤)是格.若

|S

|=1,它顯然是鏈(全序集);若

|S

|=2,不妨設(shè)

|S

|={a,b}且a≤b,則為二元鏈；若

|S

|=3,不妨設(shè)

|S

|={a,b,c}.今用反證法證S中任二元a,b

都可比較.設(shè)a,b

不可比較，則glb{a,b},lub{a,b}∈{a,b},由此得glb{a,b}=c=lub{a,b}.

進(jìn)一步又有c≤aAc≥a

→

c=a,矛

盾

.格

的

另

一

個(gè)

等

價(jià)

定

義·

有兩個(gè)二元運(yùn)算的代數(shù)(L,*,田)稱為一個(gè)格，如果*,田都滿足交換律，結(jié)合律和等霽律并且滿足吸收律：對(duì)L中任意元素a,b,c有(交換)

a*b=b*a;

a田b=b

田a;(結(jié)合)(a*b)*c=a*(b*c);

(a

田b)田c=a

田(b田c);(等界)

a*a=a;

a田a=a;(吸收)

a*(a④b)=a=a田(a*b);●

注

：

等

界

律

可

由

吸

收

律

推

出(a④a=a

田(a*(a

田b))=a),故

可

從

上

述

定

義

中

刪

去

.格

的

兩

個(gè)

定

義

等

價(jià)由格的前一個(gè)定義可定義兩個(gè)二元運(yùn)算：*,田，并

已證明*,田都滿足交換，結(jié)合和等界律并且滿足

吸收律(見(jiàn)表7.1-1),故它滿足格的后一定義.反之，由格的后一定義可證明L是其任二元的lub,glb都在L中的偏序集，從而滿足格的前一定義.在L中定義關(guān)系≤:a≤b?a*b=a,則等霽律：a*a=a

保證

自

反

律a≤a

;

a≤

b

b

≤a

?a*b=aAb*a=b→

(交換律)a

=b

;

a≤

bb

≤c

?a*b=aAb*c=b→

(傳遞律)a*c=(a*b)*c=a*(b*c)=a*b=a,

即a≤c,得證(L,≤)是偏序集.對(duì)任意a,b∈L,設(shè)

c是a,b的下界，則c*a=cAc*b=c→

c*a*b=c,即

c≤a*b;

又

a*b*b=a*b

→a*b≤b,類似有a*b≤a.

∴glu{a,b}=a*b∈L.同

理lub{a,b}=

a④b

∈L.

(注

a*b=a

?a田b=(a*b)④b=b

吸收律)子

格

與

格

的

直

接

積·

作

為

代

數(shù)

的

格(L,*,

田)的子代數(shù)稱為子格，換句

話說(shuō)，若HcL,

且H對(duì)*,田封閉，則<H,*,田)是L的子

格

.·

子

格H本身也是格，因交換律，結(jié)合律，吸收律在L中成立必在H中成立.·

設(shè)L',L"是格，則積代數(shù)：<L'×L",*,田},其中

<a,

b)*{c,d)=<a*'c,b*"'d〉;<a,

b}田(c,d)=<a'c,b

田'd),也是格，稱為格L'與L"的直接積.(L'xL"對(duì)*,田封閉由L',L"對(duì)*,田封閉推出；交換律，結(jié)合律，吸收律在L',L"中成立推出在L中也

成立.)·

<S,≤

的2元子格(只寫(xiě)載體):{e,d},{e,c},{e,b},{e,a},{b,a},{c,a},{d,a};·

S的3元子格：{e,d,a},{e,c,a},{e,b,a};·

S

的4元子格：{e,d,c,a},{e,d,b,a},{e,c,b,a}.求下圖表示的格<S,≤的所有真子格7.2#3格(L,≤)的

封

閉

區(qū)

間[a,b]

是

子

格封閉區(qū)間[a,b]定義為由a,b

界定的線性序子集：[a,b]={x

|x∈L△a≤x≤b},其中

a,b∈L.證：

[a,b]顯然是L的子集；x,y

∈[a,b]→

a≤x≤bAa≤y≤b

即a(b)為

{x,y}的下(上)界→a≤x*y≤x田y≤b

即x*y,x田y∈[a,b]

∴[a,b]

對(duì)*,田封閉，從而是L的一個(gè)子格.格

的

同

態(tài)·作為代數(shù)的格(L,*,田}的代數(shù)同態(tài)稱為格同態(tài)，具體講，f:<L,*,田)→(L',*’,田')稱為格同態(tài)，如

果對(duì)任何a,b∈L,有

f(a*b)=f(a)*'f(b),和f(a田b)=f(a)田'f(b).·格的同態(tài)象是陪域格L'的子格(見(jiàn)定理6.3-2)(習(xí)題7.2#6).·

(定理7.2-2)格同態(tài)f:<L,*,田；≤}→(L',*',田’,≤')是保序的：對(duì)任何

a,b∈L有

a≤b→f(a)≤'f(b).證：

a≤b

?

a*b=a→

f(a)=f(a*b)=f(a)*'f(b)?f(a)≤'f(b).·

任意格同構(gòu)的定義域格與陪域格的Hasse

圖除標(biāo)記外完全相同.·

(p220

例1)不計(jì)同構(gòu)差別只有2個(gè)4元格，如圖7.2-4所示；不計(jì)同構(gòu)差別只有5個(gè)5元格，如圖

7.2-5所示.格的同構(gòu)●

雙射的格同態(tài)稱為格同構(gòu)，分

配

格

的

定

義·其兩個(gè)運(yùn)算滿足分配律的格稱為分配格，具體

講，格(L,*,田)稱為分配格，如果對(duì)任何a,b∈L有a*(b田c)=(a*b)田(a*c),

(1)和

a田(b*c)=(a

田b)*(a

田c).

(2)·

由格的對(duì)偶原理，(1)成立當(dāng)且僅當(dāng)(2)成立，故

<L,*,田}為分配格當(dāng)且僅當(dāng)(1)和(2)之一成立即

可

.·

(7.3#1)用吸收律證

(1)→

(2).(a田b)*(a

田c)=((a

田b)*a)

田((a

田b)*c)

用(1)=a田((a*c)

田(b*c))用吸收律和(1)

=a田(b*c)

用

結(jié)

合

律

和

吸

收

律分

配

格

舉

例①

鏈(線性序集)是分配格，例如，<I,min,max,≤}(7.3#5)是分配格.證：設(shè)

a,b,c為鏈<S,≤>的任意3元.若

a=glb{a,b,c}

,則a*(b+c)=a=a

田a=(a*b)

田(a*c);若

a=lub{a,b,c},則a*(b

田c)=b

田c=(a*b)

田(a*c);若

b≤a≤c,

則a*(b④c)=a*c=a=b

田a=(a*b)

田(a*c).②集S的冪集格<p(S),U,∩,C>

是分配格.

證：由集合論知(定理2.2-2):A∩(BUC)=(A∩B)U(A∩C).對(duì)任意正蓬數(shù)n(Sn,GCD,LCM)是分配格證：對(duì)任意x,y∈Sn,

max{nm}

maxíLCM(xy)=A

·Rmin{nm}

min{xx}GCD(xy)=B

R由〈I,min,max,≤)

是分配格知min(a,,max(b,c?))=max(min(a,b;),min(a?,c?)

).由

此

立

即

推

出GCD(x,LCM(y,z))=LCM(GCD(x,y),GCD(x,z)).所以，格(S,GCD,LCM)

是分配格.a*(b④c)=a*1=a,

b*(a④c)=b*1=b(a*b)田(a*c)=0

田0=0,

(b*a)田(b*c)=0

田c=c注①

此兩例都不滿足雙消去律：a*b=a*cAa

田

b=a④c→b=c.②

可

以

證

明

：

格L

是

分

配

格

當(dāng)

且

僅當(dāng)

L

沒(méi)

有

同

構(gòu)于例1或例2的子格.非

分

配

格

的

舉

例例2a

o分配格的充要條件·

定理：格<L,*,田)是分配格當(dāng)且僅當(dāng)在L中成立

雙消去律：

a*b=a*c

a田b=a④c→

b=c.證：由已知條件，分配律及吸收律立即推出必要性：c=c*(a

田c)=c*(a④b)=(c*a)田(c*b)=(b*a)田(c*b)=(a

田c)*b=(a④b)*b=b.充分性(7.3#2)(由逆反律)等價(jià)于：若L

不是分配格，則在L

中雙消去律不成立.但這一結(jié)論可由上面關(guān)于非分配格的注①和②推出(在L

中有同構(gòu)于例1或例2的子格，它們都不滿足雙消去律)●格的全下界與全上界的概念·

格(L,≤)(視為偏序集)的元素a

稱為L(zhǎng)的全下(上)

界，如果

Vb(b∈L→a≤b)(Vb(b∈L→b≤a))·格的全下(上)界至多有一個(gè)，并記為0(1).證：若有兩個(gè)：u,v,

則

u≤vAv≤u,

進(jìn)

而

推

出u=v.

·

由

定

義

得

：

對(duì)

任

意b

∈L

有b*0=0,b

田0=b;b*1=b,b田1=1.·

例①

對(duì)任何有限格L={a,

…,a}有0=a,*

…

*a,

1=a?

…a·②<I,≤

全下界，全上界皆無(wú)；

(N,≤)有全下界

0而無(wú)全上界；<[0,1],≤>全下界，全上界皆有.有

界

格

與

有

補(bǔ)

格定義：同時(shí)有全下界0和全上界1的格稱為有界格；有界格(L,*,田，0,1)的元素a

的補(bǔ)元是滿足a*b=0△a④b=1的元素b∈L;

每元都有補(bǔ)元的有界格稱為有補(bǔ)格.例：霽集格<p(S),U,∩,',①,S>

及圖7.3-4中的格.注①0和1互為補(bǔ)元，且是唯一的(定理7.3-7).②

a∈{0,1}的補(bǔ)元一般不唯一(p225

例4).3)

分

配

格

任

何

元a

的

補(bǔ)

元

唯

一

.證：設(shè)b,c為a的補(bǔ)元，即a*b=0=a*cAa④b=1=a④c,則因分配格中雙消去律成立，

故由上式導(dǎo)出b=c.有

補(bǔ)

分

配

格

的

性

質(zhì)①定義：有補(bǔ)分配格中每元的補(bǔ)元唯一，從而可定

義一個(gè)“取補(bǔ)”的一元運(yùn)算.因此，此種格是一

個(gè)有兩個(gè)二元運(yùn)算，

一個(gè)一元運(yùn)算和常數(shù)0,1的代數(shù)(L,*,田，',0,1),稱為布爾代數(shù).(例如，界集格<p(S),U,∩,',①,S)是布爾代數(shù).)②

對(duì)有補(bǔ)分配格的任一元a,(a')'=a.證：根據(jù)是：a*a'=0=a'*a,a田a'=1=a'田a中a,a'的地位

對(duì)

稱

和

補(bǔ)

元

唯

一

。③

(a*b)′'=a'④b',(a田b)'=a'*b'

(摩根律).證：(a*b)*(a

'田b')=(a*b*a')田(a*b*b')=0

田0=0;

(a*b)

田(a

'田b')=(a田a'田b')*(b④a'④b')=1*1=1.有

補(bǔ)

分

配

格

的

性

質(zhì)

續(xù)④

(7.3#

11)有界分配格L的所有補(bǔ)元的集S構(gòu)成

L的一個(gè)有補(bǔ)分配子格.證：對(duì)S中任二元a,b,有a',b'∈S(用②);由③a*b

有補(bǔ)元a'田b',a田b有補(bǔ)元a'*b',由此推出a*b,a田b∈S;又0,1∈S,所以S對(duì)三個(gè)運(yùn)算及兩個(gè)

常

數(shù)

封

閉

.⑤

a≤b

?

a*b'=0

?a'b=1.證：只證前部分(后部分由摩根律推出)

.

a≤b

→

a*b=a→

a*b'=a*b*b'=a*0=0;a*b'=0

→

b田(a*b')(=b

田0)=b→(bHa)*(b+b')=b

分

配

律→

b④a=b

=

a≤b.布

爾

代

數(shù)

的

兩

個(gè)

等

價(jià)

定

義定義1:布爾代數(shù)是有補(bǔ)分配格

.定義2(公理化定義):有兩個(gè)二元運(yùn)算的代數(shù)<B,*,田}稱為布爾代數(shù)，如果對(duì)任意元素a,b,c∈B,成

立①

(交換律)

a*b=b*a,a④b=b

田a;②

(分配律)

a*(b④c)=(a*b)

田(a*c),a田(b*c)=(a

田b)*(a

田c);③

(有界律)存在0,1∈B,

使

得a*1=a,a④0=a,a∈B;④

(有補(bǔ)律)

B

的每一元a

都有(唯一)a'∈S,使

得a*a'=0,a④a'=1.注：布爾代數(shù)的兩個(gè)定義是等價(jià)的(證明略).·①

冪集代數(shù)：

<p(S),U,∩,',の,S>;·②

命題代數(shù)：

<B,V,A,-,F,T);注：在B中把互相邏輯等價(jià)命題視為相等.命題代數(shù)B中的偏序關(guān)系是邏輯蘊(yùn)涵關(guān)系：

→

,因?yàn)椋篈AB=A

?-AVB=(-AV-B)VB=-AVT=T?A→B.·③n

元開(kāi)關(guān)代數(shù)：

(A,V

為布爾乘，布爾加運(yùn)算)

B

,{*{,

-，…,,x0>,|1x>

其…

∈

{0,1}},0=<0,

…,0),1=<1,

…,1),-(x?,

…,x>=<-x?,

…

,-xn>,<x?,

…,x)*(y?,

…,yn)=(x?Ay,

…,xnAyn),<x1,…,x>

田(y1,…,yn>=(x1Vy?

,…,xVy).,x中,,x,田布爾代數(shù)舉例(只須驗(yàn)證4條公理)布爾同態(tài)與布爾同構(gòu)二布爾代數(shù)之間的映射f:<B,*,田，',0,1)→(B',*',田’,-,0',1>稱為布爾同態(tài)，如果對(duì)任意a,b∈B,有f(a*b)=f(a)*'f(b);f(a④b)=f(a)田'f(b);f(a')=-f(a);f(0)=0',f(1)=1'.若f為雙射，則稱f為布爾同構(gòu).若用B,的元素表示n元集S霽集p(S)的元素，則可

用XAY

表示X∩Y;XVY

表示XUY;-X

表示補(bǔ)集X'和用0,1分別表示O,S.

由此不難看出：

n

元集的界

集

代

數(shù)

與n

元

開(kāi)

關(guān)

代

數(shù)

布

爾

同

構(gòu)

.類似地，利用n元命題的主合，析取范式及其合，析

取

運(yùn)

算

與

否

定

運(yùn)

算

也

能

證

明n

元

命題

代

數(shù)

與n

元

開(kāi)

關(guān)

代

數(shù)

布

爾

同

構(gòu)

.布

爾

代

數(shù)

的

一

個(gè)

基

本

定

理·

定理：任何布爾代數(shù)都同構(gòu)于一個(gè)需集代數(shù)(要

建立一蓋套布爾原子理論進(jìn)行證明，從略).·

推論：有限布爾代數(shù)都同構(gòu)于某個(gè)開(kāi)關(guān)代數(shù)，從

而有限布爾代數(shù)的元素個(gè)數(shù)是2的整數(shù)界.·應(yīng)用舉例：格(S12,GCD.LCM)是布爾代數(shù)嗎?解：

S1?={1,2,3,4,6,12}的元素個(gè)數(shù)6不是2的蓬

數(shù)界，故不是布爾代數(shù).不難看出2沒(méi)有補(bǔ)元，因

為2④x=LCM(2,x)=12當(dāng)且僅當(dāng)x=12,而12的補(bǔ)元

是1而不是2.·

布爾代數(shù)(B,*,田，',0,1)的子集S稱為B的子布

爾代數(shù)，如果S對(duì)運(yùn)算*,田，'封閉和0,1∈S.布爾代數(shù)(B,,*,

,’,01,1?

>,<B?

,*2,田?

,-,0?

,12>

的積代數(shù)是(B?

×B?

,*,田，’,0,1},其中<a,c)'=(a’,-c);<a,c}*(b,d)=<a*,b,c*2d);〈a,c)田(b,d)=<a田，b,c田2d};O=<01,02>;1=<11,12>.●

子布爾代數(shù)與積布爾代數(shù)本身都是布爾代數(shù)，·

每個(gè)布爾代數(shù)(B,*,田，’,0,1)都有兩個(gè)平凡的子布爾代數(shù)：自身和{0,1}.

(封閉性：0*0=0*1=0;1*1=1;0田1=1田1=1;0④0=0;0'=1;1'=0.)布爾代數(shù)的子代數(shù)與積代數(shù)7.4#1(c)證明布爾恒等式試證：

(a*c)田(a'*b)田(b*c)=(a*c)

田(a'*b).解：

(a*c)

田(a'*b)田(b*c)=(a*c)

田(a'*b)田((b*c)*(a

田a'))=(a*c)

田(a'*b)田((b*c)*a)

田((b*c)*a'))=((a*c)

田(a*c*b))

田((a'*b)田(a'*b*c))=(a*c)田(a'*b).(第一等式用了么律；第2等式用了分配律；第3等式用了交換律與結(jié)合律；第4等式用了吸收律)7.4#1(d)試

證

：(a

田b')*(b

田c')*(c

田a')=(a

'田b)*(b

'田c)*(c

'田a).解

：

用

分

配

律

分

別

展

開(kāi)

上

式

兩

邊并

用

補(bǔ)

元

及

全

下界性質(zhì)化簡(jiǎn)得(式中*省略)左

邊=abc

田aba

'田ac'c田ac'a'田b'bc田b'ba'田b'c'c田b'c'a'=abc田a'b'c'

(相當(dāng)于化成主析取范式)右

邊=a'b'c'④a'b'a田a'cc'④a'ca④bb'c'④bb'a田bcc'田bca=a'b'c'④abc=

左

邊布爾表達(dá)式與布爾函數(shù)●

設(shè)(B,*,田，',0,1)為布爾代數(shù).取值于B中元素

的變?cè)Q為布爾變?cè)?/p>

B中元素(包括0,1)稱為布

爾

常

元

.由布爾變?cè)?，布爾常元?jīng)有限次*,田，'運(yùn)算形成的式子稱為B上布爾表達(dá)式.·例：對(duì)布爾代數(shù)B=<{a,b,0,1},*,田，',0,1}來(lái)說(shuō)，以下各式都是B上布爾表達(dá)式：f=a*(0田b)*(a田b');g=(a*x,)田(a*b'*x?)田(x?

′*x?*0);h=x?*(x?

甲x?)'.·

布

爾

代

數(shù)B

上

含n

個(gè)

布

爾

變

元

的

布

爾

表

達(dá)

式

稱為B上一個(gè)n元布爾函數(shù).化簡(jiǎn)：(a*b)田(a'*b*c')田(b*c)解

：

仍

把

*

省

略

不

寫(xiě)原

式

=

(ab(c田c))

田a'bc'④bc

全

上

界

性

質(zhì)=(abc

田abc')田a'bc'田bc

分

配

律=(abc④bc)

田(abc'田a'bc')

交換，結(jié)合律=

bc田((a田a')bc')