《離散數學》第十章格與布爾代數內容導航CONTENTS歷史人物本章導讀及學習要求格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

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

學習要求內容導航CONTENTS歷史人物本章導讀及學習要求格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

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

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

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

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

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

尤利烏斯·威廉·理查德·戴德金（1831-1916），偉大的德國數學家、理論家和教育家，近代抽象數學的先驅。內容導航CONTENTS格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

10.6歷史人物本章導讀及學習要求引言格與布爾代數也是具有兩個二元運算的代數系統，這兩個代數系統與群、環、域之間有很多聯系，但也存在著一個重要區別：在格與布爾代數中，偏序關系具有重要意義。格有多種等價定義，但主要分為兩類，一類是從偏序集的角度給出的，這種定義可以借助哈斯圖表示，因而比較直觀，易于理解，這樣定義的格稱為偏序格；另一類是從代數系統的角度來給出的，可以借助代數系統的子代數、同態與同構等工具來討論其性質，這樣定義的格稱為代數格，代數格的定義又可分為八條件、六條件、四條件、三條件、二條件甚至一條件等幾種。格的定義

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

格的判定

格的判定

格的判定例10.2判斷如圖所示哈斯圖對應的偏序集是否是格。(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

格的判定

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

格的運算性質

格的運算性質

格的運算性質

代數格的定義

偏序格與代數格是等價的。代數格

偏序格

代數格

偏序格

代數格

偏序格

代數格

偏序格

對偶格

格的對偶原理

關于格的任何真命題的對偶命題也是真命題。格的性質

a

c

b

模不等式

a

c

b

分配不等式

a

b

c

保序性

格的性質

格的性質

格的性質

內容導航CONTENTS格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

10.6歷史人物本章導讀及學習要求子格的定義

子格的判定

子格的判定

理想的定義和判定

與子群和正規子群在群論中的地位以及子環和理想在環論中的地位類似，子格和理想對于研究格的結構和性質也十分重要。

格同態

格同態

(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

內容導航CONTENTS格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

10.6歷史人物本章導讀及學習要求特殊格按照滿足的運算定律來劃分：分配格：滿足分配律模格：滿足模律分配格

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

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

分配格定理10.4

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

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

a

b

c

d

e

a

b

c

d

e

分配格的判定定理10.5

（Birkhoff判定定理）一個格是分配格的充分必要條件是該格中沒有任何子格與鉆石格或五角格同構。結論

（1）四個元素以下的格都是分配格；（2）五個元素的格僅有兩個格是非分配格(鉆石格和五角格)，其余三個格(如右圖所示)都是分配格。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

模律

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

結論

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

（Dedekind判定定理）一個格是模格的充分必要條件是該格中沒有任何子格與五角格同構。對照回顧：定理10.5

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

特殊格按照滿足的運算定律來劃分：分配格：滿足分配律模格：滿足模律按照特殊元素來劃分：有界格：有全上界和全下界有補格：每個元素有補元有界格

有界格

補元和有補格

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

e

無

補元的求解解題小貼士

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

有補分配格

內容導航CONTENTS格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

10.6歷史人物本章導讀及學習要求布爾代數有補分配格又稱為布爾格。由于布爾格中每個元素都有補元而且補元唯一，則可以將求元素的補元作為一種一元運算，此時就稱為布爾代數。

布爾代數

布爾代數

最簡單的布爾代數

∧01000101∨010011110110典型布爾代數

內容導航CONTENTS格的定義和性質子格與格同態特殊格格與布爾代數的應用

10.1

10.2

10.3

10.4作業

10.5布爾代數

10.6歷史人物本章導讀及學習要求10.5.1格與樹形圖結構定理10.11

設T是一棵有n個結點的根樹，V是T的結點集合，設0

V，令L=V

{0}，定義L上的一個二元關系

為：（1）規定0

0，且對

a

V，0

a.（2）

a,b

V