【文章內(nèi)容簡(jiǎn)介】 需證 a∧ （ b∨ c） ＝ b∨ （ a∧ c） 。 首先 ， 據(jù)定理 （ 3） ， 由 b a可知 b∨ （ c∧ a） （ b∨ c） ∧ a (） 由此 a∧ c ＝ （ a∧ c） ∧ c （ b∨ （ c∧ a）） ∧ c （ (b∨ c） ∧ a） ∧ c （ 由式 （ ）） =（ (b∨ c） ∧ c） ∧ a=c∧ a 第 7章 格和布爾代數(shù) 于是 （ b∨ （ c∧ a）） ∧ c＝（ (b∨ c） ∧ a） ∧ c=c∧ a （ ） （ 請(qǐng)讀者完成 ） （ b∨ (a∧ c）） ∨ c=(a∧ （ b∨ c）） ∨ c＝ b∨ c （ ） ,根據(jù)題設(shè)及式 （ ） 、 ()和 （ ） 得出 a∧ （ b∨ c） ＝ b∨ （ a∧ c） L滿足模性條件 ， 故 〈 L， ∨ ,∧ 〉 為模格得證 。 第 7章 格和布爾代數(shù) 定義 格 〈 L， ∧ ,∨ 〉 如果滿足分配律 ， 即對(duì)任意 a,b,c∈ L， 有 a∧ （ b∨ c） =（ a∧ b） ∨ （ a∧ c） （ ） a∨ （ b∧ c） =（ a∨ b） ∧ （ a∨ c） （ ） 則 L稱為分配格 （ distributivelattice） 。 第 7章 格和布爾代數(shù) 注意到 ， 上述兩個(gè)分配等式中有一個(gè)成立 ， 則另一個(gè)必成立 。 如式 （ ） 成立 ， 則 （ a∨ b） ∧ （ a∨ c） =((a∨ b） ∧ a)∨ ((a∨ b） ∧ c) =a∨ ((a∨ b） ∧ c) =a∨ ((a∧ c)∨ (b∧ c） ) =(a∨ (a∧ c))∨ (b∧ c） =a∨ （ b∧ c） 第 7章 格和布爾代數(shù) 【 例 】 設(shè) S是一個(gè)集合，則 〈 P(S),∩,∪ 〉 構(gòu)成格，而集合中求并 ∪ 與求交 ∩這兩種運(yùn)算滿足分配律，所以 〈 P(S),∩,∪ 〉 是分配格。并不是所有的格都是分配格。 圖 a b c10第 7章 格和布爾代數(shù) 【 例 】 如圖 Hasse圖中的格均不是分配格 。 在圖 ， 有 a∨ （ b∧ c） =a∨ 0=a (a∨ b） ∧ （ a∨ c） =1∧ 1=1 所以不是分配格 。 第 7章 格和布爾代數(shù) 分配格有以下性質(zhì)： 定理 設(shè) 〈 L， ∧ ,∨ 〉 為分配格，那么對(duì) L中任意元素 a， b， c，若 c∧ a=c∧ b并且 c∨ a=c∨ b，則 a=b。 證明 因?yàn)? （ c∧ a） ∨ b＝ （ c∧ b） ∨ b=b (因 c∧ a=c∧ b） （ c∧ a） ∨ b=（ c∨ b） ∧ （ a∨ b） 第 7章 格和布爾代數(shù) =（ c∨ a） ∧ （ a∨ b） (因 c∨ a=c∨ b) =a∨ （ c∧ b） ＝ a∨ （ c∧ a） （ 因 c∧ a=c∧ b） =a 所以 a=b。 第 7章 格和布爾代數(shù) 定理 若 〈 L, 〉 是鏈 ， 則 〈 L， 〉 是分配格 。 證明 設(shè) 〈 L, 〉 是鏈 ， 則 〈 L, 〉 是全序集 ， 設(shè)對(duì)于該集合中任意的 a,b,c三個(gè)元素 ， 分情況討論： (1)b a,c a， 此時(shí) a∧ （ b∨ c） =b∨ c， 同時(shí) （ a∧ b） ∨ （ a∧ c） =b∨ c (2)a b,a c， 此時(shí) a∧ （ b∨ c） =a， 同時(shí) （ a∧ b） ∨ （ a∧ c） =a因此無(wú)論任何情況 ， 皆有 a∧（ b∨ c） =（ a∧ b） ∨ （ a∧ c） 。 所以 〈 L， 〉 是分配格 。 第 7章 格和布爾代數(shù) 定理 設(shè) 〈 L， ∧ ,∨ 〉 為分配格 ， 則 〈 L， ∧ ,∨ 〉是模格 。 證明 對(duì)于任意的 a,b,c∈ L， 若 a b,則 a∧ b=a,并有 b∧ (a∨ c)=(b∧ a)∨ (b∧ c)=a∨ (b∧ c) 因此 ， 〈 L， ∧ ,∨ 〉 是模格 。 下面我們討論補(bǔ)格 。 定義 設(shè) 〈 L， ∧ ,∨ 〉 為有界格 ， a為 L中任意元素 ， 如果存在元素 b∈ L,使 a∨ b=1， a∧ b=0， 則稱 b是 a的補(bǔ)元或補(bǔ) （ plements） 。 第 7章 格和布爾代數(shù) 補(bǔ)元有下列性質(zhì)： （ 1） 補(bǔ)元是相互的 ， 即若 b是 a的補(bǔ) ， 那么 a也是 b的補(bǔ) 。 （ 2） 并非有界格中每個(gè)元素都有補(bǔ)元 ， 而有補(bǔ)元也不一定唯一 。 （ 3）全下界 0與全上界 1互為補(bǔ)元且唯一。 第 7章 格和布爾代數(shù) 【 例 】 考察圖 Hasse圖所示的其格中其元素的補(bǔ) 。 圖 （ a） 中除 0， 1之外 a,b,c均沒(méi)有補(bǔ)元 。 圖 （ b） 中 a的補(bǔ)元是 b,b的補(bǔ)元是 a。 圖 （ c） 中元素 a,b,c兩兩互為補(bǔ)元 ， 但不唯一 。 圖 （ d） 中除 0， 1之外沒(méi)有元素有補(bǔ)元 。 事實(shí)上 ， 多于兩個(gè)元素的鏈除 0， 1之外沒(méi)有元素有補(bǔ)元 。 在有界格中 ， 顯然 0是 1的唯一補(bǔ)元 ， 同時(shí) 1是 0的唯一補(bǔ)元 。 第 7章 格和布爾代數(shù) 圖 a b01c( a )a b01( b )a b01c( c )1ab0( d )第 7章 格和布爾代數(shù) 定義 如果有界格 〈 L， ∨ ,∧ 〉 中每個(gè)元素都至少有一個(gè)補(bǔ)元，則稱 L為補(bǔ)格（ plementedlattice）。 例 （ 2） 、 （ 3） 均是有補(bǔ)格 ， （ 1） 、 （ 4）不是補(bǔ)格 。 多于兩個(gè)元素的鏈都不是有補(bǔ)格 。 第 7章 格和布爾代數(shù) 定理 若 〈 L,∧ ,∨ 〉 是有補(bǔ)分配格 ， a∈ L,其補(bǔ)元是唯一的 。 因此 ,可用 a′來(lái)表示 a的補(bǔ)元 。 證明 采用反證法：若存在 a為 L中一元素 ， 有兩補(bǔ)元 b， c， 且 b≠c,則 a∨ b＝ a∨ c＝ 1， a∧ b＝ a∧ c＝ 0 由定理 ， b＝ c，與前面矛盾。因此 a只有唯一補(bǔ)元 a′。 第 7章 格和布爾代數(shù) 定理 若 〈 L,∧ ,∨ 〉 a∈ L，有 a″=（ a′） ′＝ a。 證明 a″∧ a′=0,a″∨ a′=1,由補(bǔ)元唯一可得 a″=a。 定理 德 摩根律 ， 設(shè) 〈 L， ∨ ,∧ 〉 是有補(bǔ)分配格 ， 則對(duì) L中任意元素 a， b， 有 (1)（ a∧ b） ′=a′∨ b′ （ 2） （ a∨ b） ′＝ a′∧ b′ 第 7章 格和布爾代數(shù) 證明 (1)由于 （ a∧ b） ∧ （ a′∨ b′） ＝ ((a∧ b） ∧ a′)∨ ((a∧ b） ∧ b′)＝ 0 （ a∧ b） ∨ （ a′∨ b′） =（ a∨ a′∨ b′） ∧ （ b∨ a′∨ b′） ＝ 1 因此 a′∨ b′為 a∧ b的補(bǔ)元 。 由補(bǔ)元的唯一性得知： (a∧ b） ′＝ a′∨ b′ 同樣可證 （ 2） ， 其證明留作練習(xí) 。 第 7章 格和布爾代數(shù) 定理 對(duì)有補(bǔ)分配格的任何元素 a， b，有 a b當(dāng)且僅當(dāng) a∧ b′=0當(dāng)且僅當(dāng) a′∨ b=1。 證明 若 a b，則有 a∨ b=b，所以 a∧ b′=(a∧ b′)∨ (b∧ b′)=(a∨ b)∧ b′=b∧ b′=0。 a∧ b′=0，則其對(duì)偶式 a′∨ b=1必成立。 若 a′∨ b=1，則 a∨ b=(a∨ b)∧ 1=(a∨ b)∧ (a′∨ b) =(a∧ a′)∨ b=0∨ b=b。 第 7章 格和布爾代數(shù) 布爾代數(shù) 定義 設(shè) B是至少有兩個(gè)元素的有補(bǔ)分配格 ， 則稱 B是布爾代數(shù) （ Booleanalgebra） 。 【 例 】 〈 {0,1},∧ ,∨ ,′〉 是一個(gè)布爾代數(shù) 。 第 7章 格和布爾代數(shù) 【 例 】 S≠ ,則 〈 P(S),∩,∪ ,∽ 〉 是一個(gè)布爾代數(shù)。其中 ∩表示集合的交運(yùn)算 ,∪ 表示集合的并運(yùn)算 ,∽ 表示集合的為一元求補(bǔ)集的運(yùn)算（這里的全集是 S）。 布爾代數(shù)通常用序組 〈 B， ∧ ， ∨ ， ′， 0， 1〉 來(lái)表示 。 其中 ′為一元求補(bǔ)運(yùn)算 。 為此介紹布爾代數(shù)的另一個(gè)等價(jià)定義 。 ?第 7章 格和布爾代數(shù) 定義 〈 B， ∧ ， ∨ ,′〉 是代數(shù)系統(tǒng)， B中至少有兩個(gè)二元元素， ∧ ， ∨ 是 B上二元運(yùn)算， ′是一元運(yùn)算，若 ∧ ， ∨ 滿足： （ 1） 交換律 。 （ 2） 分配律 。 （ 3）同一律。存在 0,1∈ B, a∈ B，有a∧ 1=a,a∨ 0=a。 （ 4） 補(bǔ)元律 。 對(duì) B中每一元素 a， 均存在元素 a′，使 a∧ a′=0,a∨ a′＝ 1， 則稱 〈 B， ∧ ， ∨ ,′〉 是布爾代數(shù) 。 第 7章 格和布爾代數(shù) 為證定義 ， 只需證 B是格 ， 進(jìn)而由 （ 2） 、 (3)、 （ 4） 可斷定 B為有補(bǔ)分配格 。 要證 B是格 ， 據(jù)定義 ， 只要證 B滿足交換律 （ 已有 ） 、 結(jié)合律和吸收律 。 下證 B滿足吸收律 。 a∈ B， 有 a∧ 0=0。 ?第 7章 格和布爾代數(shù) a∧ 0=(a∧ 0)∨ 0 (同一律 ) =（ a∧ 0） ∨ （ a∧ a′） （ 補(bǔ)元律 ） =a∧ （ 0∨ a′） （ 分配律 ） =a∧ a′ (同一律 ) =0 （ 補(bǔ)元律 ） 第 7章 格和布爾代數(shù) a,b∈ B, a∧ (a∨ b)＝ （ a∨ 0） ∧ （ a∨ b） (同一律 ) ＝ a∨ （ 0∧ b） （ 分配律 ） =a∨ 0