資源描述：
《離散數(shù)學(xué) 賈振華 第11章 格與布爾代數(shù)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第11章格與布爾代數(shù)本章學(xué)習(xí)目標(biāo)通過本章的學(xué)習(xí)，讀者應(yīng)掌握如下內(nèi)容：（1）掌握格的定義和性質(zhì)（2）掌握模格、分配格與有補(bǔ)格的概念和性質(zhì)（3）掌握布爾代數(shù)的概念和性質(zhì)（4）掌握布爾表達(dá)式的概念和性質(zhì)，并掌握同構(gòu)的概念及其判定第11章格與布爾代數(shù)11.1格的定義和性質(zhì)11.2分配格和有補(bǔ)格11.3布爾代數(shù)11.1格的定義和性質(zhì)11.1格的定義定義11.1.1設(shè)（S，≤）是一個(gè)偏序集，如果S中任意兩個(gè)元素都有上確界（最小上界）和下確界（最大下界），則稱（S，≤）為格。把S中元素a和b得上確界和下確界，分別記為：a∨b和a∧b，即a∨b=sup{a，b}，a∧b=inf{a，b}。a∨b讀作
2、a并b，a∧b讀作a交b。11.1格的定義和性質(zhì)11.1格的定義例11.1.1正整數(shù)集合上整除關(guān)系就是一個(gè)偏序關(guān)系，對(duì)于正整數(shù)集合上的任意兩個(gè)元素a，b，一定有上確界和下確界。事實(shí)上，a∨b=[a，b]，a∧b=（a，b），其中，[a，b]、（a，b）分別為a與b的最小公倍數(shù)和最大公因數(shù)。這樣正整數(shù)集和關(guān)于整除關(guān)系構(gòu)成格。11.1格的定義和性質(zhì)11.1格的定義例11.1.2設(shè)S是一個(gè)集合，P（S）是S的冪集，即P（S）是由S的所有子集組成的集合，則P（S）關(guān)于集合的包含關(guān)系構(gòu)成一個(gè)格，稱為S的冪集格。對(duì)于任意的A，B∈P（S），A∨B=A∪B，A∧B=A∩B，其中∪和∩分別為集合的并
3、與交。當(dāng)S是無限集時(shí)，令Pf（S）是由S的所有有限子集組成的集合，則Pf（S）關(guān)于集合的包含關(guān)系仍構(gòu)成一個(gè)格。11.1格的定義和性質(zhì)11.1格的定義例11.1.3設(shè)V是域F上的一個(gè)向量空間，維數(shù)可以有限也可以無限。令L（V）是V的所有子空間組成的集合，則L（V）關(guān)于集合的包含關(guān)系構(gòu)成一個(gè)格。對(duì)于任意的A，B∈L（V），子空間A∩B是A與B的下確界A∧B，由子集A∪B生成的子空間（包含A∪B的所有子空間的交）是A與B的上確界A∨B。11.1格的定義和性質(zhì)11.1.2格的對(duì)偶原理定義11.1.2設(shè)（S，≤）是格，將關(guān)系式P中的≤與≥互換，∨與∧互換得到關(guān)系式P*，其中≥定義為b≥a當(dāng)且僅
4、當(dāng)a≤b，稱P*為P的對(duì)偶式，簡(jiǎn)稱對(duì)偶。例如P是a≤a∨b，那么P的對(duì)偶式是a≥a∧b。11.1格的定義和性質(zhì)11.1.2格的對(duì)偶原理定理11.1.1（格的對(duì)偶原理）在任何格（S，≤）上成立的關(guān)系式P，其對(duì)偶式P*也成立。證明設(shè)（S，≤）為任意的格，只須證明P*對(duì)（S，≤）成立即可。如下定義S上的二元關(guān)系：任意a，b∈S，有abab。易證也是S上的偏序。11.1格的定義和性質(zhì)11.1.2格的對(duì)偶原理定理11.1.1（格的對(duì)偶原理）在任何格（S，≤）上成立的關(guān)系式P，其對(duì)偶式P*也成立。設(shè)任意a，b∈S，集合{a，b}的上確界和下確界存在，分別記作ab和ab，并且ab=ab，ab=ab
5、。所以（S，）也是格，且P*在（S，≤）中成立，當(dāng)且僅當(dāng)P在（S，）中成立。由于P在任何格（S，≤）中都成立，所以P*在（S，≤）中也成立。11.1格的定義和性質(zhì)11.1.3格的性質(zhì)定理11.1.2設(shè)（S，≤）是格，對(duì)于任意a，b，c∈S有（1）a≤a∨b，b≤a∨b；（2）a∧b≤a，a∧b≤b；（3）若b≤a，c≤a，則b∨c≤a；（4）若a≤b，a≤c，則a≤b∧c。11.1格的定義和性質(zhì)11.1.3格的性質(zhì)設(shè)（S，≤）是格。對(duì)于任意的a，b∈S，都有a∨b，a∧b∈S，即∨與∧是S的兩個(gè)代數(shù)運(yùn)算。這樣（S，∨，∧）就構(gòu)成了代數(shù)系統(tǒng)，稱為由格S誘導(dǎo)出的代數(shù)系統(tǒng)。下面討論這個(gè)代數(shù)
6、系統(tǒng)的性質(zhì)。11.1格的定義和性質(zhì)11.1.3格的性質(zhì)定理11.1.3（S，≤）是一個(gè)格，由格（S，≤）所誘導(dǎo)的代數(shù)系統(tǒng)為（S，∨，∧），則對(duì)任意的a，b，c∈S，下列性質(zhì)成立：（1）交換律a∨b=b∨a，a∧b=b∧a；（2）結(jié)合律（a∨b）∨c=a∨（b∨c），（a∧b）∧c=a∧（b∧c）；（3）冪等律a∨a=a，a∧a=a；（4）吸收律（a∨b）∧a=a，（a∧b）∨a=a。11.1格的定義和性質(zhì)11.1.3格的性質(zhì)證明根據(jù)格的對(duì)偶原理只須證明每條性質(zhì)的前半部分。（1）a∨b是{a，b}的上確界，b∨a是{b，a}的上確界，由集合定義的無序性有{a，b}={b，a}，可得a∨
7、b=b∨a。（2）因?yàn)閍≤a∨b≤（a∨b）∨c，b≤a∨b≤（a∨b）∨c，c≤（a∨b）∨c，于是有b∨c≤（a∨b）∨c，a∨（b∨c）≤（a∨b）∨c。同理可證（a∨b）∨c≤a∨（b∨c）。根據(jù)≤的反對(duì)稱性可知，（a∨b）∨c=a∨（b∨c）。11.1格的定義和性質(zhì)11.1.3格的性質(zhì)證明根據(jù)格的對(duì)偶原理只須證明每條性質(zhì)的前半部分。3）顯然a≤a∨a，又由a≤a，a是{a，a}的上界，所以a∨a≤a。根據(jù)≤的反對(duì)稱性，有a∨a=a。（4）因?yàn)閍≤
