格与布尔代数课件.pptVIP

定理8.1.13設?X,∨,∧,0,1?為有界分配格，如果對於a?X，a存在補元b，則b是a的惟一補元。證明：因為b是a的補元，所以有a∨b=1，a∧b=0設c?X，c是a的另一個補元，同樣也有a∨c=1，a∧c=0從而有a∨b=a∨c，a∧b=a∧c由於?X,∨,∧,0,1?為分配格，根據定理8.1.10必有b=c，即a的補元惟一。定義8.1.12設?X,∨,∧,0,1?為有界格，如果?a?X，在X中都有a的補元存在，則稱?X,∨,∧,0,1?為有補格例如，圖8.8是三個有界格的哈斯圖，由於每一個元素至少有一個補元，所以它們都是有補格。返回章目錄8.2布爾代數定義8.2.1有補分配格稱為布爾格。在布爾格中每一個元素都有補元。因為有補格一定是有界格，所以布爾格一定是有界分配格，根據定理8.1.13，布爾格中的每一個元素的補元存在且惟一。於是可以將求補元的運算看作一元運算且把a的補元記為a′。定義8.2.2設?X,??是布爾格，?X,∨,∧,′?是格?X,??導出的代數系統。稱代數系統?X,∨,∧,′?為布爾代數。在8.1節中證明了?P(A),R??是格，其中A=?a,b?。?P(A),∪,∩?是?P(A),R??導出的代數系統，其中∪和∩是集合並運算和交運算。以後又進一步說明了?P(A),∪,∩?是分配格和有界格，?是全下界、A是全上界。從而?P(A),∪,∩?是有界分配格。令A為全集，?T?P(A)，T的補集~T=A–T?P(A)，滿足T∪~T=A和T∩~T=?，所以T的補元T′=~T。根據定義8.2.2，?P(A),∪,∩,~?是布爾代數。可以證明，當A為任意集合時，?P(A),∪,∩,~?也是布爾代數。稱為集合代數。集合代數是布爾代數的一個具體模型。布爾代數一定是格。根據定理8.1.1，布爾代數中的兩個二元運算滿足交換律、結合律、冪等律和吸收律。此外，布爾代數還有下麵的性質：定理8.2.1設?X,∨,∧,′?為布爾代數，?a,b?X，必有⑴(a′)′=a⑵(a∨b)′=a′∧b′⑶(a∧b)′=a′∨b′證明：⑴a′是a的補元，a也是a′的補元，由布爾代數中補元的惟一性有(a′)′=a⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′)=(b∨(a∨a′))∧(a∨(b∨b′))=(b∨1)∧(a∨1)=1∧1=1(a∨b)∧(a′∧b′)=(a∧(a′∧b′))∨(b∧(a′∧b′))=((a∧a′)∧b′)∨((b∧b′)∧a′)=(0∧b′)∨(0∧a′)=0∨0=0所以(a∨b)′=a′∧b′⑶同理可證(a∧b)′=a′∨b′定理8.2.1中的⑴稱為雙重否定律，⑵和⑶稱為德摩根律。布爾代數滿足雙重否定律和德摩根律。定理8.2.2設?X,*,°,′?是代數系統，其中*和°都是二元運算，′是一元運算。?X,*,°,′?是布爾代數的充分必要條件是：⑴*和°在X上封閉且滿足交換律。⑵*和°滿足分配律(滿足*對°的分配律和°對*的分配律)。⑶X中存在運算*的么元和運算°的么元。設運算*的么元為0，運算°的么元為1。即?a?X，有a*0=a，a°1=a⑷?a?X，?a′?X，使得a*a′=1，a°a′=0由於篇幅的限制，證明從略。定理8.2.2給出的四個條件可以作為布爾代數的等價定義。布爾代數?X,*,°,′?也可以表示成為?X,*,°,′,0,1?，其中0是運算*的么元，1是運算°的么元。【例8.9】設P是所有命題構成的集合，∨,∧和?分別是命題的析取、合取和否定聯結詞。證明代數系統?P,∨,∧,??是布爾代數。證明：根據第1章的內容，∨