【正文】 的某個(gè)子集構(gòu)成格 ， 卻不一定是子格 。 第 7章 格和布爾代數(shù) 定義 設(shè) 〈 L,∧ ,∨ 〉 是一個(gè)格，設(shè)非空集合 S且 S L,若對(duì)任意的 a,b∈ S,有 a∧ b∈ S,a∨ b∈ S,則稱〈 S,∧ ,∨ 〉 是 〈 L,∧ ,∨ 〉 的子格。 〉 是格 ， 并且該格對(duì)應(yīng)的偏序關(guān)系就是整除關(guān)系 。 y={x,y}的最小公倍數(shù) ， 因?yàn)?*,。 ?第 7章 格和布爾代數(shù) （ 2） 〈 Sn,*,。 【 例 】 （ 1） 〈 P(S),∩,∪ 〉 是一個(gè)代數(shù)系統(tǒng) ， P(S)是集合 S的冪集 ， 因?yàn)?∩,∪ 滿足可交換 、 可結(jié)合并滿足吸收律 ，所以 〈 P(S),∩,∪ 〉 是格 。 滿足交換律 、 結(jié)合律和吸收律 ， 則〈 S,*,。 〉 是代數(shù)系統(tǒng) ， *， 。 因此 〈 L, 〉 是格 。 又因?yàn)?(a∧ b)∧ b＝ a∧ (b∧ b)=a∧ b， 所以 a∧ b b,故 a∧ b為 {a,b}的一個(gè)下界 。 第 7章 格和布爾代數(shù) （ 4） 下證在這個(gè)關(guān)系下 ， 對(duì)任意 a,b∈ L， a∧ b為{a,b}的下確界 ， 即 a∧ b=GLB{a,b}。 設(shè) c為 {a， b}任一上界 ， 即 a c， b c， 那么 ， a∨ c＝ c,b∨ c＝ c,于是 a∨ c∨ b∨ c＝ c∨ c 亦即 a∨ b∨ c＝ c,故 a∨ b≤c。 由吸收律 a∧ （ a∨ b） ＝ a， 所以 a a∨ b。 反之 ， 設(shè) a∨ b＝ b， 那么 a∧（ a∨ b） ＝ a∧ b， 由吸收律可知 a＝ a∧ b， 即 a b。 （ 2） 可證 a b當(dāng)且僅當(dāng) a∨ b＝ b。 第 7章 格和布爾代數(shù) ③ 設(shè) a b， b c， 則 a∧ b=a， b∧ c=b， 于是 a∧ c=（ a∧ b） ∧ c＝ a∧ （ b∧ c） ＝ a∧ b=a 故 a c。 由于a∧ b=b∧ a， 故 a=b。 自反性得證 。 （ 1） L上偏序關(guān)系 。 由吸收律知 a∧ a＝ a∧ （ a∨ （ a∧ b）） ＝ a a∨ a＝ a∨ (a∧ （ a∨ b）） ＝ a 第 7章 格和布爾代數(shù) 。即在 L中可 a,b∈ L,a∧ b=GLB{a,b},a∨ b=LUB{a,b}。 由于 a a∨ （ b∧ c） ， （ a∨ b） ∧ c c 因此由傳遞性有 a c。 第 7章 格和布爾代數(shù) （ 2）因?yàn)?a a∨ b， a a∨ c,故 a （ a∨ b） ∧ （ a∨ c）。 最后 ， 設(shè) b＝ a∨ b， 則由 a a∨ b可得 a b。 因此有 a∧ b=a。 （ 3） a c當(dāng)且僅當(dāng) a∨ (b∧ c) （ a∨ b） ∧ c。 那么對(duì) L中任意元素 a,b,c， 有 （ 1） a b當(dāng)且僅當(dāng) a∧ b=a當(dāng)且僅當(dāng) a∨ b=b。為了解決這個(gè)問(wèn)題 ， 我們?cè)龠M(jìn)一步介紹格的下述性質(zhì) 。 a∧ (a∨ b)=a的證明留給讀者 。 利用對(duì)偶原理可得 a∨ （ b∨ c） =（ a∨ b） ∨ c。 （ 2）由格的并 ∨ 與交 ∧ 運(yùn)算的定義知滿足交換律。 ， 所以 a∨ a=a。 第 7章 格和布爾代數(shù) 定理 設(shè) 〈 L, 〉 是一個(gè)格 ， 那么對(duì) L中任意元素 a,b,c， 有 （ 1） a∨ a=a， a∧ a＝ a (冪等律 ) （ 2） a∨ b=b∨ a， a∧ b=b∧ a （ 交換律 ） （ 3） a∨ （ b∨ c） =（ a∨ b） ∨ c,a∧ （ b∧ c） =（ a∧ b） ∧ c (結(jié)合律 ) （ 4） a∧ (a∨ b)=a， a∨ (a∧ b)=a (吸收律 ) 第 7章 格和布爾代數(shù) 證明 （ 1） 由自反性可得 a a， 所以 a是 a的一個(gè)上界 ，因?yàn)?a∨ a是 a與 a的最小上界 ， 因此 a∨ a a。 這說(shuō)明 b∨ d是 a和 c的一個(gè)上界 ， 而 a∨ c是 a和 c的最小上界 ， 所以 ， 必有 a∨ c b∨ d 將 a∧ c≤b∧ d的證明留給讀者 。 由對(duì)偶原理可得 a∧ b a， a∧ b b。 這個(gè)性質(zhì)稱為格的保序性 。 第 7章 格和布爾代數(shù) 定理 設(shè) 〈 L, 〉 是一個(gè)格 ， 那么對(duì) L中任何元素 a,b,c， 有 （ 1） a a∨ b， b a∨ b a∧ b a， a∧ b b （ 2） 若 a b， c d， 則 a∨ c b∨ d， a∧ c b∧ d。 在上述對(duì)偶原理中 ， “ 如果命題 P在任意格 〈 L， 〉 上成立 ” 的含義是指當(dāng)命題 P中的變量取值于L中 ， 且上確界運(yùn)算為 ∨ ， 下確界運(yùn)算為 ∧ ， 則 P對(duì)于它們也成立 。 第 7章 格和布爾代數(shù) 定理 若 〈 L, 〉 是一個(gè)格 ， 則 〈 L, 〉 也是一個(gè)格 ,且它的并 、 交運(yùn)算 ∨ r,∧ r對(duì)任意 a,b∈ L滿足 a∨ rb=a∧ b a∧ rb=a∨ b 于是 ， 我們有下列對(duì)偶原理 。 并且它們所對(duì)應(yīng)的哈斯圖是互為顛倒的 。 ????第 7章 格和布爾代數(shù) （ 3）設(shè) Z+表示正整數(shù)集， |表示 Z+上整除關(guān)系，那么 〈 Z+， |〉 為格，其中并、交運(yùn)算即為求兩正整數(shù)最小公倍數(shù)和最大公約數(shù)的運(yùn)算，即 m∨ n＝ LCM（ m,n） m∧ n＝ gcd（ m,n） 另外 ， 若將 〈 L, 〉 中的小于等于關(guān)系換成大于等， 即對(duì)于 L中任何兩個(gè)元素 a,b定義 a b的充分必要條件是 b a,則 〈 L, 〉 也是偏序集 。 第 7章 格和布爾代數(shù) 【 例 】 （ 1） 對(duì)任意集合 S， 偏序集 〈 P（ S） ， 〉 為格 ，其中并 、 交運(yùn)算即為集合的并 、 交運(yùn)算 ， 即 B∨ C＝ B∪ C B∧ C＝ B∩C 封閉于 P(S),這里 B,C∈ P(S)。由于對(duì)任何 a， b， a∨ b及 a∧ b都是 L中確定的成員，因此∨ ,∧ 均為 L上的二元運(yùn)算。 雖然偏序集合的任何子集的上確界 、 下確界并不一定都存在 ， 但存在 ， 則必唯一 ， 而格定義保證了上確界 、 下確界的存在性 。不過(guò) ， 當(dāng)某子集的上 、 下確界存在時(shí) ， 這個(gè)上 、 下確界是唯一確定的 。 格是具有兩個(gè)二元運(yùn)算的代數(shù)系統(tǒng) ， 它是一個(gè)特殊的偏序集 ， 而布爾代數(shù)則是一個(gè)特殊的格 。第 7章 格和布爾代數(shù) 第 7章 格和布爾代數(shù) 格與子格 特殊格 布爾代數(shù) 例題選解 習(xí) 題 七 第 7章 格和布爾代數(shù) 格與子格 本章將討論另外兩種代數(shù)系統(tǒng) —— 格與布爾代數(shù) ，它們與群 、 環(huán) 、 域的基本不同之處是：格與布爾代數(shù)的基集都是一個(gè)有序集 。 這一序關(guān)系的建立及其與代數(shù)運(yùn)算之間的關(guān)系是介紹的要點(diǎn) 。 第 7章 格和布爾代數(shù) 圖 a bcde f第 7章 格和布爾代數(shù) 在第四章 ， 對(duì)偏序集的任一子集可引入上確界 （ 最小上界 ） 和下確界 （ 最大下界 ） 的概念 ， 但并非每個(gè)子集都有上確界或下確界 ， 例如在圖 示的有序集里 ， {a， b}沒(méi)有上確界 ， {e， f}沒(méi)有下確界 。 第 7章 格和布爾代數(shù) 定義 如果偏序集 〈 L 〉 中的任何兩個(gè)元素的子集都有上確界和下確界 ,則稱偏序集 〈 L 〉 為格（ lattice）。 因此我們通常用 a∨ b表示 {a，b}的上確界 ， 用 a∧ b表示 {a， b}的下確界 ， 第 7章 格和布爾代數(shù) 圖 baa b( a ) ( b ) ( c )( d ) ( e )第 7章 格和布爾代數(shù) 并記作 a∨ b=LUB{a,b}（ Leastupperbound） ,a∧ b=GLB{a,b}(Greatestlowerbound),∨ 和 ∧ 分別稱為并（ join）和交（ meet）運(yùn)算。由定義知道，并非所有的偏序集都能構(gòu)成格，我們用 Hasse圖表示偏序集，圖？ 圖 （ a） 、 （ b） 、 （ c） 所規(guī)定的偏序集是格 ， 圖 （ d） 、 （ e)及圖 是格 ,因?yàn)閳D中 {a,b}無(wú)上確界 。 （ 2） 設(shè) L為命題公式集合 ， 邏輯蘊(yùn)涵關(guān)系 “ ” 為L(zhǎng)上的偏序關(guān)系 （ 指定邏輯等價(jià)關(guān)系 “ ” 為相等關(guān)系 ） ， 那么 ， 〈 L, 〉 為格 ， 對(duì)任何命題公式 A， B，A∨ B=A∨ B， A∧ B=A∧ B（ 等式右邊的 ∨ ， ∧ 為析取與合取邏輯運(yùn)算符 ） 。 我們把偏序集 〈 L, 〉 和 〈 L, 〉 稱為是相互對(duì)偶的 。 關(guān)于格我們有同樣的性質(zhì) 。 第 7章 格和布爾代數(shù) 定理 如果命題 P在任意格 〈 L， 〉 上成立 ，則將 L中符號(hào) ∨ ， ∧ ， ∧ ， ∨ ，公式 P*在任意格 〈 L， 〉 上也成立 ， 這里 P*稱為 P的對(duì)偶式 。 現(xiàn)在我們深入地討論格的性質(zhì) 。 （ 3） 若 a b， 則 a∨ c b∨ c， a∧ c b∧ c。 第 7章 格和布爾代數(shù) 證明 （ 1） 因?yàn)?a∨ b是 a的一個(gè)上界 ， 所以 a a∨ b；同理有 b a∨ b。 （ 2）由題設(shè)知 a b， c d，由（ 1） 有 b b∨ d， d b∨ d 有 a b∨ d， c b∨ d。 （ 3） 將 （ 2） 中的 a代替 b， b代替 c， c代替 d即可得證 。 由定理 （ 1） 可知 a a∨ a。 利用對(duì)偶原理可得 a∧ a＝ a。 第 7章 格和布爾代數(shù) （ 3） 由下確界定義知 a∧ （ b∧ c） b∧ c b () a∧ （ b∧ c） a () a∧ （ b∧ c） b∧ c c () 由式 ()、 ()得 a∧ （ b∧ c a∧ b () 第 7章 格和布爾代數(shù) 由式 ()、 ()得 a∧ （ b∧ c） (a∧ b)∧ c () 同理可證 （ a∧ b） ∧ c a∧ （ b∧ c） （ ）