《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu19n》由会员分享，可在线阅读，更多相关《离散数学 教学课件 ppt 作者 赵一鸣 阚海斌 吴永辉 dshu19n（13页珍藏版）》请在金锄头文库上搜索。
1、3 布尔格与布尔代数,一、布尔代数 定义16.10:有补分配格称为布尔(Boole)格, 习惯上写成(B;)。 有补格：有界(有最大元1和最小元0)，且每个元素有补元 b是a的补元：ab=1,ab=0,定理17.10:布尔格(B;)中任a,bB,有: (1)a的补元是唯一的。 (2)(ab)=ab,(ab)=ab。 (3)ab=0ab。 (4)(a)=a,证明:(1)设a1,a2为a的补元,则有a1a=1, a1a=0,a2a=1, a2a=0, 目标是a1=a2 (2)要证(ab)=ab,即证 (ab) (ab)=1, (ab)(ab)=0 (3)由ab=0,证明ab, 关键是如何由ab=0
2、引出a与b的联系. 注意到定理17.1(2):ab当且仅当ab=a; 因此可考虑由ab=0,导出ab=a 由ab,证明ab=0, 利用保序性,由(B;)定义了,运算，而a的补元a也是B中的元素，且分配格补元唯一 看作为B上的一元运算。 B;,为代数系统，又称为布尔代数。,布尔代数B;,是有补分配格,具有性质L1L4, L1幂等律:aa=a,aa=a; L2交换律:ab=ba,ab=ba; L3结合律:a(bc)=(ab)c, a(bc)=(ab)c; L4吸收律:a(ab)=a, a(ab)=a。 分配格,满足分配等式D1D2, D1:a(bc)=(ab)(ac);(ab)(ac)=a(bc)
3、 D2:(ab)(ac)(bc)=(ab)(ac)(bc),有补格:一定是有界格,每个元素有补元,满足B1、B2和C1C3, B1:a1=1;a0=0 B2:a1=a;a0=a C1:aa=1,aa=0 C2:0=1 C3:(ab)=ab,(ab)=ab,和定义即为P1,并可得到P2P3, P1:ab是a和b的最小上界，ab是a和b的最大下界 P2:ab当且仅当ab=a P3:ab=0ab 上述性质并不是相互独立的，可以从其中几个推出另外几个性质,定理16.11:B至少包含两个元素,和为B上的两个二元运算,为B上的一元运算,若对任何a,b,cB满足: (H1)ab=ba,ab=ba。 (H2)
4、a(bc)=(ab)(ac);(ab)(ac)=a(bc) (H3)在B中存在零元0,使a0=a,a0=0,存在单位元1,使a1=a,a1=1。 (H4)aB,使aa=0,aa=1。 则B;,为布尔代数。,B; ,为代数系统,为定义在B上的二元运算,为定义在B上的一元运算, 满足条件(H1)(H4),则称B为布尔代数。,二、布尔环 定义:在布尔代数B;,中,定义B上的二元运算+及如下:任a,bB a+b=(ab)(ab),ab=ab 容易验证在一般的布尔代数B;,上定义的B;+,是可交换的有单位元环。我们称这样的环为布尔环 定义16.12:B;,为布尔代数,如上定义+,则有B;+,为环,称此环为布尔环。,定理16.12:B;+,为布尔环,则对任aB,a2=a,且2a=0。 引理：设A;+,为环,若对任aA,a2=a,则必有2a=0。 给定的有单位元1的环B;+,若它的每个元素都是幂等元,且定义任a,bB,a=1-a, ab=a+b-ab,ab=ab,可以得到一个代数系统B;,可以验证它满足H1H4,因此所定义的代数系统B;,是布尔代数。,定义16.13:一个带单位元的环, 如果它的每个元素都是幂等的, 则称该环为布尔环 由布尔格可以定义一个布尔代数,并进一步定义一个布尔环。 由布尔环可以定义一个布尔代数,并进一步定义一个布尔格。,作业P220: 24,25,26,27,28,
