第六格與布爾代數(shù)

第六格與布爾代數(shù)演示文稿目前一頁\總數(shù)四十二頁\編于七點(diǎn)（優(yōu)選）第六格與布爾代數(shù)目前二頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21第6章格與布爾代數(shù)集合的表示方法2子格3特殊格4偏序格與代數(shù)格1格的性質(zhì)2布爾代數(shù)5目前三頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/216.1格的定義目前四頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21一、定義設(shè)<L,?>是一個偏序集，如果對任意a,b∈L，{a,b}都有最大下界和最小上界存在，則稱<L,?>是格，簡稱L是格。若L為有限集，則稱格<L,?>為有限格。目前五頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21用a∨b表示{a,b}的最小上界，用a∧

b表示{a,b}的最大下界∨讀作“并”∧讀作“交”目前六頁\總數(shù)四十二頁\編于七點(diǎn)目前七頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21例（1）Sn表示n的所有因子的集合，D是一個整除關(guān)系，問此偏序集<Sn

，D>是否是一個格？（2）設(shè)A是一個集合，P(A)是A的冪集，是集合上的包含關(guān)系，問此偏序集<P(A),>是否是一個格？目前八頁\總數(shù)四十二頁\編于七點(diǎn)定理(格的基本性質(zhì))設(shè)<L,?>是格,則運(yùn)算∨和∧適合交換律、結(jié)合律、冪等律和吸收律,即(1)a,b∈L

有

a∨b=b∨a,a∧b=b∧a(2)

a,b,c∈L

有

(a∨b)∨c=a∨(b∨c),(a∧b)∧c=a∧(b∧c)(3)a∈L

有

a∨a=a,a∧a=a(4)

a,b∈L

有

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

目前九頁\總數(shù)四十二頁\編于七點(diǎn)定理（格的性質(zhì)：序與運(yùn)算的關(guān)系）設(shè)L是格,則a,b∈L有

a?b

a∧b=a

a∨b=b目前十頁\總數(shù)四十二頁\編于七點(diǎn)定理（格的保序性）設(shè)L是格,a,b,c,d∈L，若a?b且c?d,則

a∧c?b∧d,a∨c?b∨d目前十一頁\總數(shù)四十二頁\編于七點(diǎn)定理：設(shè)L是格,a,b,c∈L有

a∨(b∧c)?(a∨b)∧(a∨c).注意：一般說來,格中的∨和∧運(yùn)算不滿足分配律.

目前十二頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21二、子格設(shè)(L,∧,∨)是一個格，S是L的一個子集，(S,∧,∨)稱為(L,∧,∨)的一個子格，當(dāng)且僅當(dāng)在運(yùn)算∧,∨下，S是封閉的。目前十三頁\總數(shù)四十二頁\編于七點(diǎn)

e

fg

bd

c

ah

例：S={a,b,c,d,e,f,g,h}構(gòu)成格S1={a,b,d,f}和S2={c,e,g,h}和S3={a,b,c,d,e,g,h}都構(gòu)成格但S3不是S的子格目前十四頁\總數(shù)四十二頁\編于七點(diǎn)對偶式：格中元素用運(yùn)算符∧,∨連接起來的的一個表達(dá)式f，將f中的∧換成∨，將∨換成∧，如有0，1，將0換成1，將1換成0，所形成的表達(dá)式稱為f的對偶表達(dá)式記作f*

。對偶原理:對于<L,R>中任一真命題,其對偶命題也真。目前十五頁\總數(shù)四十二頁\編于七點(diǎn)三、格的同態(tài)與同構(gòu)定義：設(shè)<A1,?1>和<A2,?2>是兩個格，它們分別誘導(dǎo)的代數(shù)系統(tǒng)為<A1,∧1,∨1>和<A2,∧2,∨2>，若存在一個從A1到A2的映射f，使得對于任意的a，b∈A1，有f(a∧1b)＝f(a)∧2f(b)f(a∨1b)＝f(a)∨2f(b)則稱f是從<A1,∧1,∨1>到<A2,∧2,∨2>的格同態(tài)。亦稱<f(A1),?2>是<A1,?1>的格同態(tài)象。當(dāng)f是雙射的，則稱f是從<A1,∧1,∨1>到<A2,∧2,∨2>的格同構(gòu)，亦稱格<A1,?1>和<A2,?2>是同構(gòu)的。目前十六頁\總數(shù)四十二頁\編于七點(diǎn)定理：設(shè)f是格<A1,?1>到<A2,?2>格同態(tài)，則對任意的a，b∈A1，若a?1b，必有f(a)?2f(b)。目前十七頁\總數(shù)四十二頁\編于七點(diǎn)定理：設(shè)<A1,?1>和<A2,?2>是兩個格，f是從A1到A2雙射，則f是從<A1,?1>到<A2,?2>的格同構(gòu)，當(dāng)且僅當(dāng)，對任意的a，b∈A1，a?1b?f(a)?2f(b)。目前十八頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/216.2.分配格設(shè)<L,∧,∨>是格,若a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.目前十九頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21例a(c)bcdea(b)bcde(a)目前二十頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21例設(shè)A為任意一個集合，格<P(A),>是否是分配格？目前二十一頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21定理1所有鏈都是分配格。

目前二十二頁\總數(shù)四十二頁\編于七點(diǎn)定理2：

如果在一個格中交運(yùn)算對并運(yùn)算可分配，則并運(yùn)算對交運(yùn)算也是可分配的。反之亦然。目前二十三頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21定理3一個格是分配格的充分必要條件是該格中沒有任何子格與兩個五元素格中的任何一個同構(gòu)。目前二十四頁\總數(shù)四十二頁\編于七點(diǎn)定理4定理:

設(shè)格<L,∧,∨>是分配格，對任意a,b,c∈L，如果a∧c＝b∧c，a∨c＝b∨c則有a＝b。目前二十五頁\總數(shù)四十二頁\編于七點(diǎn)證明：若<L,∧,∨>是分配格，且a∧c＝b∧c，a∨c＝b∨c，則a＝a∧(a∨c)＝a∧(b∨c)＝(a∧b)∨(a∧c)＝(a∧b)∨(b∧c)＝b∧(a∨c)＝b∧(b∨c)＝b目前二十六頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21性質(zhì)（1）四個元素以下的格都是分配格；（2）五個元素的格僅有兩個格是非分配格，其余三個格(右圖(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde目前二十七頁\總數(shù)四十二頁\編于七點(diǎn)6.3有補(bǔ)格目前二十八頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21一、有界格1.設(shè)<L,?>是一個格，若存在元素a∈L，使得對任意x∈L，都有：a?x，則稱a為格<L,?>的全下界，記為02.設(shè)<L,?>是一個格，若存在元素a∈L，使得對任意x∈L，都有：x?a，則稱a為格<L,?>的全上界，記為13.具有全上界和全下界的格稱為有界格。記為<L,∧,∨,0,1>目前二十九頁\總數(shù)四十二頁\編于七點(diǎn)例：目前三十頁\總數(shù)四十二頁\編于七點(diǎn)定理：設(shè)<L,∧,∨,0,1>是有界格,則a∈L有

：a∧0=0,a∨0=a,a∧1=a,a∨1=1目前三十一頁\總數(shù)四十二頁\編于七點(diǎn)注意：（1）有限格L={a1,a2,…,an}是有界格,a1∧a2∧…∧an是L的全下界,a1∨a2∨…∨an是L的全上界.（2）0是關(guān)于∧運(yùn)算的零元,∨運(yùn)算的幺元；

1是關(guān)于∨運(yùn)算的零元,∧運(yùn)算的幺元.（3）對于涉及到有界格的命題,如果其中含有全下界0或全上界1,在求該命題的對偶命題時,必須將0替換成1,而將1替換成0.目前三十二頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21定理在格<L,?>中，全下界和全上界分別是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：設(shè)<L,?>是一個格，若格<L,?>的全上界和全下界存在，則必惟一。目前三十三頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21二、補(bǔ)元設(shè)<L,,>為有界格，1和0分別為它的全上界和全下界，a∈L。如果存在b∈L，使得ab=0，ab=1，則稱b為a的補(bǔ)元，記為。目前三十四頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21例如下圖有界格，求其所有元素的補(bǔ)元(如果有的話)。c0(b)db1

a0(a)deb1ac目前三十五頁\總數(shù)四十二頁\編于七點(diǎn)定理設(shè)<L,∧,∨,0,1>是有界分配格.若L中元素a存在補(bǔ)元,則存在惟一的補(bǔ)元.證：假設(shè)c是a的補(bǔ)元,則有

a∨c=1,a∧c=0,又知b是a的補(bǔ)元,故a∨b=1,a∧b=0從而得到a∨c=a∨b,a∧c=a∧b,

由于L是分配格,b=c.目前三十六頁\總數(shù)四十二頁\編于七點(diǎn)三、有補(bǔ)格若有界格<L,,>中的所有元素都存在補(bǔ)元，則稱<L,,>為有補(bǔ)格。目前三十七頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21四、有補(bǔ)分配格目前三十八頁\總數(shù)四十二頁\編于七點(diǎn)2023/5/21有補(bǔ)分配格：布爾格。由一個布爾格所誘導(dǎo)的一個代數(shù)系統(tǒng)可記為：<L,∧,∨,ˉ,0,1>。稱為布爾代數(shù)。目前三十九頁\總數(shù)四十二頁\編于七點(diǎn)6.4布爾代數(shù)定義：一個有補(bǔ)分配格是一個布爾代數(shù)，可記為<B,∧,∨,ˉ,0,1>。目前四十頁\總數(shù)四十二頁\編于七點(diǎn)設(shè)<B,∧,∨,ˉ,0,1>是一個布爾代數(shù)，a,b,c是集合B中任意元素，于是，它有如下性質(zhì)：（1）因?yàn)?lt;B,∧,∨>是一個格，所以有

a∧a＝a

a∨a＝a

a∧b＝b∧a

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

a∧(a∨b)＝a

a∨(a∧b)＝a（2）因?yàn)?lt;B,∧,∨>是分配格，所以有

a∧(b∨c)＝(a∧b)∨(a∧c)a∨(b∧c)＝(a∨b)∧(a∨c)（3）因?yàn)?lt;B,∧,∨,0,1>是有界格，所以有

a∧0＝0a∨1＝