6-4 布尔代数.ppt

第六章 格和布尔代数 6-4 布尔代数 　　以上我们学习了一些特殊的格：分配格、有界格、有补格，那么既是分配格又是有补格的格就是我们接下来要学习的布尔格，由其诱导的代数系统称为布尔代数。 一、基本定义 1、有补分配格：定义6-3.6 既是有补格又是分配格 2、布尔格：定义6-4.1 有补分配格称为布尔格。 在布尔格中每一个元素都有补元。因为有补格一定是有界格，所以布尔格一定是有界分配格，根据定理，布尔格中的每一个元素的补元存在且惟一。于是可以将求补元的运算看作一元运算且把a的补元记为a′。 3、布尔代数：定义6-4.2 设?X,??是布尔格，?X,∨,∧,′?是格?X,??导出的代数系统。称代数系统?X,∨,∧, ′?为布尔代数。 4、有限布尔代数：定义6-4.2 具有有限个元素的布尔代数 　　　前面我们证明了 ?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。根据定义6-4.2 ， 　?P (A),∪,∩, ~?是布尔代数。 　　　可以证明，当A为任意集合时，?P (A),∪,∩, ~?也是布尔代数。称为集合代数。集合代数是布尔代数的一个具体模型。 二、布尔代数的性质 　　布尔代数一定是格。根据定理，布尔代数中的两个二元运算满足交换律、结合律、幂等律和吸收律。此外，布尔代数还有下面的性质： 定理6-4.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′ 定理6-4.1中的⑴称为双重否定律，⑵和⑶称为德摩根律。布尔代数满足双重否定律和德摩根律。 定理6.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 由于篇幅的限制，证明从略。 定理6.2.2给出的四个条件可以作为布尔代数的等价定义。 布尔代数?X,*,°,′?也可以表示成为?X,*,°,′,0,1?，其中0是运算*的幺元，1是运算°的幺元。 【例8.9】设P是所有命题构成的集合，∨,∧和?分别是命题的析取、合取和否定联结词。证明代数系统?P,∨,∧, ??是布尔代数。 证明：根据第1章的内容，∨和∧在P上封闭且满足交换律、分配律。命题常元0(假)和1(真)是集合P的元素，满足?q?P，q∨0=q，q∧1=q。 ?q?P，?q?P，满足q∨?q=1，q∧?q=0。 根据定理8.2.2，?P,∨,∧, ??是布尔代数。 例8.9中的布尔代数?P,∧,∨, ??叫做命题代数，它是布尔代数的又一个模型。 三、布尔代数的同构 6.2.