第10章 格與布爾代數(shù)-《離散數(shù)學(xué)（微課版）》教學(xué)課件

《離散數(shù)學(xué)》第十章格與布爾代數(shù)內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6本章導(dǎo)讀從數(shù)學(xué)的觀點(diǎn)看，數(shù)學(xué)有序結(jié)構(gòu)、代數(shù)結(jié)構(gòu)、拓?fù)浣Y(jié)構(gòu)三個(gè)基本的結(jié)構(gòu)。格是一種兼有序和代數(shù)的重要結(jié)構(gòu)，它在抽象代數(shù)、射影幾何、點(diǎn)集論、拓?fù)鋵W(xué)、泛函分析、邏輯和概率論、模糊數(shù)學(xué)等許多領(lǐng)域都有廣泛應(yīng)用。格的概念是在19世紀(jì)末，由戴德金和施羅德分別基于對(duì)偶群和邏輯代數(shù)兩個(gè)方向得出的，但直到1933～1938年，經(jīng)伯克霍夫、奧爾等人的工作才確立了格在代數(shù)學(xué)中的地位。戴德金伯克霍夫歷史人物布爾研究人的思維規(guī)律，于1854年出版《思維規(guī)律的研究》，建立了邏輯代數(shù)，即布爾代數(shù)。布爾代數(shù)可看作一種特殊的格（盡管它的出現(xiàn)比格早），在計(jì)算機(jī)科學(xué)中具有非常重要的應(yīng)用，如在密碼學(xué)、計(jì)算機(jī)語(yǔ)義學(xué)、開關(guān)理論、計(jì)算機(jī)理論和邏輯設(shè)計(jì)以及其他一些科學(xué)和工程領(lǐng)域中，都有直接應(yīng)用。喬治·布爾(1815～1864），英國(guó)數(shù)學(xué)家，布爾代數(shù)的創(chuàng)始人。重點(diǎn)1格和子格的判定2根據(jù)格的定義和性質(zhì)證明3特殊格之間的關(guān)系及判定定理4子格的求解、補(bǔ)元的求解5同態(tài)和同構(gòu)的證明難點(diǎn)1利用格的定義證明相關(guān)性質(zhì)2格中運(yùn)算定律的驗(yàn)證3格中運(yùn)算定律的綜合證明

學(xué)習(xí)要求內(nèi)容導(dǎo)航CONTENTS歷史人物本章導(dǎo)讀及學(xué)習(xí)要求格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6布爾1815年11月2日生于英格蘭的林肯小鎮(zhèn)，父親是一個(gè)皮匠。1835年他開辦了自己的學(xué)校。

在備課的時(shí)候，布爾不滿意當(dāng)時(shí)的數(shù)學(xué)課本，便決定閱讀偉大數(shù)學(xué)家的論文。布爾撰寫了微分方程和差分方程的課本，這些課本在英國(guó)一直使用到19世紀(jì)末。1847年，布爾出版了《邏輯的數(shù)學(xué)分析》；1849年，他被任命位于愛(ài)爾蘭科克的皇后學(xué)院的數(shù)學(xué)教授。1854年，他出版了《思維規(guī)律的研究》這是他最著名的著作。

在這本書中布爾介紹了現(xiàn)在以他的名字命名的布爾代數(shù)。1864年，布爾死于肺炎，這是由于他在暴風(fēng)雨天氣中奔波后盡管已經(jīng)濕淋淋的仍堅(jiān)持上課引起的。喬治·布爾(1815～1864），英國(guó)數(shù)學(xué)家，布爾代數(shù)的創(chuàng)始人。布爾布爾在1855年結(jié)婚，他的妻子瑪麗·埃弗雷斯特是皇后學(xué)院一位希臘文教授的侄女。布爾的后代中有眾多的科學(xué)家和各界名人。他有五個(gè)女兒，三女兒Alicia是四維幾何的重要貢獻(xiàn)者，四女兒Lucy是英國(guó)第一個(gè)女化學(xué)教授，五女兒EthelLilian是《牛虻》作者。布爾是被稱為“深度學(xué)習(xí)之父”的GeoffreyHinton的高(外)祖父（即布爾大女兒的曾孫）。他還有兩個(gè)曾外孫WilliamHinton(中文名：韓丁)和JoanHinton（中文名：寒春）與中國(guó)有很大的淵源。寒春和他的丈夫陽(yáng)早為中國(guó)的農(nóng)業(yè)發(fā)展做出了很大貢獻(xiàn)，是我國(guó)首張綠卡的獲得者。她一直生活在中國(guó)，直到2010年在北京去世。喬治·布爾(1815～1864），英國(guó)數(shù)學(xué)家，布爾代數(shù)的創(chuàng)始人。戴德金1831年10月6日出生于德國(guó)薩克森州東部城市不倫瑞克，父母都是知識(shí)分子。戴德金早年在不倫瑞克理工學(xué)院學(xué)習(xí)，1850年轉(zhuǎn)入哥廷根大學(xué)，師從高斯，是高斯的關(guān)門弟子，兩年后即完成了關(guān)于歐拉積分的博士論文，獲得哲學(xué)博士學(xué)位。博士畢業(yè)后，戴德金花兩年時(shí)間去柏林繼續(xù)深造，并在1854年夏取得大學(xué)執(zhí)教資格。戴德金先后在哥廷根大學(xué)、蘇黎世工科學(xué)校任教，在上課的同時(shí)也繼續(xù)學(xué)習(xí)，1862年，戴德金回到母校不倫瑞克理工學(xué)院任職，直到去世。戴德金終生未婚，一直保持健康的身心，直到1916年2月12日平靜安詳?shù)嘏c世長(zhǎng)辭。

尤利烏斯·威廉·理查德·戴德金（1831-1916），偉大的德國(guó)數(shù)學(xué)家、理論家和教育家，近代抽象數(shù)學(xué)的先驅(qū)。戴德金戴德金受到了高斯、狄利克雷和黎曼很深的影響，他負(fù)責(zé)編輯過(guò)狄利克雷、高斯、黎曼的全集。戴德金和集合論創(chuàng)始人康托爾一直保持著友誼，相互敬重，也是最早支持康托爾無(wú)窮集合工作的數(shù)學(xué)家之一。戴德金和海爾里?！ろf伯合作，在黎曼曲面上應(yīng)用理想論的結(jié)果。當(dāng)時(shí)韋伯是哥尼斯堡大學(xué)的老師，在講課過(guò)程當(dāng)中，他介紹了戴德金的思想，從而許多學(xué)生受到了戴德金的思想影響，其中就包括著名數(shù)學(xué)家大衛(wèi)·希爾伯特。1900年，希爾伯特在國(guó)際數(shù)學(xué)家大會(huì)上高度贊揚(yáng)了戴德金的工作。艾米·諾特與奧伊斯坦·奧爾共同編輯了戴德金的全集，也發(fā)展了戴德金的理論，包括在格論方面的工作。

尤利烏斯·威廉·理查德·戴德金（1831-1916），偉大的德國(guó)數(shù)學(xué)家、理論家和教育家，近代抽象數(shù)學(xué)的先驅(qū)。戴德金戴德金的主要成就是在代數(shù)理論方面。他研究過(guò)任意域、環(huán)、群、結(jié)構(gòu)及模等問(wèn)題，他基于對(duì)偶群提出了格的概念。并在授課時(shí)率先引入了環(huán)（域）的概念，給理想子環(huán)下了一般定義。在實(shí)數(shù)和連續(xù)性理論方面，他提出“戴德金分割”，給出了無(wú)理數(shù)及連續(xù)性的純算術(shù)的定義。1872年，他的《連續(xù)性與無(wú)理數(shù)》出版，使他成為現(xiàn)代實(shí)數(shù)理論的奠基人之一在代數(shù)數(shù)論方面，他建立了現(xiàn)代代數(shù)數(shù)和代數(shù)數(shù)域的理論，將庫(kù)默爾的理想數(shù)加以推廣，引出了現(xiàn)代的“理想”概念，并得到了代數(shù)整數(shù)環(huán)上理想的惟一分解定理。今天把滿足理想惟一分解條件的整環(huán)稱為“戴德金整環(huán)”。他在數(shù)論上的貢獻(xiàn)對(duì)19世紀(jì)數(shù)學(xué)產(chǎn)生了深刻影響。

尤利烏斯·威廉·理查德·戴德金（1831-1916），偉大的德國(guó)數(shù)學(xué)家、理論家和教育家，近代抽象數(shù)學(xué)的先驅(qū)。內(nèi)容導(dǎo)航CONTENTS格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6歷史人物本章導(dǎo)讀及學(xué)習(xí)要求引言格與布爾代數(shù)也是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng)，這兩個(gè)代數(shù)系統(tǒng)與群、環(huán)、域之間有很多聯(lián)系，但也存在著一個(gè)重要區(qū)別：在格與布爾代數(shù)中，偏序關(guān)系具有重要意義。格有多種等價(jià)定義，但主要分為兩類，一類是從偏序集的角度給出的，這種定義可以借助哈斯圖表示，因而比較直觀，易于理解，這樣定義的格稱為偏序格；另一類是從代數(shù)系統(tǒng)的角度來(lái)給出的，可以借助代數(shù)系統(tǒng)的子代數(shù)、同態(tài)與同構(gòu)等工具來(lái)討論其性質(zhì)，這樣定義的格稱為代數(shù)格，代數(shù)格的定義又可分為八條件、六條件、四條件、三條件、二條件甚至一條件等幾種。格的定義

所有的全序集（或鏈）都是格為方便說(shuō)明，可把由偏序集定義的格稱為偏序格。

格的判定

格的判定

格的判定例10.2判斷如圖所示哈斯圖對(duì)應(yīng)的偏序集是否是格。(a)

a

bcdefg(a)

(b)

abcde

(c)

a

b

c

d

e(e)

bc

d

e

a

(d)

b

c

deb

a

(f)

c

e

f

d

a格的判定

a

(g)

bd

f

h

c

e

g

h

a

d

b

c

f

(h)

g

e

(i)

ab

c

d

e

f

fb

(j)

b

a

c

e

ca

(k)

b

d

e

a

(l)

b

c

d

e

格的判定

解題小貼士—通過(guò)哈斯圖判斷是否是格的方法哈斯圖中，同一條鏈上的元素一定存在最大下界和最小上界。因此，判斷一個(gè)哈斯圖是否是格，只需考慮不在同一條鏈上的元素，即不可比的元素是否有最大下界和最小上界。格的運(yùn)算性質(zhì)

格的運(yùn)算性質(zhì)

格的運(yùn)算性質(zhì)

格的運(yùn)算性質(zhì)

代數(shù)格的定義

偏序格與代數(shù)格是等價(jià)的。代數(shù)格

偏序格

代數(shù)格

偏序格

代數(shù)格

偏序格

代數(shù)格

偏序格

對(duì)偶格

格的對(duì)偶原理

關(guān)于格的任何真命題的對(duì)偶命題也是真命題。格的性質(zhì)

a

c

b

模不等式

a

c

b

分配不等式

a

b

c

保序性

格的性質(zhì)

格的性質(zhì)

格的性質(zhì)

內(nèi)容導(dǎo)航CONTENTS格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6歷史人物本章導(dǎo)讀及學(xué)習(xí)要求子格的定義

子格的判定

子格的判定

理想的定義和判定

與子群和正規(guī)子群在群論中的地位以及子環(huán)和理想在環(huán)論中的地位類似，子格和理想對(duì)于研究格的結(jié)構(gòu)和性質(zhì)也十分重要。

格同態(tài)

格同態(tài)

(c)

a

b

c

d

e

(f)

a

b

c

d

e

a

(e)

b

c

d

e

a

(d)

b

c

d

e

(g)

a

b

c

d

e

a

(a)

b

c

d

a

(b)

b

c

d

內(nèi)容導(dǎo)航CONTENTS格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6歷史人物本章導(dǎo)讀及學(xué)習(xí)要求特殊格按照滿足的運(yùn)算定律來(lái)劃分：分配格：滿足分配律模格：滿足模律分配格

冪集格和命題格均是分配格。所有鏈都是分配格。分配格定理10.4

所有全序集（或鏈）都是分配格。

分配格定理10.4

所有全序集（或鏈）都是分配格。

分配格例10.5證明如圖所示的兩個(gè)格（鉆石格和五角格）都不是分配格。

a

b

c

d

e

a

b

c

d

e

分配格的判定定理10.5

（Birkhoff判定定理）一個(gè)格是分配格的充分必要條件是該格中沒(méi)有任何子格與鉆石格或五角格同構(gòu)。結(jié)論

（1）四個(gè)元素以下的格都是分配格；（2）五個(gè)元素的格僅有兩個(gè)格是非分配格(鉆石格和五角格)，其余三個(gè)格(如右圖所示)都是分配格。a

b

c

d

e

a

b

c

d

e

a

b

c

d

e

分配格的判定

分配格的判定

a

b

c

d

e

a

b

c

d

e

模格

a

b

c

模不等式

a

b

c

模律

模格有很多重要的性質(zhì)，其中比較有名的就是戴德金轉(zhuǎn)置定理（也就是菱形同構(gòu)定理），這形象的描述了模格的哈斯圖可以看做是若干個(gè)菱形堆積構(gòu)成的。模格的判定

結(jié)論

每一個(gè)全序集（或鏈）是模格，四個(gè)元素以下的格都是模格；而對(duì)于五個(gè)元素的格，僅有一個(gè)格不是模格(即五角格)，其余四個(gè)格都是模格。模格的判定定理10.8

（Dedekind判定定理）一個(gè)格是模格的充分必要條件是該格中沒(méi)有任何子格與五角格同構(gòu)。對(duì)照回顧：定理10.5

（Birkhoff判定定理）一個(gè)格是分配格的充分必要條件是該格中沒(méi)有任何子格與鉆石格或五角格同構(gòu)。分配格和模格的判定例10.6判斷右圖所示的格是否為分配格或模格？

特殊格按照滿足的運(yùn)算定律來(lái)劃分：分配格：滿足分配律模格：滿足模律按照特殊元素來(lái)劃分：有界格：有全上界和全下界有補(bǔ)格：每個(gè)元素有補(bǔ)元有界格

有界格

補(bǔ)元和有補(bǔ)格

補(bǔ)元和有補(bǔ)格例10.7右圖所示的有界格，求其所有元素的補(bǔ)元(如果有的話)，指出它們是否是有補(bǔ)格。

e

無(wú)

補(bǔ)元的求解解題小貼士

通過(guò)哈斯圖計(jì)算補(bǔ)元的方法（1）0和1互為補(bǔ)元。（2）除0和1外，可比的兩個(gè)元素不可能存在補(bǔ)元關(guān)系，即他們不在同一條鏈上。所以只要驗(yàn)證與所求元素不在同一條鏈的元素就可以了（即不可比的元素才有可能為補(bǔ)元）。補(bǔ)元和有補(bǔ)格

有補(bǔ)分配格

內(nèi)容導(dǎo)航CONTENTS格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6歷史人物本章導(dǎo)讀及學(xué)習(xí)要求布爾代數(shù)有補(bǔ)分配格又稱為布爾格。由于布爾格中每個(gè)元素都有補(bǔ)元而且補(bǔ)元唯一，則可以將求元素的補(bǔ)元作為一種一元運(yùn)算，此時(shí)就稱為布爾代數(shù)。

布爾代數(shù)

布爾代數(shù)

最簡(jiǎn)單的布爾代數(shù)

∧01000101∨010011110110典型布爾代數(shù)

內(nèi)容導(dǎo)航CONTENTS格的定義和性質(zhì)子格與格同態(tài)特殊格格與布爾代數(shù)的應(yīng)用

10.1

10.2

10.3

10.4作業(yè)

10.5布爾代數(shù)

10.6歷史人物本章導(dǎo)讀及學(xué)習(xí)要求10.5.1格與樹形圖結(jié)構(gòu)定理10.11

設(shè)T是一棵有n個(gè)結(jié)點(diǎn)的根樹，V是T的結(jié)點(diǎn)集合，設(shè)0

V，令L=V

{0}，定義L上的一個(gè)二元關(guān)系

為：（1）規(guī)定0

0，且對(duì)

a

V，0

a.（2）

a,b

V