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

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

1）任兩點(diǎn)向上或向下有交點(diǎn)（存在上下界）

2）向上或向下交點(diǎn)間可比（存在上下確界）

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

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

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

上界也許有最小，下界也許有最大。自然數(shù)公因子與公倍數(shù)最大，最小問題？第5頁10.1格定義10.1.3格誘導(dǎo)代數(shù)系統(tǒng)由于格中二元運(yùn)算：求上，下確界（∨，∧）是封閉，于是就有了格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>。例設(shè)A={a,b},P(A)={φ,{a},,{a,b}},A上關(guān)系為集合包括關(guān)系：?顯然，集合包括關(guān)系?是自反，反對(duì)稱和傳遞，即為偏序關(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)運(yùn)算∨,∧如下表所示：φ{(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)運(yùn)算∨,∧如下表所示：∧φ{(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上二元運(yùn)算*,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í)過邏輯運(yùn)算合，析取，集合運(yùn)算交，并對(duì)于它們各自集合均組成代數(shù)格。第9頁10.2格主要性質(zhì)10.2.1格對(duì)偶原理

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

A∩E=A。（最小元φ對(duì)偶于最大元E）基于此，格誘導(dǎo)代數(shù)系統(tǒng)中，兩個(gè)運(yùn)算性質(zhì)一定對(duì)偶出現(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)系反對(duì)稱性來證明相等！(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í)上，在代數(shù)系統(tǒng)<A,*,o>中，若運(yùn)算*,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í)上，能夠由代數(shù)格運(yùn)算定義一種關(guān)系，它是一種偏序關(guān)系，且是一種格，而它誘導(dǎo)代數(shù)系統(tǒng)即是代數(shù)格。有關(guān)格等價(jià)定義：格中將∧和∨當(dāng)作二元運(yùn)算，一定滿足交換律、結(jié)合律、冪等律和吸取律。反過來，若兩個(gè)二元運(yùn)算滿足交換律、結(jié)合律和吸取律，就能夠定義一種格。第17頁10.3幾個(gè)特殊格10.3.1分派格格<L,?>誘導(dǎo)代數(shù)系統(tǒng)<L,∨,∧>運(yùn)算∨,∧滿足分派律（互相）。則稱為格為分派格。

P221頁示例結(jié)論：格中，一種運(yùn)算對(duì)另一種運(yùn)算可分派，則另一種運(yùn)算對(duì)第一種運(yùn)算一定也是可分派。分析：?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幾個(gè)特殊格10.3.2有界格格<L,?>中若存在元素，與任意元素均可比，且為上界，則稱其為全上界，一般記為1（全下界0）。現(xiàn)有全上界，又有全下界格為有界格。

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

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