離散數(shù)學(xué)課件公開課一等獎?wù)n件省課獲獎?wù)n件

本章知識重點本章重點本章難點第10章格與布爾代數(shù)格概念；格性質(zhì)；幾個特殊格；布爾代數(shù)格概念與性質(zhì)；布爾代數(shù)格概念與性質(zhì)第1頁10.1格定義10.1.1格概念復(fù)習(xí)：關(guān)系--哈斯圖--集合上，下界--集合上，下確界--自反，反對稱，傳遞關(guān)系省略環(huán)，方向，間接弧關(guān)系圖可比，且比集合中元素均大/小最小上界，最大下界lub，glb偏序關(guān)系--序偶集合（笛卡爾積子集）事實上，本章是討論偏序集與代數(shù)系統(tǒng)間關(guān)聯(lián)性！第2頁10.1格定義10.1.1格概念設(shè)<L,?>為偏序集，若對于L中任意兩個元素均存在上，下確界，則稱<L,?>為格。判斷下列哈斯圖代表偏序集是否組成格?√√××√√√×第3頁10.1格定義10.1.1格概念由于在哈斯圖代表偏序關(guān)系中，任兩個元素上界是其向上交點，下界是其向下交點，故組成格偏序集應(yīng)當(dāng)滿足：

1）任兩點向上或向下有交點（存在上下界）

2）向上或向下交點間可比（存在上下確界）

3）若有x≤y，則必有：lub(x,y)=y，glb(x,y)=x第4頁10.1格定義10.1.2格中運算根據(jù)上，下確界惟一性，在格中，任意兩個元素均存在惟一元素:上，下確界與其對應(yīng)，故可以為格中兩個元素上，下確界是一種運算，并記為：

a∨b=lub(x,y)a∧b=glb(x,y)注意：這里∨，∧不是邏輯合，析取運算；

(提議與交或并有關(guān)聯(lián)記憶上/下界）

上界也許有最小，下界也許有最大。自然數(shù)公因子與公倍數(shù)最大，最小問題？第5頁10.1格定義10.1.3格誘導(dǎo)代數(shù)系統(tǒng)由于格中二元運算：求上，下確界（∨，∧）是封閉，于是就有了格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>。例設(shè)A={a,b},P(A)={φ,{a},,{a,b}},A上關(guān)系為集合包括關(guān)系：?顯然，集合包括關(guān)系?是自反，反對稱和傳遞，即為偏序關(guān)系，其哈斯圖如下所示：φ{(diào)a}{a,b}

<P(A),?>是格。第6頁10.1格定義10.1.3格誘導(dǎo)代數(shù)系統(tǒng)由<P(A),?>誘導(dǎo)代數(shù)系統(tǒng)運算∨,∧如下表所示：φ{(diào)a}{a,b}∨φ{(diào)a}{a,b}φ{(diào)a}{a,b}φ{(diào)a}{a,b}{a}{a}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}{a,b}第7頁10.1格定義10.1.3格誘導(dǎo)代數(shù)系統(tǒng)由<P(A),?>誘導(dǎo)代數(shù)系統(tǒng)運算∨,∧如下表所示：∧φ{(diào)a}{a,b}φ{(diào)a}{a,b}φ{(diào)a}{a}{a}{a,b}φφφφφφφφ任意格都能夠得到惟一誘導(dǎo)代數(shù)系統(tǒng)。φ{(diào)a}{a,b}第8頁10.1格定義10.1.4代數(shù)格設(shè)A為非空集合，A上二元運算*,o若滿足：

1)交換律

2)結(jié)合律

3)吸取律

?a,b

,c?A，有：a*b=b*aaob=boa(a*b)*c=a*(b*c)(aob)oc=ao(boc)a*(aob)=aao(a*b)=a則稱<A,*,o>為代數(shù)格。根據(jù)上述定義，我們懂得，我們學(xué)習(xí)過邏輯運算合，析取，集合運算交，并對于它們各自集合均組成代數(shù)格。第9頁10.2格主要性質(zhì)10.2.1格對偶原理

對偶格—若<L,?>是格，則偏序關(guān)系?逆關(guān)系?對L必也是格，稱<L,?>與<L,?>為對偶格。根據(jù)偏序關(guān)系逆關(guān)系性質(zhì)，上，下界是對偶；上下確界是對偶；最大，最小值也是對偶（?與?）。格對偶原理：設(shè)f是具有格命題，若將命題中?與?交換，∨與∧交換，所得命題稱為原命題對偶命題，記為f*。則對偶命題與原命題是等價命題。如：A∪φ=A對偶命題是：

A∩E=A。（最小元φ對偶于最大元E）基于此，格誘導(dǎo)代數(shù)系統(tǒng)中，兩個運算性質(zhì)一定對偶出現(xiàn)。第10頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>具有些什么性質(zhì)呢？

1)交換律

2)結(jié)合律

3)吸取律

4)冪等律a∨b=b∨aa∧b=b∧a(a∨b)∨c=a∨(b∨c)(a∧b)∧c=a∧(b∧c)a∨(a∧b)=aa∧(a∨b)=aa∨a=aa∧a=a證明1)交換律顯然！格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>滿足下列性質(zhì)?a,b,c?A，有：第11頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>滿足下列性質(zhì)：

2)結(jié)合律

3)吸取律

4)冪等律

?a,b,c?A，有：(a∨b)∨c=a∨(b∨c)(a∧b)∧c=a∧(b∧c)a∨(a∧b)=aa∧(a∨b)=aa∨a=aa∧a=a

2)結(jié)合律我們僅證：(a∨b)∨c=a∨(b∨c)我們利用偏序關(guān)系及最小上界概念來證明左右相等：

a∨ba?

(a∨b)∨c?a∨b?a

(a∨b)∨c?a∨b?b(a∨b)∨c?c(a∨b)∨c是{a,b,c}上界第12頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>滿足下列性質(zhì)：

2)結(jié)合律

?a,b,c?A，有：(a∨b)∨c=a∨(b∨c)(a∧b)∧c=a∧(b∧c)

(a∨b)∨c?a∨b?a

(a∨b)∨c?a∨b?b(a∨b)∨c?ca∨(b∨c)是{a,b∨c}最小上界(a∨b)∨ca∨(b∨c)…(1)?同理有：(a∨b)∨c?a∨(b∨c)..…(2)故有結(jié)論：(a∨b)∨c=a∨(b∨c)上界?最小上界利用偏序關(guān)系反對稱性來證明相等！(a∨b)∨c是{a,b,c}上界第13頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>滿足下列性質(zhì)：

3)吸取律

4)冪等律

?a,b,c?A，有：a∨(a∧b)=aa∧(a∨b)=aa∨a=aa∧a=a我們僅證：a∨(a∧b)=a由于最小上界是上界，故有：a∨(a∧b)?a…(1)又a?a，且：(a∧b)?

a，即a是它們上界上界?

最小上界，即：a∨(a∧b)?a…(2)故有：a∨(a∧b)=a第14頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>滿足下列性質(zhì)：

?a,b,c?A，有：我們僅證：a∨a=a由于最小上界也是上界，故有：a∨a?a…(1)又由自反性有a≥a，即a是a上界，而上界大于最小上界，故：a∨a?a…(2)于是：a∨a=a。

4)冪等律a∨a=aa∧a=a第15頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)事實上，在代數(shù)系統(tǒng)<A,*,o>中，若運算*,o滿足吸取律，則必滿足冪等律。吸取律冪等律

?a,b,c?A，有：a*(aob)=aao(a*b)=aa*a=aaoa=aa*a=a*(ao(a*b))=a*(ao(…))=a

同理可得：aoa=a第16頁10.2格主要性質(zhì)10.2.2格主要性質(zhì)

格

誘導(dǎo)代數(shù)系統(tǒng)（交換，結(jié)合，吸取,冪等性）

代數(shù)格（交換，結(jié)合，吸?。┐鷶?shù)系統(tǒng)也有冪等性

代數(shù)格與格誘導(dǎo)代數(shù)系統(tǒng)具有相同性質(zhì)。

事實上，能夠由代數(shù)格運算定義一種關(guān)系，它是一種偏序關(guān)系，且是一種格，而它誘導(dǎo)代數(shù)系統(tǒng)即是代數(shù)格。有關(guān)格等價定義：格中將∧和∨當(dāng)作二元運算，一定滿足交換律、結(jié)合律、冪等律和吸取律。反過來，若兩個二元運算滿足交換律、結(jié)合律和吸取律，就能夠定義一種格。第17頁10.3幾個特殊格10.3.1分派格格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>運算∨,∧滿足分派律（互相）。則稱為格為分派格。

P221頁示例結(jié)論：格中，一種運算對另一種運算可分派，則另一種運算對第一種運算一定也是可分派。分析：?a,b,c?L，若有：a∧(b∨c)=(a∧b)∨(a∧c)

則有：(a∨b)∧(a∨c)=((a∨b)∧a)∨((a∨b)∧c)(分派)=(a)∨((a∧c)∨(b∧c))(吸取)=a∨(b∧c))(結(jié)合，吸取)

故有：(a∨b)∧(a∨c)=a∨(b∧c))第18頁10.3幾個特殊格10.3.2有界格格<L,?>中若存在元素，與任意元素均可比，且為上界，則稱其為全上界，一般記為1（全下界0）?，F(xiàn)有全上界，又有全下界格為有界格。

P224頁示例結(jié)論：格中，若有全上界或全下界，必惟一。第19頁10.3幾個特殊格10.3.3有補格有界格，元素a,b滿足：交為全下界，并為全上界，則稱這兩個元素互為補元。a補元常記為a’。有界格元素補元個數(shù)不確定（0/1/2/..）。

P226頁示例若格中每個元素都存在補元，則稱其為有補格。顯然：全上界與全下界互為補元。顯然，a與a