离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu19n.ppt

《离散数学 教学课件 作者 赵一鸣 阚海斌 吴永辉 dshu19n.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、§3布尔格与布尔代数一、布尔代数定义16.10:有补分配格称为布尔(Boole)格,习惯上写成(B;≤)。有补格：有界(有最大元1和最小元0)，且每个元素有补元b是a的补元：ab=1,ab=0定理17.10:布尔格(B;≤)中任a,bB,有:(1)a的补元是唯一的。(2)(ab)'=a'b',(ab)'=a'b'。(3)ab=0a≤b'。(4)(a')'=a证明:(1)设a1,a2为a的补元,则有a1a=1,a1a=0,a2a=1,a2a=0,目标是a1=a2(2)要证(ab)'=a'b

2、',即证(ab)(a'b')=1,(ab)(a'b')=0(3)由ab=0,证明a≤b',关键是如何由ab=0引出a与b'的联系.注意到定理17.1(2):a≤b当且仅当ab=a;因此可考虑由ab=0,导出ab'=a由a≤b',证明ab=0,利用保序性由(B;≤)定义了,运算，而a的补元a'也是B中的元素，且分配格补元唯一'看作为B上的一元运算。[B;,,']为代数系统，又称为布尔代数。布尔代数[B;,,']是有补分配格,具有性质L1~L4,L1幂等律:aa=a,aa=

3、a;L2交换律:ab=ba,ab=ba;L3结合律:a(bc)=(ab)c,a(bc)=(ab)c;L4吸收律:a(ab)=a,a(ab)=a。分配格,满足分配等式D1~D2,D1:a(bc)=(ab)(ac);(ab)(ac)=a(bc)D2:(ab)(ac)(bc)=(ab)(ac)(bc)有补格:一定是有界格,每个元素有补元,满足B1、B2和C1~C3,B1:a1=1;a0=0B2:a1=a;a0=aC1:aa'=1,aa'=0

4、C2:0'=1C3:(ab)'=a'b',(ab)'=a'b’和定义即为P1,并可得到P2~P3,P1:ab是a和b的最小上界，ab是a和b的最大下界P2:a≤b当且仅当ab=aP3:ab=0a≤b’上述性质并不是相互独立的，可以从其中几个推出另外几个性质定理16.11:B至少包含两个元素,和为B上的两个二元运算,'为B上的一元运算,若对任何a,b,cB满足:(H1)ab=ba,ab=ba。(H2)a(bc)=(ab)(ac);(ab)(ac)=a(bc)(H3

5、)在B中存在零元0,使a0=a,a0=0,存在单位元1,使a1=a,a1=1。(H4)a'B,使aa'=0,aa'=1。则[B;,,']为布尔代数。[B;,,']为代数系统,,,为定义在B上的二元运算,’为定义在B上的一元运算,满足条件(H1)~(H4),则称B为布尔代数。二、布尔环定义:在布尔代数[B;,,']中,定义B上的二元运算+及·如下:任a,bBa+b=(ab')(a'b),a·b=ab容易验证在一般的布尔代数[B;,,']上定义的[B;+,·]是可交换的有单位元

6、环。我们称这样的环为布尔环定义16.12:[B;,,']为布尔代数,如上定义+,·,则有[B;+,·]为环,称此环为布尔环。定理16.12:[B;+,·]为布尔环,则对任aB,a2=a,且2a=0。引理：设[A;+,·]为环,若对任aA,a2=a,则必有2a=0。给定的有单位元1的环[B;+,·],若它的每个元素都是幂等元,且定义任a,bB,a'=1-a,ab=a+b-a·b,ab=a·b,可以得到一个代数系统[B;,,'],可以验证它满足H1~H4,因此所定义的代数系统[B;,,']是布尔代数

7、。定义16.13:一个带单位元的环,如果它的每个元素都是幂等的,则称该环为布尔环由布尔格可以定义一个布尔代数,并进一步定义一个布尔环。由布尔环可以定义一个布尔代数,并进一步定义一个布尔格。作业P220:24,25,26,27,28