離散數(shù)學(xué)(第16-17章)陳瑜

陳瑜Email：chenyu.inbox@2/4/2023離散數(shù)學(xué)計算機學(xué)院2/4/20231計算機科學(xué)與工程學(xué)院第16章：環(huán)和域16.1環(huán)的定義及其性質(zhì)2/4/20232計算機科學(xué)與工程學(xué)院環(huán)和域

前面討論了具有一個二元運算的代數(shù)系統(tǒng)——半群、含幺半群、群、子群。下面討論具有兩個二元運算的代數(shù)系統(tǒng)。給定兩個代數(shù)系統(tǒng)<A,+>，<A,*>可將它們組合成一個具有兩個二元運算的代數(shù)系統(tǒng)<A,+,*>,而這兩個二元運算符+和*之間是有聯(lián)系的。環(huán),域，特別是有限域是糾錯碼理論的基礎(chǔ)。2/4/20233計算機科學(xué)與工程學(xué)院環(huán)Ring定義16.1

一個代數(shù)系統(tǒng)<R,+,*>，如果滿足：

（1）<R，+>是阿貝爾群；

（2）<R,*>是半群；

（3）乘法*在加法+上可分配。即對任意a，b，cR有

a*(b+c)=（a*b）+（a*c）

(b+c)*a=（b*a）+（c*a)

則稱<R,+,*>是一個環(huán)。(聯(lián)系兩個二元運算，否則就不是一個系統(tǒng)而是兩個系統(tǒng))2/4/20234計算機科學(xué)與工程學(xué)院例16.1在加法和乘法作用下，整數(shù)、實數(shù)、有理數(shù)、偶數(shù)和復(fù)數(shù)都能構(gòu)成環(huán)。

<Z,+,×><R,+,×><Q,+,×><E,+,×><C,+,×>+可以交換，0是+的幺元，

i的逆為-i；+,×可結(jié)合,×對+可分配2/4/20235計算機科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20236計算機科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵

對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20237計算機科學(xué)與工程學(xué)院例16.2設(shè)Zk表示整數(shù)集Z上的模k剩余類集合，即:Zk={[0]，[1]，[2]，…，[k-1]}<Zk

，>是群（剩余類加群），<Zk

，>是半群（剩余類乘半群），∵對[i]，[j]，[k]Zk有[i]（[j][k]）=[i(j+k)]=[ij+ik]=[ij][ik]=([i][j])([i][k]）∴<Zk

，，>是環(huán)，稱為（模k）剩余類環(huán)。特別，k=2時，稱為布爾環(huán)。2/4/20238計算機科學(xué)與工程學(xué)院定理16.1(移項法則)設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:

a+b=ca+b-c=θ2/4/20239計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202310計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)(-a)*b=a*(-b)=-(a*b)(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明:

因為a*θ=a*（θ+θ）=(a*θ)+(a*θ)，由移項法則a*θ=θ。同樣，可得θ*a=θ。2/4/202311計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202312計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明：因為(a*(-b))+(a*b)=a*(-b+b)=a*θ=θ,所以a*(-b)=-(a*b)。同理，(a*b)+((-a)*b)=(a-a)*b=θ,所以（-a)*b=-(a*b).2/4/202313計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c2/4/202314計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*b(b-c)*a=b*a-c*aa*(b-c）=a*b-a*c證明：利用②式的結(jié)果，

((-a)*(-b))-(a*b)=((-a)*(-b)）+((-a)*b)）=(-a)*(-b+b)=(-a)*θ=θ,但是，-(a*b)又是a*b的逆，根據(jù)群<R,+>中逆的唯一性，a*b=(-a)*(-b).2/4/202315計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)證明：a*(b-c)=a*(b+(-c))=(a*b)+(a*(-c))=(a*b)-(a*c).2/4/202316計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)

（b-c）*a=(b*a)-(c*a)2/4/202317計算機科學(xué)與工程學(xué)院定理16.2設(shè)<R,+,*>是一個環(huán)，θ是加法幺元，對任意a，b，cR有:a*θ=θ*a=θ(加法幺元是乘法零元)a*(-b)=-(a*b)=(-a)*b

(-a)*(-b)=a*ba*(b-c)=(a*b)-(b*c)

（b-c）*a=(b*a)-(c*a)

這個定理表明，普通環(huán)的運算性質(zhì)在很多方面類似于數(shù)的運算性質(zhì)，但是在某些方面它們卻有不同。例如在模m剩余類環(huán)<Zm,，

>中，我們特別注意到一種情況：當[i]≠[0],[j]≠[0]時，卻可能[i][j]=[0]。例如在<Z6,，

>中，[2][3]=[0],[4][3]=[0]。2/4/202318計算機科學(xué)與工程學(xué)院定義16.2設(shè)<R,+,*>是環(huán)，a,b∈R。如果a≠θ且b≠θ,而a*b=θ，則稱a和b是R中的零因子。例16-3模m剩余類環(huán)<Zm,，

>沒有零因子當且僅當m是素數(shù)。因為當m是合數(shù)時，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當m是素數(shù)時，不存在a≥2和b≥2使m=ab，因而無零因子。

2/4/202319計算機科學(xué)與工程學(xué)院定義16.2設(shè)<R,+,*>是環(huán)，a,b∈R。如果a≠θ且b≠θ,而a*b=θ，則稱a和b是R中的零因子。例16.3

模m剩余類環(huán)<Zm,，

>沒有零因子當且僅當m是素數(shù)。因為當m是合數(shù)時，必有a≥2,b≥2使m=ab，從而[a][b]=[m]=[0],而且[a]和[b]都是零因子。當m是素數(shù)時，不存在a≥2和b≥2使m=ab，因而無零因子。

合數(shù)是除了1和它本身還能被其他的正整數(shù)整除的正整數(shù).

除2之外的偶數(shù)都是合數(shù).(除0以外)2/4/202320計算機科學(xué)與工程學(xué)院16.2整環(huán)與域2/4/202321計算機科學(xué)與工程學(xué)院特殊環(huán)定義16.3設(shè)<R,+,*>是一個環(huán):如果<R,*>是可交換的，稱<R,+,*>是交換環(huán)；如果<R,*>是含幺半群，稱<R,+,*>是含幺環(huán)；如果對于R中某些非零元素a≠θ、b≠θ,能使a*b=θ,稱<R,+,*>是含零因子環(huán)；a、b稱為零因子；如果<R,+,*>是可交換的、含幺、而無零因子，則稱它是整環(huán)。2/4/202322計算機科學(xué)與工程學(xué)院例16.4（同前例16.3）

證明（模k）剩余類環(huán)<Zk，，>無零因子當且僅當k是素數(shù)。證明：∵當k是合數(shù)時，必有a≥2、b≥2，使得k=ab，從而[a][b]=[k]=[0]，即[a]、[b]都是零因子。又∵當k是素數(shù)時，不存在a≥2、b≥2，使得k=ab，從而無零因子。

∴結(jié)論成立。2/4/202323計算機科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當且僅當對a,x,yR，當a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202324計算機科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當且僅當對a,x,yR，當a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202325計算機科學(xué)與工程學(xué)院定理16.3

設(shè)<R,+,*>是一個環(huán)，則R中無零因子當且僅當對a,x,yR，當a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）證明如果R中無零因子，則當a*x=a*y時，(a*x)-(a*y)=θ，即a*(x-y)=θ.由于a≠θ,因而x-y=θ，即x=y。同理，由x*a=y*a可以得出x=y。反過來，設(shè)由a*x=a*y必然得出x=y的結(jié)論，如果R中存在b和c使b*c=θ，那么由b*c=θ=b*θ就導(dǎo)出c=θ。這說明R中必?zé)o零因子。

2/4/202326計算機科學(xué)與工程學(xué)院定理16.3設(shè)<R,+,*>是一個環(huán)，則R中無零因子當且僅當對a,x,yR，當a≠0時，

a*x=a*yx=y或x*a=y*ax=y

（即滿足可約律）定義16.4

設(shè)<R,+,*>是一個環(huán)，S是R的非空集合，如果<S,+,*>也是一個環(huán)，則稱S是R的子環(huán)。例如：<{[0],[2],[4]}，，>是模6剩余類環(huán)<Z6，，>的子環(huán)。2/4/202327計算機科學(xué)與工程學(xué)院環(huán)的同構(gòu)與同態(tài)定義16.5

設(shè)<S,+,*>和<T,,>是兩個環(huán)，如在集合S與T之間存在映射f：ST，使得對a，bS，有：

f(a+b)=f(a)f(b)

f(a*b)=f(a)f(b)

則稱f是從<S,+,*>到<T,,>的環(huán)同態(tài)映射，f(S)為S的一個同態(tài)象。當f是一個滿射時，則稱f為滿同態(tài)；當f是一個雙射時，則稱f是環(huán)同構(gòu)映射；2/4/202328計算機科學(xué)與工程學(xué)院例16.5存在整數(shù)環(huán)<Z,+,*>到模m剩余類環(huán)<Zm,,>的同態(tài)，因為我們可以定義映射f：Z→Zm如下：使對所有x∈Z，

f(x)=xmodm.

在此映射下，設(shè)a,b∈Z,由同余的性質(zhì)，

[a+b]=[a][b],[a*b]=[a][b]，所以<Z,+,*>～<Zm,,>

。2/4/202329計算機科學(xué)與工程學(xué)院定理16.4設(shè)f是環(huán)<S,+,*>到環(huán)<T,,>的同態(tài)映射，則:如果θ和e分別是S中的加法幺元和乘法幺元，則f(θ)和f(e)分別是f(S)中的幺元和幺元；對aS，如果-a（或a-1）是a的加法（或乘法）逆元，則f(-a)（或f(a-1)）是f(S)中的逆元（或逆元）；<f(S),,>也是環(huán)。2/4/202330計算機科學(xué)與工程學(xué)院域

給環(huán)施加進一步的限制，從而得到另一個代數(shù)系統(tǒng)——域。問題歸結(jié)為<R-{θ},*>是否是一個群。定義16.6

設(shè)<R,+,*>是一個環(huán)，如果<R,+>和<R-{θ},*>都是交換群，則稱<R,+,*>是域。

一般情況下，整環(huán)不是域，但當環(huán)的元素個數(shù)有限時，有以下結(jié)論：定理16.5有限整環(huán)<R,+,*>必是域。(教材p198)θ是加法幺元2/4/202331計算機科學(xué)與工程學(xué)院例16.6實數(shù)環(huán)<R,+,×>、有理數(shù)環(huán)<Q,+,×>、剩余類環(huán)<Zp，，>(p是素數(shù)）都是域。整數(shù)環(huán)<Z,+,×>、剩余類環(huán)<Zm，，>(m是合數(shù)）都不是域。因為<Z-{0}，×>、<Zm–{[0]}，>都不是群。2/4/202332計算機科學(xué)與工程學(xué)院習(xí)題熟記相關(guān)概念2/4/202333計算機科學(xué)與工程學(xué)院第17章格與布爾代數(shù)17.1格的定義與性質(zhì)2/4/202334計算機科學(xué)與工程學(xué)院格與布爾代數(shù)下面討論另外兩個重要的代數(shù)系統(tǒng)—格與布爾代數(shù)，這兩個代數(shù)系統(tǒng)與前面討論的代數(shù)系統(tǒng)之間存在著一個重要區(qū)別：在格與布爾代數(shù)中，偏序關(guān)系具有重要意義。2/4/202335計算機科學(xué)與工程學(xué)院本章主要介紹以下幾點：格的概念和基本性質(zhì)子格的定義特殊的格及性質(zhì)布爾代數(shù)的概念和基本性質(zhì)2/4/202336計算機科學(xué)與工程學(xué)院格的定義定義17.1（代數(shù)格）設(shè)<L，∨，∧>是一個代數(shù)系統(tǒng)，如果∨，∧滿足：交換律：a∨b=b∨a，a∧b=b∧a,結(jié)合律：a∨(b∨c)=(a∨b)∨c,

a∧(b∧c)=(a∧b)∧c吸收律：a∨(a∧b)=a，a∧(a∨b)=a

則稱<L，∨，∧>是一個代數(shù)格。2個典型的格:

集合代數(shù)系統(tǒng)<2A，∪，∩>

命題邏輯系統(tǒng)<，∨，∧>代數(shù)格2/4/202337計算機科學(xué)與工程學(xué)院定理17.1

(冪等律)設(shè)<L,∨，∧>是一個代數(shù)格，a∈L，則必有a∨a=a,a∧a=a。證明：

a∨a=a∨(a∧(a∨a))(吸收律)=a.(吸收律)

在上兩式中，把∨換成∧，把∧換成∨后，可以證明a∧a=a。2/4/202338計算機科學(xué)與工程學(xué)院復(fù)習(xí)：偏序關(guān)系是集合上的自反的、可傳遞、反對稱關(guān)系,它提供比較集合元素的工具。定義：設(shè)R是集合A上的自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的偏序關(guān)系(記為“”,讀作“小于等于”)。序偶<A，R>稱為偏序集。定義17.2設(shè)<L，>是一個偏序集，對a，bL，集合{a，b}都有最大下界(glb)和最小上界(lub)，則稱<L，>是一個偏序格，簡稱L是一個格，若L是一個有限集，則稱<L，>為有限格。2/4/202339計算機科學(xué)與工程學(xué)院復(fù)習(xí)：偏序關(guān)系是集合上的自反的、可傳遞、反對稱關(guān)系,它提供比較集合元素的工具。定義：設(shè)R是集合A上的自反的、反對稱的、傳遞的關(guān)系，則稱R是A上的偏序關(guān)系(記為“”,讀作“小于等于”)。序偶<A，R>稱為偏序集。定義17.2

設(shè)<L，>是一個偏序集，對a，bL，集合{a，b}都有最大下界(glb)和最小上界(lub)，則稱<L，>是一個偏序格，簡稱L是一個格，若L是一個有限集，則稱<L，>為有限格。從定義知道：有限偏序集要成為格，必須有一個最大元和最小元。2/4/202340計算機科學(xué)與工程學(xué)院偏序集<2A，>中，任何兩個元素X、Y2A，都有l(wèi)ub（X，Y）=X∪Y，glb（X，Y）=X∩Y，則<2A，>是一個偏序格，稱為冪集格。2/4/202341計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；2/4/202342計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明

（首先證明<L,≤>是偏序集。）由于a∧a=a(冪等律)，因此a≤a,即“≤”具有自反性。設(shè)a≤b且b≤a,則由“≤”的定義a=a∧b(a≤b)=b∧a(交換律)=b,(b≤a),即反對稱性成立。

2/4/202343計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明

（首先證明<L,≤>是偏序集。）再設(shè)a≤b，b≤c,那么a∧c=(a∧b)∧c(由a≤b)=a∧(b∧c)(結(jié)合律)=a∧b(由b≤c)

=a,(由a≤b),即有a≤c，傳遞性成立。2/4/202344計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界?，F(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202345計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。

現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202346計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界?，F(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。

類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。2/4/202347計算機科學(xué)與工程學(xué)院定理17.2設(shè)<L，∨，∧>是一個代數(shù)格，定義格上的自然偏序“”：ab當且僅當a∧b=a，則<L，>是一個偏序格；

證明

其次，證明對任意x，y∈L，{x，y}在L中有最大下界和最小上界。由于x∧(x∧y)=x∧y,(結(jié)合律，冪等律)所以，x∧y≤x.同理可得x∧y≤y。這說明x∧y是{x，y}的一個下界。

現(xiàn)在設(shè)c是x和y的任一下界，即c≤x且c≤y,那么c∧(x∧y)=(c∧x)∧y(結(jié)合律)=c∧y=c.這說明c≤x∧y，從而知道，glb(x，y)=x∧y。類似地，可以證明lub(x，y)=x∨y，只需在上述證明中把∧換成∨，把∨換成∧即可。綜合以上結(jié)論，命題得證。2/4/202348計算機科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202349計算機科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202350計算機科學(xué)與工程學(xué)院定理17.3設(shè)<L，>是一個偏序格，在格上定義“∨”、“∧”：a∧b=glb（a，b），a∨b=lub（a，b），則<L，∨，∧>是一個代數(shù)格。

證明

從運算和的定義可以看出，它們滿足交換律、結(jié)合律和冪等律?，F(xiàn)證明吸收律成立。事實上，由glb(a,b)≤a≤lub(a,b),可以看出

a∧(a∨b)=glb(a,lub(a,b))=a,

a∨(a∧b)=lub(a,glb(a,b))=a.

由此可知，<L,∨，∧>是代數(shù)格。

定理17.2和17.3表明：格的兩種定義是完全等價的。以后我們將不特別加以區(qū)分，而是根據(jù)需要采用相應(yīng)的定義來說明問題。2/4/202351計算機科學(xué)與工程學(xué)院例如圖所示的八個偏序集都是格；2/4/202352計算機科學(xué)與工程學(xué)院2/4/202353計算機科學(xué)與工程學(xué)院如圖所示的四個偏序集都不是格。2/4/202354計算機科學(xué)與工程學(xué)院作業(yè)熟練掌握相關(guān)概念、定理2/4/202355計算機科學(xué)與工程學(xué)院17.2子格與格同態(tài)2/4/202356計算機科學(xué)與工程學(xué)院定義17.3

設(shè)代數(shù)系統(tǒng)<L,∨,∧>是一個格，SL，若S滿足：S≠Φ；運算∨和∧對子集S都是封閉的；則稱<S,∨,∧>是<L,∨,∧>的子格。2/4/202357計算機科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（?。┰厥菍ε几裰械淖钚。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202358計算機科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（小）元必是對偶格中的最?。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202359計算機科學(xué)與工程學(xué)院格的性質(zhì)與同態(tài)定義17.4設(shè)<L，>和<L，′>是兩個偏序格，如果偏序關(guān)系′是的逆關(guān)系，則稱此兩個偏序格為對偶格。

設(shè)L是由18的正因子組成的集合，則L關(guān)于整除關(guān)系構(gòu)成的逆關(guān)系是倍數(shù)關(guān)系；設(shè)倍數(shù)關(guān)系用“‖”表示，那么<L，‖>是格，并和<L，∣>互為對偶。

在一個格中的最大（?。┰厥菍ε几裰械淖钚。ù螅┰?；即兩個對偶格的Hasse圖是相互顛倒的。2/4/202360計算機科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。2/4/202361計算機科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。2/4/202362計算機科學(xué)與工程學(xué)院定義17.5設(shè)<L，∨，∧>是一個格，E是格中的公式。將E中的0（最小元）和1（最大元）互換、∨和∧互換后得到的新公式E*稱為E的對偶公式。對偶原理：設(shè)X和Y是格<L，∨，∧>上的兩個公式，X*和Y*是相對應(yīng)的對偶公式。如果X=Y，則X*=Y*。定理17.4設(shè)X和Y是格<L，∨，∧>上的兩個公式，是對應(yīng)的偏序。如果XY，則Y*X*。

證明：由偏序集的定義及對偶原理有：

XYX∧Y=X（偏序定義）

X*∨Y*=X*

（對偶原理）Y*X*

（偏序定義）2/4/202363計算機科學(xué)與工程學(xué)院定理17.5、17.6設(shè)<L，∨，∧>是一個格，是對應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤b

a∨c≤b∨c

a≤b

a∧c≤b∧c

a≤b且c≤d

a∧c≤b∧da≤b且c≤d

a∨c≤b∨d

a≤b且a≤c

a≤b∧ca≤c且b≤c

a∨b≤ca∨(b∧c)≤(a∨b)∧(a∨c) (a∧b)∨(a∧c)≤a∧(b∨c)

(保序性)(準分配關(guān)系)2/4/202364計算機科學(xué)與工程學(xué)院定理17.5、17.6設(shè)<L，∨，∧>是一個格，是對應(yīng)的偏序，a,b,c,dL，則：(教材p202)a≤b

a∨c≤b∨c

a≤b

a∧c≤b∧c

(保序性)證明：①a≤b

a∨b=b(a∨c)∨(b∨c)=b∨c

a∨c≤b∨c。②a≤b

a∧b=a(a∧c)∧(b∧c)=a∧c

a∧c≤b∧c。2/4/202365計算機科學(xué)與工程學(xué)院格的同態(tài)與同構(gòu)

將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個格，ψ是L到S的映射。如果對任意x,y∈L，都有：ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當ψ分別是單射、滿射和雙射時，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2/4/202366計算機科學(xué)與工程學(xué)院格的同態(tài)與同構(gòu)將代數(shù)系統(tǒng)的同態(tài)與同構(gòu)應(yīng)用于格，可以獲得格的同態(tài)與同構(gòu)定義：定義17.6設(shè)<L,∨，∧>和<S，，>是兩個格，ψ是L到S的映射。如果對任意x,y∈L，都有：ψ(x∨y)＝ψ(x)ψ(y)ψ(x∧y)＝ψ(x)ψ(y)，則稱ψ為從格<L,∨，∧>到格<S，，>的格同態(tài)映射，當ψ分別是單射、滿射和雙射時，ψ分別稱為單一格同態(tài)、滿格同態(tài)和格同構(gòu)。2/4/202367計算機科學(xué)與工程學(xué)院例設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。2/4/202368計算機科學(xué)與工程學(xué)院例

設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。2/4/202369計算機科學(xué)與工程學(xué)院例

設(shè)D6表示6的正因子集，證明因子格<D6

，|>和冪集格<2{a,b}，>是同構(gòu)的。證明：定義映射f：D6→2{a,b}，使得f(1)=,f(2)={a},f(3)=,f(6)={a,b}∵<D6

，|>對應(yīng)的代數(shù)格為<D6

，lcm，gcd><2{a,b}，>對應(yīng)的代數(shù)格為<2{a,b}，∪，∩>∴f(lcm(1,3))=f(3)==∪=f(1)∪f(3)f(gcd(2,6))=f(2)={a}={a}∩{a,b}=f(2)∩f(6)f(lcm(2,3))=f(6)={a,b}={a}∪=f(2)∪f(3)f(gcd(2,3))=f(1)=={a}∩=f(2)∩f(3)

其余情況也可一一驗證，又因為是雙射，所以，命題得證。lcm:最小公倍數(shù)gcd：最大公約數(shù)2/4/202370計算機科學(xué)與工程學(xué)院保序定理（教材p203）定理17.7設(shè)<L1，∨，∧>和<L2，，>是兩個格，對應(yīng)的偏序關(guān)系為、，則有：如果f：L1→L2是一個格同態(tài)，則對a，bL1，ab

f(a)

f(b)；

證明：對a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因為aba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對a，bL1，ab

f(a)f(b)2/4/202371計算機科學(xué)與工程學(xué)院保序定理定理17.7設(shè)<L1，∨，∧>和<L2，，>是兩個格，對應(yīng)的偏序關(guān)系為、，則有：如果f：L1→L2是一個格同態(tài)，則對a，bL1，ab

f(a)

f(b)；

證明：對a，bL1，由f是函數(shù)，所以有f(a)、f(b)L2， 因為aba∧b＝a，于是，由同態(tài)等式知：f(a)＝f(a∧b)＝f(a)f(b)

所以：f(a)f(b)。 即：對a，bL1，ab

f(a)f(b)2/4/202372計算機科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：

2/4/202373計算機科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：當f是L到P的格同構(gòu)時，它必須滿足保序定理，因此保序為必要條件是成立的。至于充分條件，只需證明由a≤bf(a)f(b)能導(dǎo)出f(a∨b)=f(a)⊕f(b)和f(a∧b)=f(a)f(b)就行了。

設(shè)a∨b=c，則a≤c且b≤c,從而f(a)f(c)，且

f(b)f(c).再由定理17-2.2第⑥條知道：

f(a)⊕f(b)

f(c)，這說明f(c)是f(a)和f(b)的一個上界。2/4/202374計算機科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：當f是L到P的格同構(gòu)時，它必須滿足保序定理，因此保序為必要條件是成立的。至于充分條件，只需證明由a≤bf(a)f(b)能導(dǎo)出f(a∨b)=f(a)⊕f(b)和f(a∧b)=f(a)f(b)就行了。設(shè)a∨b=c，則a≤c且b≤c,從而f(a)f(c)，且

f(b)f(c).再由定理17.5第⑥條知道：

f(a)⊕f(b)

f(c)，這說明f(c)是f(a)和f(b)的一個上界。a≤c且b≤ca∨b≤c2/4/202375計算機科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：

剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個上界，即f(a)f(d)且f(b)f(d)。由題設(shè)條件可以得到a≤d且b≤d，從而a∨b≤d，即c≤d，于是f(c)f(d).

由此，就證明了f(c)=f(a∨b)=f(a)⊕f(b)。同理可證f(a∧b)=f(a)f(b)。因此，雙射f是格同構(gòu)。2/4/202376計算機科學(xué)與工程學(xué)院定理17.8

雙射f：L→P為格<L,∨，∧>到格<P,⊕,>的格同構(gòu)的充分必要條件是：對任意的a,b∈L，a≤bf(a)f(b),其中≤和分別是格L和P對應(yīng)的偏序。

證明：剩下的任務(wù)要證明f(c)是f(a)和f(b)的最小上界。設(shè)f(d)是f(a)和f(b)的任意一個上界，即f(a)f(d)且f(b)f(d)。由題設(shè)條件可以得到a≤d且b≤d，從而a∨b≤d，即c≤d，于是f(c)f(d).

由此，就證明了f(c)=f(a∨b)=f(a)⊕f(b)。同理可證f(a∧b)=f(a)f(b)。因此，雙射f是格同構(gòu)。2/4/202377計算機科學(xué)與工程學(xué)院例

設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對xL,f(x)={y|yL且y|x}。則：

f(1)=1，f(2)={1,2},f(3)={1,3},f(12)={1,2,3,12}，且x|y時,f(x)f(y)

所以，f是保序映射。

而f(lcm(2,3))=f(12)={1,2,3,12},f(2)∪f(3)={1,2,3}

即f(lcm(2,3))≠f(2)∪f(3)

所以f不是<L，|>到<2L，>的格同態(tài)。2/4/202378計算機科學(xué)與工程學(xué)院例

設(shè)L={1，2，3，12}，在<L，|>和冪集格<2L，>之間構(gòu)造映射f：L→2L，使得對xL,f(x)={y|yL且y|x}。則：

f(1)=1，f(2)={1,2},f(3)={1,3},f(12)={1,2,3,12}，且x|y時,f(x)f(y)

所以，f是保序映射。而f(lcm(2,3))=f(12)={1,2,3,12},f(2)∪f(3)={1,2,3}

即f(lcm(2,3))≠f(2)∪f(3)

所以f不是<L，|>到<2L，>的格同態(tài)。2/4/202379計算機科學(xué)與工程學(xué)院習(xí)題熟練掌握相關(guān)概念、定理2/4/202380計算機科學(xué)與工程學(xué)院17.3分配格與有補格2/4/202381計算機科學(xué)與工程學(xué)院分配格定義17.7設(shè)<L,∨，∧>是一個格，如果對任意a,b,c∈L，都有：

a∨(b∧c)＝(a∨b)∧(a∨c)(1)

a∧(b∨c)＝(a∧b)∨(a∧c)(2)

則稱<L,∨，∧>是一個分配格。注意：式(1)和式(2)的兩個分配律是對偶的，由對偶原理，定義17.7可簡化為只含式(1)和式(2)中一個的分配律。2/4/202382計算機科學(xué)與工程學(xué)院分配格定義17.7設(shè)<L,∨，∧>是一個格，如果對任意a,b,c∈L，都有：

a∨(b∧c)＝(a∨b)∧(a∨c)(1)

a∧(b∨c)＝(a∧b)∨(a∧c)(2)

則稱<L,∨，∧>是一個分配格。注意：式(1)和式(2)的兩個分配律是對偶的，由對偶原理，定義17.7可簡化為只含式(1)和式(2)中一個的分配律。2/4/202383計算機科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運算，則<P,∧,∨>是否是分配格？解：1)對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202384計算機科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運算，則<P,∧,∨>是否是分配格？解：1)

對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202385計算機科學(xué)與工程學(xué)院例設(shè)A為任意一個集合，則冪集格<2A,∩,∪>是否是分配格？設(shè)P為命題公式集合，∧、∨分別是命題合取與析取運算，則<P,∧,∨>是否是分配格？解：1)對任意P、Q、R∈2A

，有：P∩(Q∪R)＝(P∩Q)∪(P∩R)P∪(Q∩R)＝(P∪Q)∩(P∪R)

所以，格<2A，∩,∪>是一個分配格。

2)

對任意R、S、T∈P，有R∧(S∨T)＝(R∧S)∨(R∧T)R∨(S∧T)＝(R∨S)∧(R∨T)

所以，格<P,∧,∨>是一個分配格。2/4/202386計算機科學(xué)與工程學(xué)院例證明圖中a）、b）所示的兩個格都不是分配格。2/4/202387計算機科學(xué)與工程學(xué)院證明在圖a）、b）中都取b,c,d三個元素來驗證。用“∧”和“∨”表示它們的交和并運算。在圖a）中， b∧

(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨e＝e。在圖b）中，b∧(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨d＝d。因此，在圖a）和圖b）中都有：b∧(c∨d)≠(b∧c)∨(b∧d)。故它們都不是分配格。2/4/202388計算機科學(xué)與工程學(xué)院證明在圖a）、b）中都取b,c,d三個元素來驗證。用“∧”和“∨”表示它們的交和并運算。在圖a）中， b∧

(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨e＝e。在圖b）中，b∧(c∨d)＝b∧a＝b，而 (b∧c)∨(b∧d)＝e∨d＝d。因此，在圖a）和圖b）中都有：b∧(c∨d)≠(b∧c)∨(b∧d)。故它們都不是分配格。2/4/202389計算機科學(xué)與工程學(xué)院結(jié)論一個格是分配格，當且僅當該格中沒有任何子格與圖中的兩個五元素格中的任何一個同構(gòu)。2/4/202390計算機科學(xué)與工程學(xué)院如圖a）～h）所示的八個圖都是分配格嗎？結(jié)論：1）四個元素以下的格都是分配格；

2）五個元素的格僅有兩個格是非分配格(前一個頁面中圖a）、b)），其余三個格(上圖中的圖f、圖g、圖h)都是分配格。2/4/202391計算機科學(xué)與工程學(xué)院定理17.9

設(shè)<L,∨,∧>是分配格，對于任何a,x,y∈L，如果a∨x＝a∨y且a∧x＝a∧y，則x＝y(tǒng)。

證明：x＝x∧

(a∨x) (吸收律)

＝x∧

(a∨y) (已知a∨x＝a∨y)

＝(x∧a)∨(x∧y) (分配律)

＝(a∧y)∨(x∧y) (已知a∧x＝a∧y)

＝y(tǒng)∧

(a∨x) (交換律，分配律)

＝y(tǒng)∧(a∨y) (已知a∨x＝a∨y)

＝y(tǒng) (吸收律)注意，在定理17.9中，<L,∨,∧>是分配格，a∨x＝a∨y和a∧x＝a∧y三者缺一不可。2/4/202392計算機科學(xué)與工程學(xué)院定理17.9

設(shè)<L,∨,∧>是分配格，對于任何a,x,y∈L，如果a∨x＝a∨y且a∧x＝a∧y，則x＝y(tǒng)。證明：x＝x∧

(a∨x) (吸收律)

＝x∧

(a∨y) (已知a∨x＝a∨y)

＝(x∧a)∨(x∧y) (分配律)

＝(a∧y)∨(x∧y) (已知a∧x＝a∧y)

＝y(tǒng)∧

(a∨x) (交換律，分配律)

＝y(tǒng)∧(a∨y) (已知a∨x＝a∨y)

＝y(tǒng) (吸收律)注意，在定理17.9中，<L,∨,∧>是分配格，a∨x＝a∨y和a∧x＝a∧y三者缺一不可。2/4/202393計算機科學(xué)與工程學(xué)院有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個格，若存在元素a∈L，使得對任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2/4/202394計算機科學(xué)與工程學(xué)院有界格定義17.8設(shè)<L,≤>（或<L,∨，∧>）是一個格，若存在元素a∈L，使得對任意x∈L，都有a≤x(或x≤a)，則稱a為格<L,≤>的最小元(或最大元)，分別記為0(或1)，而具有最大元和最小元的格稱為有界格。根據(jù)最大元“1”和最小元“0”的定義，對任意x∈L，1∧x＝x∧1＝x， 1∨x＝x∨1＝10∧x＝x∧0＝0， 0∨x＝x∨0＝x2/4/202395計算機科學(xué)與工程學(xué)院例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。有限格一定是有界格。但一個有界格則不一定是有限格，如<[0,1]，≤>。2/4/202396計算機科學(xué)與工程學(xué)院例如下圖a、b、c所示的格是有界格，其最大元和最小元都是1，0。圖12-3．2有限格一定是有界格。但一個有界格則不一定是有限格，如<[0,1]，≤>。2/4/202397計算機科學(xué)與工程學(xué)院有補格定義17.9、17.10設(shè)<L,∨,∧>為有界格，1和0分別為它的最大元和最小元，對于a∈L。如果存在b∈L，使得：a∧b＝0，a∨b＝1（同時成立），則稱a和b互為補元。若對任意a∈L，都有補元存在，則稱<L,∨,∧>為有補格。2/4/202398計算機科學(xué)與工程學(xué)院例

如下圖所示的圖，求其所有元素的補元(如果有的話)。2/4/202399計算機科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補格，圖b是有補格。補元如果存在，不一定唯一，那么，在什么條件下可以保證補元是唯一的呢？2/4/2023100計算機科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補格，圖b是有補格。

補元如果存在，不一定唯一，那么，在什么條件下可以保證補元是唯一的呢？2/4/2023101計算機科學(xué)與工程學(xué)院對于圖a（這里設(shè)x的補元為x’） 0'＝1，1'＝0，a'＝e，d'＝c，d'＝e， c'＝d，e'＝a，e'＝d，b無補元。對于圖b 0'＝1，1'＝0，a'＝d，a'＝c， b'＝d，b'＝c，c'＝a，c'＝b， d'＝a，d'＝b因此圖a不是有補格，圖b是有補格。

補元如果存在，不一定唯一，那么，在什么條件下可以保證補元是唯一的呢？2/4/2023102計算機科學(xué)與工程學(xué)院定理17.10在有補分配格(既是有補格又是分配格，簡稱為有補分配格)<L,∨,∧>中，如元素a∈L有補元存在，則此元素的補元必唯一。

證明：設(shè)a有兩個補元b和c，由補元的定義知：

a∧b＝0＝a∧c，a∨b＝1＝a∨c

由消去律（分配格所具有）知，b＝c。2/4/2023103計算機科學(xué)與工程學(xué)院定理17.10在有補分配格(既是有補格又是分配格，簡稱為有補分配格)<L,∨,∧>中，如元素a∈L有補元存在，則此元素的補元必唯一。

證明：

設(shè)a有兩個補元b和c，由補元的定義知：

a∧b＝0＝a∧c，a∨b＝1＝a∨c

由消去律（分配格所具有）知，b＝c。2/4/2023104計算機科學(xué)與工程學(xué)院定理17.11、17.12（教材p206）

設(shè)<L,∨,∧>是有補分配格，“≤”是該格的自然偏序，則對任意a,b∈L，都有；

(對合律)

；；a≤b

。(DeMorgan律)2/4/2023105計算機科學(xué)與工程學(xué)院17.4布爾代數(shù)2/4/2023106計算機科學(xué)與工程學(xué)院布爾代數(shù)定義

稱有補分配格<B,∨,∧>為布爾格。在有補分配格中每個元都有補元而且補元唯一，則可以將求元素的補元“ˉ”作為一種一元運算，則此布爾格<B,∨,∧>可記為<B,∨,∧,ˉ,0,1>，此時，稱<B,∨,∧,ˉ,0,1>為布爾代數(shù)。（突出了代數(shù)特征）若一個布爾代數(shù)的元素個數(shù)是有限的，則稱此布爾代數(shù)為有限布爾代數(shù)。2/4/2023107計算機科學(xué)與工程學(xué)院布爾代數(shù)定義

稱有補分配格<B,∨,∧>為布爾格。在有補分配格中每個元都有補元而且補元惟一，則可以將求元素的補元“ˉ”作為一種一元運算，則此布爾格<B,∨,∧>可記為<B,∨,∧,ˉ,0,1>，此時，稱<B,∨,∧,ˉ,0,1>為布爾代數(shù)。（突出了代數(shù)特征）若一個布爾代數(shù)的元素個數(shù)是有限的，則稱此布爾代數(shù)為有限布爾代數(shù)。2/4/2023108計算機科學(xué)與工程學(xué)院例 如圖(a)、(b)、(c)所示的圖中，圖(a)是一個布爾代數(shù)，但圖(b)、(c)都不是布爾代數(shù)。2/4/2023109計算機科學(xué)與工程學(xué)院布爾代數(shù)的性質(zhì)布爾代數(shù)是有補分配格，有補分配格<B，∨，∧>必須滿足：是格分配律成立有最大元和最小元（有界）；每個元的補元存在；最大元1和最小元0可以用下面的同一律和零律來描述：在L中存在兩個元素0和1，使得對任意a∈L，有：

a∧1＝a，a∨0＝a；a∨1＝1，a∧0＝0。2/4/2023110計算機科學(xué)與工程學(xué)院補元的存在可以用下面的互補律來描述：對任意a∈L，存在∈L，使得a∧＝0，a∨＝1。從本章17.1節(jié)知道格可以用交換律、結(jié)合律、吸收律、冪等律來描述。有補分配格就必須滿足交換律、結(jié)合律、吸