代数结构-布尔代数与格

《代数结构-布尔代数与格》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、布尔代数与格离散数学－代数结构南京大学计算机科学与技术系内容提要布尔函数布尔代数布尔代数的抽象定义理解布尔代数的性质代数格有限布尔代数的表示布尔代数与数字逻辑电路设计布尔函数nn令B={0,1},B={(x,…,x)

2、x∈B,i=1,…,n},从B到B1ni的函数称为n度布尔函数，f:Bn→B。取值范围为B的变元称为布尔变元，x∈B。n248n度布尔函数的个数：2↑2(2,2,2,…)三种说法含n个命题变量的命题逻辑表达式nn度布尔函数f:B→B有n个输入和一个输出的逻辑电路一个逻辑电路设计的例子举重比赛中三个裁判中两个或者两个以上判

3、定为成功则该次成绩有效,设计一个电子打分器,输出一个结果:“成功”或”失败”。xyzf(x,y,z)布尔函数:f(x,y,z)=1iff.x,y,z至少有两个为1。000000100100相应的布尔表达式:0111(x’∧y∧z)∨(x∧y’∧z)∨1000(x∧y∧z’)∨(x∧y∧z)101111011111回顾：命题表达式的主析取范式求(p→q)↔r的主析取范式(¬p∧r)∨(q∧r)∨(p∧¬q∧¬r)（析取范式）¬p∧r↔¬p∧(¬q∨q)∧r↔(¬p∧¬q∧r)∨(¬p∧q∧r)q∧r↔(p∧q∧r)∨(¬p∧q∧r)(¬p∧¬q∧r)∨(¬p∧

4、q∧r)∨(p∧q∧r)∨(p∧¬q∧¬r)(¬p∧¬q∧r)∨(¬p∧q∧r)∨(p∧¬q∧¬r)∨(p∧q∧r)001011100111集合{0,1}上的运算布尔和1+1=1,1+0=1,0+1=1,0+0=0布尔积1⋅1=1,1⋅0=0,0⋅1=0,0⋅0=0补0=1,1=0布尔函数上的运算布尔和(f+g)(x,…,x)=f(x,…,x)+g(x,…,x)1n1n1n布尔积(fg)(x,…,x)=f(x,…,x)⋅g(x,…,x)1n1n1n补函数f(x,…,x)=f(x,…,x)1n1n布尔恒等式（1）等式名称x=x双重补律x+

5、x=x幂等律x⋅x=xx+0=x同一律x⋅1=xx+1=1支配律x⋅0=0x+y=y+x交换律x⋅y=y⋅x布尔恒等式（2）等式名称x+(y+z)=(x+y)+z结合律x⋅(y⋅z)=(x⋅y)⋅zx+(y⋅z)=(x+y)⋅(x+z)分配律x⋅(y+z)=x⋅y+x⋅z(x⋅y)=x+y德摩根律(x+y)=x⋅yx+(x⋅y)=x吸收律x⋅(x+y)=xx+x=1补律x⋅x=0布尔代数的抽象定义一个布尔代数是一个集合B，它有二元运算∨和∧、一元运算以及特殊元素0和1，且∀x,y,z∈B,下列性质成立：x∨(y∨z)=(x∨y)∨z结合律x∧(y∧z)=(x∧y

6、)∧zx∨(y∧z)=(x∨y)∧(x∨z)分配律x∧(y∨z)=(x∧y)∨(x∧z)x∧y=y∧x交换律x∨y=y∨xx∨0=x同一律x∧1=xx∨x=1补律x∧x=0布尔代数举例({0,1},+,⋅,,0,1)为布尔代数n度布尔函数全体也构成一个布尔代数布尔和布尔积补函数全取0的函数、全取1的函数A的幂集也构成一个布尔代数(ρ(A),⋂,⋃,∼,∅,A）布尔代数举例nB={(x,…,x)

7、x∈B,i=1,…,n}构成布尔代数1nix=(a,…,a),y=(b,…,b),a∈B,b∈B1n1niix∧y=(c,…,c),wherec=a∧b

8、1niiix∨y=(d,…,d),whered=a∨b1niiix=(e,…,e),wheree=a1nii理解布尔代数的性质结合律、交换律、分配律、同一律、补律蕴含：支配律、吸收律、幂等律、双重补律、德摩根律证明支配律：∀x∈B,x∨1=1,x∧0=0x∨1=1∧(x∨1)=(x∨x)∧(x∨1)=x∨(x∧1)=x∨x=1x∧0=0∨(x∧0)=(x∧x)∨(x∧0)=x∧(x∨0)=x∧x=0理解布尔代数的性质证明吸收律x∨(x∧y)=(x∧1)∨(x∧y)=x∧(1∨y)=x∧1=xx∧(x∨y)=(x∨0)∧(x∨y)=x∨(0∧y)

9、=x∨0=x证明幂等律（方法一）x∨(x∧x)=x(应用吸收律）x∧x=x∧(x∨(x∧x))=x(应用吸收律）证明幂等律（方法二）x∧x=x∧(x∨0)=x(应用同一律、吸收律）理解布尔代数的性质引理：∀x,y,z∈B,若x∧z=y∧z且x∨z=y∨z，则x=yx=x∨(x∧z)=x∨(y∧z)=(x∨y)∧(x∨z)//吸收律/分配律y=y∨(y∧z)=y∨(x∧z)=(y∨x)∧(y∨z)证明双重补律x∨x=1=x∨xx∧x=0=x∧xx=x理解布尔代数的性质证明德摩根律：∀x,y∈B,(x∧y)=x∨y;根据补元的唯一性，只需证

10、明x∨y是