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

第七格與布爾代數(shù)演示文稿1現(xiàn)在是1頁(yè)\一共有36頁(yè)\編輯于星期一（優(yōu)選）第七格與布爾代數(shù)現(xiàn)在是2頁(yè)\一共有36頁(yè)\編輯于星期一3定義設(shè)<A,>為偏序集,BA,yA.(1)若x(xB→xy)成立,則稱y為B的上界;(2)若x(xB→yx)成立,則稱y為B的下界;(3)令C={y|y為B的上界},若C有最小元，則稱該最小元為B的最小上界或上確界,記為L(zhǎng)UB(上確界)(4)令D={y|y為B的下界},若D有最大元，則稱該最大元為為B的最大下界或下確界,記為GLB(下確界)

復(fù)習(xí)偏序關(guān)系中的上界，下界，上確界與下確界現(xiàn)在是3頁(yè)\一共有36頁(yè)\編輯于星期一4例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”為整除關(guān)系。其hasze圖如下：｛2,7｝的最小上界、最大下界各為什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界為14。最大下界無(wú)。｛2,3｝的最小上界無(wú)，最大下界無(wú)。｛5,14｝的最小上界無(wú)，最大下界無(wú)?！?格的概念

現(xiàn)在是4頁(yè)\一共有36頁(yè)\編輯于星期一5然而也存在這樣一類偏序集，它的每一對(duì)元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze圖如下：現(xiàn)在是5頁(yè)\一共有36頁(yè)\編輯于星期一6一、格1．定義：設(shè)<A,≤>是一個(gè)偏序集，若對(duì)A中的任兩個(gè)元素a、b，都有最小上界和最大下界，則稱 <A,≤>為格。其中上確界lub{a,b}，記為a∨b,稱為a和b的并。下確界glb{a,b}，記為a∧b,稱為a和b的交。將∨、∧，看作集合上的兩個(gè)二元運(yùn)算，故格<A,≤>所誘導(dǎo)的代數(shù)系統(tǒng)記作<A，∨，∧>?，F(xiàn)在是6頁(yè)\一共有36頁(yè)\編輯于星期一7一、格下述偏序集能構(gòu)成格的是（？）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac現(xiàn)在是7頁(yè)\一共有36頁(yè)\編輯于星期一8一、格2、對(duì)偶格：若<A,≤>是一個(gè)偏序集，則<A,≥>也是一個(gè)偏序集，其中“≥”是“≤”的逆關(guān)系。若<A,≤>是一個(gè)格，則<A,≥>也是一個(gè)格，稱這兩個(gè)格互為對(duì)偶。若將關(guān)于格<A,≤>的命題中符號(hào)≤，≥，∨、∧，分別用≥，≤，∧、∨，代替，則得到一個(gè)新的命題，稱這個(gè)新命題為原命題的對(duì)偶命題。定理：對(duì)于格中的一個(gè)真命題，其對(duì)偶命題亦真。

現(xiàn)在是8頁(yè)\一共有36頁(yè)\編輯于星期一9二、格的性質(zhì)定理1：若<A，≤>是一個(gè)格，則對(duì)任意a、b

、cA，有（1）a≤a∨b，b≤a∨b

（2）a∧b≤a，a∧b≤b（3）若a≤c且b≤c，則a∨b≤c（4）若c≤a且c≤b，則c≤a∧b現(xiàn)在是9頁(yè)\一共有36頁(yè)\編輯于星期一10二、格的性質(zhì)（1）a≤a∨b，b≤a∨b

證明：因a∨b=lub{a，b}，它顯然是a的一個(gè)上界，∴a≤a∨b

，同理：b≤a∨b。（2）a∧b≤a，a∧b≤b證明：因a∧b=glb{a，b}，它顯然是a的一個(gè)下界，∴a∧b≤a

，同理：a∧b≤b?，F(xiàn)在是10頁(yè)\一共有36頁(yè)\編輯于星期一11二、格的性質(zhì)（3）若a≤c且b≤c，則a∨b≤c

證明：∵a≤c且b≤c，由上界的定義知，c是{a，b}的一個(gè)上界，而a∨b是{a，b}的最小上界，∴a∨b≤c。（4）若c≤a且c≤b，則c≤a∧b證明：∵c≤a且c≤b，由下界的定義知，c是{a，b}的一個(gè)下界，而a∧b是{a，b}的最大下界，∴c≤a∧b。

現(xiàn)在是11頁(yè)\一共有36頁(yè)\編輯于星期一12二、格的性質(zhì)推論：在<A，≤>中，對(duì)于任意a，b

，cA，如果b≤c，則a∨b≤a∨c，a∧b≤a∧c。定理2：若<A，≤>是一個(gè)格，則對(duì)于任意a，bA，以下三個(gè)公式等價(jià)；（1）a≤b

（2）a∨b=b

（3）a∧b=a現(xiàn)在是12頁(yè)\一共有36頁(yè)\編輯于星期一13二、格的性質(zhì)（1）a≤b

（2）a∨b=b

（3）a∧b=a證明：（1）（2）∵a≤b且偏序關(guān)系是自反的?！郻≤b，∴

a∨b≤b

又

b≤a∨b成立∴a∨b=b（偏序關(guān)系是反對(duì)稱的）設(shè)a∨b=b

∵a≤a∨b成立，將a∨b=b代入a≤a∨b得：a≤b

類似可證（1）（3）現(xiàn)在是13頁(yè)\一共有36頁(yè)\編輯于星期一14二、格的性質(zhì)定理3：<A，≤>是一個(gè)格，則對(duì)于任意a，b，cA，滿足以下四個(gè)定律：（1）交換律：a∨b=b∨a

a∧b=b∧a（2）吸收律：a∨（a∧b）=aa∧（a∨b

）=a（3）結(jié)合律：a∨（b∨c）=（a∨b）∨c，

a∧（b∧c）=（a∧b

）∧c（4）等冪律：a∨a=a

a∧a=a現(xiàn)在是14頁(yè)\一共有36頁(yè)\編輯于星期一15二、格的性質(zhì)定理4：設(shè)有格<A，≤>，對(duì)于任意a，b，c，dA，如果a≤b和c≤d，則（1）a∨c≤b∨d，（2）a∧c≤b∧d證：∵b≤b∨d，d≤b∨d

，而a≤b，c≤d，∴由傳遞性可得：a≤b∨d

，c≤b∨d，這就表明b∨d是a和c的一個(gè)上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。類似地可以證明：a∧c≤b∧d

現(xiàn)在是15頁(yè)\一共有36頁(yè)\編輯于星期一16二、格的性質(zhì)定理5：在一個(gè)格<A，≤>中，對(duì)于任意a，b，cA，有下列分配不等式成立：（1）a∨（b∧c）≤（a∨b）∧（a∨c）（2）a∧（b∨c）≥（a∧b）∨（a∧c）證：由定理1，（1）（2）知：a≤a∨b和a≤a∨c，可得：

a≤（a∨b）∧（a∨c），①又∵b∧c≤b≤a∨b和b∧c≤c≤a∨c∴b∧c≤（a∨b）∧（a∨c）②對(duì)于①和②，有：a∨（b∧c）≤（a∨b）∧（a∨c）利用對(duì)偶原理，即得：（a∧b）∨（a∧c）≤a∧（b∨c）

現(xiàn)在是16頁(yè)\一共有36頁(yè)\編輯于星期一17定義設(shè)<A，≤>是一個(gè)格，設(shè)非空集合S且S

A,若對(duì)任意的a,b∈S,有a∧b∈S,a∨b∈S,則稱〈S,≤〉是<A，≤>的子格。顯然，子格必是格。而格的某個(gè)子集構(gòu)成格，卻不一定是子格。三、子格現(xiàn)在是17頁(yè)\一共有36頁(yè)\編輯于星期一18【例】設(shè)〈A,≤〉是一個(gè)格，其中A={a,b,c,d,e},其哈斯圖如圖所示。S1={a,b,c,d}，S2={a,b,c,e},則〈S1,≤〉是〈A,≤〉是一個(gè)子格，〈S2,≤〉不是〈A,≤〉是一個(gè)子格，因?yàn)閎∧c=d∈S2，〈S2,≤〉不是子格。三、子格現(xiàn)在是18頁(yè)\一共有36頁(yè)\編輯于星期一19§2分配格

對(duì)格<A,≤>中的任意元素a,b,cA，必有a(bc)≤(ab)(ac)(ab)(ac)≤a(bc）當(dāng)上述兩式中等號(hào)成立的時(shí)候，就得到一類特殊的格?！抖x》設(shè)<A,,>是由格<A,≤>所誘導(dǎo)的代數(shù)系統(tǒng)。如果對(duì)任意的a,b,cA，滿足：

a(bc)=(ab)(ac)a(bc)=(ab)(ac)

則稱<A,≤>是分配格?，F(xiàn)在是19頁(yè)\一共有36頁(yè)\編輯于星期一20例：判斷圖示的格是否是分配格

∵a3∧（a4∨a5）=a3∧a1=a3

（a3∧a4）∨（a3∧a5）=a4∨a6=a4

∴所示的格不是分配格。

§2分配格

現(xiàn)在是20頁(yè)\一共有36頁(yè)\編輯于星期一21§2分配格《定理》如果格中交對(duì)并是分配的，那么并對(duì)交也是分配的，反之亦然。證明：已知a(bc)＝(ab)(ac)

(ab)(ac)=((ab)a)((ab)c) =a((ab)c) =a((ac)(bc)) =(a(ac))(bc) =a(bc)即：并對(duì)交也是分配的?，F(xiàn)在是21頁(yè)\一共有36頁(yè)\編輯于星期一22§2分配格《定理》每個(gè)鏈均是分配格。證明：設(shè)<A,≤>是鏈。對(duì)任意a，b，cA(1)若a≤b或a≤c，則a(bc)＝a，

(ab)(ac)＝a即：a(bc)＝(ab)(ac)(2)若a≥b且a≥c，則

a(bc)＝bc，

(ab)(ac)＝bc即：a(bc)＝(ab)(ac)。得證?，F(xiàn)在是22頁(yè)\一共有36頁(yè)\編輯于星期一23定理：設(shè)<A，≤

>是一個(gè)分配格，則對(duì)于任意a，b，cA，如果有a∧b=a∧c和a∨b=a∨c成立，則必有b=c?！?分配格

證：∵（a∧b）∨c=（a∧c）∨c=c（a∧b）∨c=（a∨c）∧（b∨c）=（a∨b）∧（b∨c）=（b∨a）∧（b∨c）=b∨（a∧c）=b∨(a∧b)=b∴b=c

現(xiàn)在是23頁(yè)\一共有36頁(yè)\編輯于星期一24§2分配格《定義》設(shè)<A,,>是由格<A,≤>所誘導(dǎo)的代數(shù)系統(tǒng)。如對(duì)A中任意a，b，c，當(dāng)b≤a時(shí)，有：

a(bc)＝b(ac)則稱<A,≤>為模格。現(xiàn)在是24頁(yè)\一共有36頁(yè)\編輯于星期一25§2分配格《定理》分配格是模格。證明：由于a(bc)＝(ab)(ac)若b≤a，則ab=b，代入上式得

a(bc)＝b(ac)

∴分配格是模格現(xiàn)在是25頁(yè)\一共有36頁(yè)\編輯于星期一26§3有補(bǔ)格《定義》設(shè)<A,≤>是一個(gè)格，如果存在元素aA，對(duì)于任意的xA，都有：a≤x

則稱a為格<A,≤>的全下界，記格的全下界為0?！抖x》設(shè)<A,≤>是一個(gè)格，如果存在元素bA，對(duì)于任意的xA，都有：x≤b

則稱b為格<A,≤>的全上界，記格的全上界為1?，F(xiàn)在是26頁(yè)\一共有36頁(yè)\編輯于星期一27§3有補(bǔ)格《定理》如果格<A,≤>有全上界（全下界），那么它是唯一的。證明：（反證法）設(shè)有兩個(gè)全上界a和b，則由定義

a≤b，且b≤a，由“≤”的反對(duì)稱性，a＝b。《定義》設(shè)<A,≤>是一個(gè)格，如果格中存在全上界和全下界，則稱該格為有界格?，F(xiàn)在是27頁(yè)\一共有36頁(yè)\編輯于星期一28§3有補(bǔ)格《定理》如果<A,≤>是有界格，全上界和全下界分別是1和0，則對(duì)任意元素aA，有：

a1=1a=1，a1=1a=a，

a0=0a=a，a0=0a=0。證明：因?yàn)?≤a1， 又因(a1)A且1是全上界，∴a1≤1，

∴a1=1。由交換律：1a＝a1=1。 因?yàn)閍≤a，a≤1，∴aa≤a1，即：a≤a1，又a1≤a，∴a1=a。仿此可得另兩式?，F(xiàn)在是28頁(yè)\一共有36頁(yè)\編輯于星期一29§3有補(bǔ)格《定義》設(shè)<A,≤>是一個(gè)有界格，對(duì)于A中的一個(gè)元素a，如果存在bA，使得ab=1和ab=0，則稱元素b是元素a的補(bǔ)元。討論定義：（1）∵和是可交換的，∴補(bǔ)元是相互的。

（2）

，即在有界格中，1和0互為補(bǔ)元；

（3）由定義可知A中一個(gè)元素的補(bǔ)元不一定是唯一的；可能存在多個(gè)補(bǔ)元，也可能不存在補(bǔ)元?，F(xiàn)在是29頁(yè)\一共有36頁(yè)\編輯于星期一30§3有補(bǔ)格《定義》在一個(gè)有界格中，如果每個(gè)元素都至少有一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格。討論定義：（1）在有補(bǔ)格中，每一個(gè)元素一定存在補(bǔ)元（不一定是一個(gè)補(bǔ)元）；（2）有補(bǔ)格一定是有界格，而有界格不一定是有補(bǔ)格?，F(xiàn)在是30頁(yè)\一共有36頁(yè)\編輯于星期一31如圖所示的格，是有補(bǔ)格嗎？該格是有界格，卻不是有補(bǔ)格?！?有補(bǔ)格現(xiàn)在是31頁(yè)\一共有36頁(yè)\編輯于星期一32§3有補(bǔ)格《定理》在有界分配格中，若有一個(gè)元素有補(bǔ)元，則