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

第六格與布爾代數(shù)演示文稿現(xiàn)在是1頁\一共有42頁\編輯于星期二（優(yōu)選）第六格與布爾代數(shù)現(xiàn)在是2頁\一共有42頁\編輯于星期二2023/4/24第6章格與布爾代數(shù)集合的表示方法2子格3特殊格4偏序格與代數(shù)格1格的性質(zhì)2布爾代數(shù)5現(xiàn)在是3頁\一共有42頁\編輯于星期二2023/4/246.1格的定義現(xiàn)在是4頁\一共有42頁\編輯于星期二2023/4/24一、定義設(shè)<L,?>是一個(gè)偏序集，如果對任意a,b∈L，{a,b}都有最大下界和最小上界存在，則稱<L,?>是格，簡稱L是格。若L為有限集，則稱格<L,?>為有限格?，F(xiàn)在是5頁\一共有42頁\編輯于星期二2023/4/24用a∨b表示{a,b}的最小上界，用a∧

b表示{a,b}的最大下界∨讀作“并”∧讀作“交”現(xiàn)在是6頁\一共有42頁\編輯于星期二現(xiàn)在是7頁\一共有42頁\編輯于星期二2023/4/24例（1）Sn表示n的所有因子的集合，D是一個(gè)整除關(guān)系，問此偏序集<Sn

，D>是否是一個(gè)格？（2）設(shè)A是一個(gè)集合，P(A)是A的冪集，是集合上的包含關(guān)系，問此偏序集<P(A),>是否是一個(gè)格？現(xiàn)在是8頁\一共有42頁\編輯于星期二定理(格的基本性質(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

現(xiàn)在是9頁\一共有42頁\編輯于星期二定理（格的性質(zhì)：序與運(yùn)算的關(guān)系）設(shè)L是格,則a,b∈L有

a?b

a∧b=a

a∨b=b現(xiàn)在是10頁\一共有42頁\編輯于星期二定理（格的保序性）設(shè)L是格,a,b,c,d∈L，若a?b且c?d,則

a∧c?b∧d,a∨c?b∨d現(xiàn)在是11頁\一共有42頁\編輯于星期二定理：設(shè)L是格,a,b,c∈L有

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

現(xiàn)在是12頁\一共有42頁\編輯于星期二2023/4/24二、子格設(shè)(L,∧,∨)是一個(gè)格，S是L的一個(gè)子集，(S,∧,∨)稱為(L,∧,∨)的一個(gè)子格，當(dāng)且僅當(dāng)在運(yùn)算∧,∨下，S是封閉的?，F(xiàn)在是13頁\一共有42頁\編輯于星期二

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的子格現(xiàn)在是14頁\一共有42頁\編輯于星期二對偶式：格中元素用運(yùn)算符∧,∨連接起來的的一個(gè)表達(dá)式f，將f中的∧換成∨，將∨換成∧，如有0，1，將0換成1，將1換成0，所形成的表達(dá)式稱為f的對偶表達(dá)式記作f*

。對偶原理:對于<L,R>中任一真命題,其對偶命題也真?，F(xiàn)在是15頁\一共有42頁\編輯于星期二三、格的同態(tài)與同構(gòu)定義：設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，它們分別誘導(dǎo)的代數(shù)系統(tǒng)為<A1,∧1,∨1>和<A2,∧2,∨2>，若存在一個(gè)從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)的?，F(xiàn)在是16頁\一共有42頁\編輯于星期二定理：設(shè)f是格<A1,?1>到<A2,?2>格同態(tài)，則對任意的a，b∈A1，若a?1b，必有f(a)?2f(b)?，F(xiàn)在是17頁\一共有42頁\編輯于星期二定理：設(shè)<A1,?1>和<A2,?2>是兩個(gè)格，f是從A1到A2雙射，則f是從<A1,?1>到<A2,?2>的格同構(gòu)，當(dāng)且僅當(dāng)，對任意的a，b∈A1，a?1b?f(a)?2f(b)?，F(xiàn)在是18頁\一共有42頁\編輯于星期二2023/4/246.2.分配格設(shè)<L,∧,∨>是格,若a,b,c∈L,有

a∧(b∨c)=(a∧b)∨(a∧c)a∨(b∧c)=(a∨b)∧(a∨c)則稱L為分配格.現(xiàn)在是19頁\一共有42頁\編輯于星期二2023/4/24例a(c)bcdea(b)bcde(a)現(xiàn)在是20頁\一共有42頁\編輯于星期二2023/4/24例設(shè)A為任意一個(gè)集合，格<P(A),>是否是分配格？現(xiàn)在是21頁\一共有42頁\編輯于星期二2023/4/24定理1所有鏈都是分配格。

現(xiàn)在是22頁\一共有42頁\編輯于星期二定理2：

如果在一個(gè)格中交運(yùn)算對并運(yùn)算可分配，則并運(yùn)算對交運(yùn)算也是可分配的。反之亦然?，F(xiàn)在是23頁\一共有42頁\編輯于星期二2023/4/24定理3一個(gè)格是分配格的充分必要條件是該格中沒有任何子格與兩個(gè)五元素格中的任何一個(gè)同構(gòu)。現(xiàn)在是24頁\一共有42頁\編輯于星期二定理4定理:

設(shè)格<L,∧,∨>是分配格，對任意a,b,c∈L，如果a∧c＝b∧c，a∨c＝b∨c則有a＝b?，F(xiàn)在是25頁\一共有42頁\編輯于星期二證明：若<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現(xiàn)在是26頁\一共有42頁\編輯于星期二2023/4/24性質(zhì)（1）四個(gè)元素以下的格都是分配格；（2）五個(gè)元素的格僅有兩個(gè)格是非分配格，其余三個(gè)格(右圖(a),(b)和(c))都是分配格。(a)(a)abcde(b)abcde(c)abcde現(xiàn)在是27頁\一共有42頁\編輯于星期二6.3有補(bǔ)格現(xiàn)在是28頁\一共有42頁\編輯于星期二2023/4/24一、有界格1.設(shè)<L,?>是一個(gè)格，若存在元素a∈L，使得對任意x∈L，都有：a?x，則稱a為格<L,?>的全下界，記為02.設(shè)<L,?>是一個(gè)格，若存在元素a∈L，使得對任意x∈L，都有：x?a，則稱a為格<L,?>的全上界，記為13.具有全上界和全下界的格稱為有界格。記為<L,∧,∨,0,1>現(xiàn)在是29頁\一共有42頁\編輯于星期二例：現(xiàn)在是30頁\一共有42頁\編輯于星期二定理：設(shè)<L,∧,∨,0,1>是有界格,則a∈L有

：a∧0=0,a∨0=a,a∧1=a,a∨1=1現(xiàn)在是31頁\一共有42頁\編輯于星期二注意：（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,在求該命題的對偶命題時(shí),必須將0替換成1,而將1替換成0.現(xiàn)在是32頁\一共有42頁\編輯于星期二2023/4/24定理在格<L,?>中，全下界和全上界分別是集合L的最小元和最大元，由于最大元和最小元的惟一性，有下面的定理：設(shè)<L,?>是一個(gè)格，若格<L,?>的全上界和全下界存在，則必惟一。現(xiàn)在是33頁\一共有42頁\編輯于星期二2023/4/24二、補(bǔ)元設(shè)<L,,>為有界格，1和0分別為它的全上界和全下界，a∈L。如果存在b∈L，使得ab=0，ab=1，則稱b為a的補(bǔ)元，記為?，F(xiàn)在是34頁\一共有42頁\編輯于星期二2023/4/24例如下圖有界格，求其所有元素的補(bǔ)元(如果有的話)。c0(b)db1

a0(a)deb1ac現(xiàn)在是35頁\一共有42頁\編輯于星期二定理設(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.現(xiàn)在是36頁\一共有42頁\編輯于星期二三、有補(bǔ)格若有界格<L,,>中的所有元素都存在補(bǔ)元，則稱<L,,>為有補(bǔ)格?，F(xiàn)在是37頁\一共有42頁\編輯于星期二2023/4/24四、有補(bǔ)分配格現(xiàn)在是38頁\一共有42頁\編輯于星期二2023/4/24有補(bǔ)分配格：布爾格。由一個(gè)布爾格所誘導(dǎo)的一個(gè)代數(shù)系統(tǒng)可記為：<L,∧,∨,ˉ,0,1>。稱為布爾代數(shù)。現(xiàn)在是39頁\一共有42頁\編輯于星期二6.4布爾代數(shù)定義：一個(gè)有補(bǔ)分配格是一個(gè)布爾代數(shù)，可記為<B,∧,∨,ˉ,0,1>。現(xiàn)在是40頁\一共有42頁\編輯于星期二設(shè)<B,∧,∨,ˉ,0,1>是一個(gè)布爾代數(shù)，a,b,c是集合B中任意元素，于是，它有如下性質(zhì)：（1）因?yàn)?lt;B,∧,∨>是一個(gè)格，所以有

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＝