離散數(shù)學(xué)課件第七章(第1講)

本章將介紹其他的代數(shù)系統(tǒng)——格和布爾代數(shù)，格論是數(shù)學(xué)的一個分支，不僅在近代解析集合有重要的作用，而且在計(jì)算機(jī)領(lǐng)域也有一定的用途；布爾代數(shù)形成比較早，在19世紀(jì)，就已經(jīng)有了相當(dāng)?shù)陌l(fā)展，布爾代數(shù)是研究和邏輯、集合等運(yùn)算有關(guān)的知識。7.1 格的概念7.2 分配格7.3有補(bǔ)格7.4 布爾代數(shù)第七章格與布爾代數(shù)§7.1格的概念例：偏序集(｛2,3,5,7,14,15,21｝,/)，“/”為整除關(guān)系。其hasze圖如下：｛2,7｝的最小上界、最大下界各為什么？｛2,3｝呢？｛5,14｝呢？｛2,7｝的最小上界為14。最大下界無。｛2,3｝的最小上界無，最大下界無。｛5,14｝的最小上界無，最大下界無。然而也存在這樣一類偏序集，它的每一對元素都有最小上界和最大下界，如：偏序集(｛1,2,3,4,6,8,12,24｝,/)：其Hasze圖如下：1、格

定義：設(shè)<A,≤>是一個偏序集，若對A中的任兩個元素a、b，都有最小上界和最大下界，則稱<A,≤>為格。其中上確界lub{a,b}，記為a∨b,稱為a和b的并。下確界glb{a,b}，記為a∧b,稱為a和b的交。將∨、∧，看作集合上的兩個二元運(yùn)算，故格<A,≤>所誘導(dǎo)的代數(shù)系統(tǒng)記作<A，∨，∧>。例：下述偏序集能構(gòu)成格的是（）(a)(b)(c)(d)bbcdefacdfabcdefghabcdef√ac2、對偶格

對偶格：若<A,≤>是一個偏序集，則<A,≥>也是一個偏序集，其中“≥”是“≤”的逆關(guān)系。若<A,≤>是一個格，則<A,≥>也是一個格，稱這兩個格互為對偶格。若將關(guān)于格<A,≤>的命題中符號≤，≥，∨、∧，分別用≥，≤，∧、∨，代替，則得到一個新的命題，稱這個新命題為原命題的對偶命題。定理：對于格中的一個真命題，其對偶命題亦真。3、格的性質(zhì)定理1：若<A，≤>是一個格，則對任意a、b

、c

A，有（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（1）a≤a∨b，b≤a∨b

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

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

，同理：a∧b≤b。（3）若a≤c且b≤c，則a∨b≤c

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

推論：在<A，≤>中，對于任意a，b

，c

A，如果b≤c，則a∨b≤a∨c，a∧b≤a∧c。

定理2：若<A，≤>是一個格，則對于任意a，b

A，以下三個公式等價；（1）a≤b

（2）a∨b=b

（3）a∧b=a（1）a≤b

（2）a∨b=b

（3）a∧b=a

證明：（1）（2）∵a≤b且偏序關(guān)系是自反的。∴b≤b，∴

a∨b≤b

又

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

設(shè)a∨b=b

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

類似可證（1）

（3）

定理3：<A，≤>是一個格，則對于任意a，b，c

A，滿足以下四個定律：（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定理4：設(shè)有格<A，≤>，對于任意a，b，c，d

A，如果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的一個上界，而a∨c是a和c的最小上界，∴必有a∨c≤b∨d。類似可以證明：a∧c≤b∧d

定理5：在一個格<A，≤>中，對于任意a，b，c

A，有下列分配不等式成立：（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）②對于①和②，有：a∨（b∧c）≤（a∨b）∧（a∨c）類似可證明：（a∧b）∨（a∧c）≤a∧（b∨c）

定義：設(shè)<A，≤>是一個格，設(shè)非空集合S且S

A，若對任意的a，b∈S，有a∧b∈S，a∨b∈S，則稱<S，

≤>是<A，≤>的子格。顯然，子格必是格。而格的某個子集構(gòu)成格，卻不一定是子格。4、子格例

：設(shè)〈A，≤〉是一個格，其中A={a