離散數(shù)學(xué)(賈振華主編)教學(xué)課件 第九章格與代數(shù).ppt

《離散數(shù)學(xué)(賈振華主編)教學(xué)課件 第九章格與代數(shù).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第9章格與代數(shù)本章學(xué)習(xí)目標(biāo)本章將介紹另外的代數(shù)系統(tǒng)——格和布爾代數(shù)，格論大體形成于20世紀(jì)30年代，它是數(shù)學(xué)的一個(gè)分支，不僅在近代解析集合有重要的作用，而且在計(jì)算機(jī)領(lǐng)域也有一定的用途；布爾代數(shù)形成比較早，在19世紀(jì)，就已經(jīng)有了相當(dāng)?shù)陌l(fā)展，布爾代數(shù)是研究和邏輯、集合等運(yùn)算有關(guān)的知識。（1）掌握格的定義和性質(zhì)（2）掌握分配格與有補(bǔ)格的概念和性質(zhì)（3）掌握布爾代數(shù)的概念和性質(zhì)（4）掌握布爾表達(dá)式的概念和性質(zhì)，掌握同構(gòu)的概念及其判定第9章格與代數(shù)9.1格的定義和性質(zhì)9.2分配格和有補(bǔ)格9.3布爾代數(shù)第9章格與代數(shù)

2、9.1格的定義和性質(zhì)9.1.1格的定義定理9.1(對偶原理)一個(gè)關(guān)于格的上、下確界以及偏序關(guān)系≤，≥的命題是真命題，當(dāng)且僅當(dāng)將命題中的上確界換成下確界、下確界換成上確界、將關(guān)系“≤”換成“≥”、將“≥”換成“≤”后是一個(gè)真命題。定義9.1設(shè)是一個(gè)偏序集，如果A中任意兩個(gè)元素x，y∈A，都有最小上界（上確界）和最大下界（下確界），則稱為格。第9章格與代數(shù)9.1格的定義和性質(zhì)9.1.2格的性質(zhì)定理9.3在一個(gè)格中，對于a，b，c，d∈A，如果a≤b，c≤d則，a∨c≤b∨da∧c

3、≤b∧d定理9.2在一個(gè)格中，對任意的a，b∈A，都有a≤a∨bb≤a∨ba∧b≤aa∧b≤b第9章格與代數(shù)9.1格的定義和性質(zhì)9.1.2格的性質(zhì)定理9.5在一個(gè)格中，對任意的a，b，c∈A，都有a∨（b∧c）≤（a∨b）∧（a∨c）（a∧b）∨（a∧c）≤a∧（b∨c）定理9.4設(shè)是一個(gè)格，由格所誘導(dǎo)的代數(shù)系統(tǒng)為，則對任意的a，b，c，d∈A，有如下的規(guī)律：（1）a∨b=b∨a(交換律)（2）a∨（b∨c）=（a∨b）∨c(結(jié)合律)（3）a∨a=a(

4、等冪律)（4）a∨（a∧b）=a(吸收律)第9章格與代數(shù)9.1格的定義和性質(zhì)9.1.2格的性質(zhì)定理9.7設(shè)是一個(gè)格，那么，對于任意的a，b,c∈A，有a≤c?a∨（b∧c）≤（a∨b）∧c定理9.6設(shè)是一個(gè)格，那么,對于任意的a，b，c∈A有，a≤b等價(jià)于a∧b=a等價(jià)于a∨b=b第9章格與代數(shù)9.1格的定義和性質(zhì)9.1.3格與代數(shù)系統(tǒng)的對應(yīng)定理9.8任何一個(gè)偏序格與一代數(shù)格等價(jià)。定義9.2設(shè)L是非空集合，在其上定義一個(gè)“加法”運(yùn)算和一個(gè)“乘法”運(yùn)算，即“+”和“*”。并且滿足交換律、

5、結(jié)合律和吸收律。代數(shù)系統(tǒng)就稱為代數(shù)格。定義9.3設(shè)〈L，*，+〉是一個(gè)格，S是L的子集?！碨，*，+〉是L的子格，當(dāng)且僅當(dāng)運(yùn)算*和+在S上是封閉的。第9章格與代數(shù)9.2分配格和有補(bǔ)格9.2.1分配格定義9.4設(shè)是由格所誘導(dǎo)的代數(shù)系統(tǒng)。如果對任意的a，b，c∈A，滿足a∧（b∨c）=（a∧b）∨（a∧c）（交運(yùn)算對于并運(yùn)算可分配）和a∨（b∧c）≤（a∨b）∧（a∨c）（并運(yùn)算對于交運(yùn)算可分配）則稱是分配格.第9章格與代數(shù)9.2分配格和有補(bǔ)格9.2.2有補(bǔ)格定

6、義9.5設(shè)是一個(gè)格，如果存在元素a∈A，對于任意的x∈A，都有a≤x，則稱a為格的全下界，記格的全下界為0；同理若存在元素b∈A，對于任意的x∈A，都有x≤b，稱b為格的全上界，記格的全上界為1。定義9.6如果一個(gè)格中存在全下界和全上界，則稱該格為有界格。第9章格與代數(shù)9.2分配格和有補(bǔ)格9.2.2有補(bǔ)格定義9.5設(shè)是一個(gè)格，如果存在元素a∈A，對于任意的x∈A，都有a≤x，則稱a為格的全下界，記格的全下界為0；同理若存在元素b∈A，對于任意的x∈A，都有

7、x≤b，稱b為格的全上界，記格的全上界為1。定義9.6如果一個(gè)格中存在全下界和全上界，則稱該格為有界格。第9章格與代數(shù)9.2分配格和有補(bǔ)格9.2.2有補(bǔ)格定理9.12一個(gè)格若有全下界，則其是唯一的；同理若一個(gè)格若有全上界，則其也是唯一的。定義9.7設(shè)是一個(gè)有界格，∧和∨是對應(yīng)的二元運(yùn)算，0是其全下界，而1是其全上界，對于x，y∈A，有x∨y=1，x∧y=0，稱y為x的補(bǔ)元，簡稱補(bǔ)第9章格與代數(shù)9.2分配格和有補(bǔ)格9.2.2有補(bǔ)格定義9.8在一個(gè)有界格中，如果每個(gè)

8、元素都至少有一個(gè)補(bǔ)元素，則稱此格為有補(bǔ)格。定理9.13設(shè)即是一個(gè)有界格，同時(shí)還是一個(gè)分配格，那么若某一個(gè)元素有補(bǔ)元素，則其補(bǔ)元素必是唯一的。第9章格與代數(shù)9.3布爾代數(shù)9.3.1布爾代數(shù)的概念定義9.9設(shè)即是一個(gè)有補(bǔ)格，同時(shí)還是一個(gè)分配格，那么稱為布爾格。定義9.10由布爾格，誘導(dǎo)出的代數(shù)系統(tǒng)為布爾代數(shù)。定理9.14設(shè)為布爾代數(shù)，對任意的元a∈G，