格与布尔代数ppt课件.ppt

《格与布尔代数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章格与布尔代数第二节布尔代数定义：设是格，若它既是有补格，又是分配格则称为有补分配格也称作：布尔格，或布尔代数(BooleanAlgebra)常记作：布尔代数的性质是格，且≤是B上由或*所定义的偏序关系ab=lub{a,b}，a*b=glb{a,b}a≤bab=ba*b=aab=ba，a*a=b*a（交换律）a(bc)=(ab)c，a*(b*c)=(a*b)*c（结合律）a(a*b)=a，a*(ab)=a（吸收律）aa=a，a*a=a（等幂律）布尔代数的性质是分配格a*(bc)

2、=(a*b)(a*c)a(b*c)=(ab)*(ac)（分配律）(ab=ac)∧(a*b=a*c)b=c(ab)*(bc)*(ca)=(a*b)(b*c)(c*a)是模格a≤ca(b*c)=(ab)*c（模等式）证明：(ab)*(bc)*(ca)=((a*b)(a*c)b(b*c))*(ca)=(a*b*c)(a*c)(b*c)(b*c)(a*b)(a*c)(b*a)(a*b*c)=(a*b)(b*c)(c*a)布尔代数的性质是有界格0≤a≤1a0=a，a*1=a（么律）a1=1，a*0

3、=0（零律）是有补格aa’=1，a*a’=0（互补律）1’=0，0’=1布尔代数的性质是有补分配格(a’)’=a(ab)’=a’*b’，(a*b)’=a’b’（德·摩根律）a≤ba’b=1a*b’=0以上公式并非是独立的可以从中选出一些公式作为基本公式，来推导出其他公式并且可以用基本公式来定义布尔代数布尔代数的定义定义：设是一个代数结构，其中：和*是B上的二元运算，’是B上的一元运算，且0,1B对于a,bB，有ab=ba，a*b=b*a（交换律）a*(bc)=(a*b)(a*c)a(b*c

4、)=(ab)*(ac)（分配律）a0=a，a*1=a（么律）aa’=1，a*a’=0（互补律）则称为布尔代数,*,’分别是B上的并、交、补运算0和1分别称为,*的零元和么元从这4个定律，可以推出所有布尔代数的公式有兴趣的同学可以参阅R.L.古德斯坦因著的《布尔代数》还存在其它的布尔代数的定义，略布尔代数例9.12：设B={0,1}，B上的运算,*,’由下表定义：01001111*01000101aa’0110满足前面定义中的条件（交换律、分配律、么律和互补律），因此它是布尔代数（二元布尔代数）二元布尔代数是哈斯图为链的唯一

5、布尔代数布尔代数例9.13：设S是非空集合，P(S)是它的幂集。满足前面定义中的条件（交换律、分配律、么律和互补律），因此它是布尔代数。若

6、S

7、=n，则

8、P(S)

9、=2n，该布尔代数是n维立方体S={a},S={a,b}和S={a,b,c}时的布尔代数的哈斯图如下：{a}{a}{b}{a,b}{a}{b}{a,b}{c}{a,c}{b,c}{a,b,c}布尔代数例9.14：设S表示含有n个命题变元的命题公式集合。满足前面定义中的条件（交换律、分配律、么律和互补律），因此它是布尔代数。（这里把互为等价的两个命题公式看作是相等的）对

10、于由∨（或∧）和所定义的偏序关系是：布尔代数例9.15：设Bn是由0和1形成的n元组集合，且a=，b=0n=<0,0,…,0>，1n=<1,1,…,1>对任意a,bBn，定义：ab=a*b=a’=<a1,a2,…,an>是布尔代数（开关代数）第三节子布尔代数、积布尔代数、布尔代数同态定义：给定布尔代数，≠TB若T对、*和’是封闭的，且：0,1T称是

11、*,’,0,1>的子布尔代数显然：<{0,1},,*,’,0,1>和都是的(平凡)子布尔代数定理：每个子布尔代数都是布尔代数子布尔代数实际检测一个布尔代数，没有必要按定义进行即没有必要检测：T是否对{,*,’}封闭，且0,1T只需检测T是否对{,’}封闭，或T是否对{*,’}封闭即可ab=(a’*b’)’（德·摩根律：(ab)’=a’*b’）0