《代数结构-布尔代数与格》由会员分享，可在线阅读，更多相关《代数结构-布尔代数与格（45页珍藏版）》请在金锄头文库上搜索。
1、布尔代数与格布尔代数与格 离散数学代数结构离散数学代数结构 南京大学计算机科学与技术系南京大学计算机科学与技术系 内容提要内容提要 布尔函数布尔函数 布尔代数布尔代数 布尔代数的抽象定义布尔代数的抽象定义 理解布尔代数的性质理解布尔代数的性质 代数格代数格 有限布尔代数的表示有限布尔代数的表示 布尔代数与数字逻辑电路设计布尔代数与数字逻辑电路设计 布尔函数布尔函数 令令B=0, 1, Bn=(x1, , xn)| xi B, i =1, , n, 从从Bn到到B 的函数称为的函数称为n度布尔函数，度布尔函数， f : BnB。 取值范围为取值范围为B的变元称为的变元称为布尔变元布尔变元 ，x
2、B。 n度布尔函数的个数：度布尔函数的个数：2 2n (22 , 24 , 28, ) 三种说法三种说法 含含n个命题变量的命题逻辑表达式个命题变量的命题逻辑表达式 n度度布尔函数布尔函数 f : BnB 有有n个输入和一个输出的逻辑电路个输入和一个输出的逻辑电路 一个逻辑电路设计的例子一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效次成绩有效, 设计一个电子打分器设计一个电子打分器, 输出一个结果输出一个结果: “成功”成功” 或”失败”。或”失败”。 布尔函数布尔函数: f(x,y,z)=1 iff.
3、x,y,z 至少有两个为至少有两个为1。 x z y 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 相应的布尔表达式相应的布尔表达式: (x y z) (x y z) (x y z) (x y z) 回顾：命题表达式的主析取范式回顾：命题表达式的主析取范式 求求 (pq) r 的主析取范式的主析取范式 (p r) (q r) (p q r ) （析取范式）（析取范式） (p q r) (p q r) (p q r) (p q r ) (p q r) (p q r) (p q r) (p q r)
4、 001 011 100 111 p r p (q q) r (p q r ) (p q r ) q r ( p q r ) (p q r ) 集合集合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)(x1, , xn)= f(x1, , xn)+g(x1, , xn) 布尔积布尔积 (f g)(x1, , xn)=f(x1, , xn) g(x1, , xn) 补函数补函数 f (x1, , xn)
5、= f(x1, , xn) 布尔恒等式（布尔恒等式（1） 等等 式式 名名 称称 x = x 双重补律双重补律 x+x = x x x = x 幂等律幂等律 x+0 = x x 1 = x 同一律同一律 x+1 = 1 x 0 = 0 支配律支配律 x+y = y+x x y = y x 交换律交换律 布尔恒等式（布尔恒等式（2） 等等 式式 名名 称称 x+(y+z)=(x+y)+z x (y z)=(x y) z 结合律结合律 x+(y z)=(x+y) (x+z) x (y+z)=x y +x z 分配律分配律 (x y) = x + y (x+y) = x y 德摩根律德摩根律 x+(
6、x y)=x x (x+y)=x 吸收律吸收律 x + x =1 x x =0 补律补律 布尔代数的抽象定义布尔代数的抽象定义 一个布尔代数是一个集合一个布尔代数是一个集合B，它有二元运算它有二元运算 和和 、一元运一元运 算算 以及特殊元素以及特殊元素0和和1，且且 x, y, z B, 下列性质成立：下列性质成立： x (y z)=(x y) z x (y z)=(x y) z 结合律结合律 x (y z)=(x y) (x z) x (y z)=(x y) (x z) 分配律分配律 x y =y x x y= y x 交换律交换律 x 0 = x x 1 = x 同一律同一律 x x =
7、1 x x =0 补律补律 布尔代数举例布尔代数举例 (0, 1, +, , , 0, 1)为布尔代数为布尔代数 n度布尔函数全体也构成一个布尔代数度布尔函数全体也构成一个布尔代数 布尔和布尔和 布尔积布尔积 补函数补函数 全取全取0的函数、全取的函数、全取1的函数的函数 A的幂集也构成一个布尔代数的幂集也构成一个布尔代数( (A), , , , , A） 布尔代数举例布尔代数举例 Bn=(x1, , xn)| xi B, i =1, , n构成构成布尔代数布尔代数 x= (a1 , , an), y=(b1 , , bn), ai B, bi B x y = (c1 , , cn), whe
8、re ci=ai bi x y = (d1 , , dn), where di=ai bi x= (e1 , , en), where ei=ai 理解布尔代数的性质理解布尔代数的性质 结合律、交换律、结合律、交换律、分配律分配律、同一律、补律同一律、补律 蕴含：蕴含：支配律、吸收律、幂等律、双重补律、德摩根律支配律、吸收律、幂等律、双重补律、德摩根律 证明支配律证明支配律： 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 理解布尔代数的性
9、质理解布尔代数的性质 证明吸收律证明吸收律 x (x y)= (x 1) (x y)= x (1 y) = x 1 = x x (x y)= (x 0) (x y)= x (0 y) = 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 ，则则
10、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; 根据补元的唯一性根据补元的唯一性，只需证明只需证明x y是是x y的补元的补元。 (x y) (x y)= (x x y ) (y x y ) =1 (x y) (x y)= (x y x ) (x y y ) =0
11、 理解布尔代数的性质理解布尔代数的性质 结合律结合律 交换律交换律 分配律分配律 同一律同一律 补律补律 支配律支配律 吸收律吸收律 幂等律幂等律 双重补律双重补律 德摩根律德摩根律 吸收律吸收律 幂等律幂等律 x (x x)= x (应用吸收律应用吸收律） x x = x ( x (x x) = x (应用吸收律应用吸收律） 代数格代数格 设设L是一个集合，是一个集合， 和和 是是L上的二元运算，且满足上的二元运算，且满足结合律、结合律、 交换律、交换律、吸收律吸收律，则称，则称(L, , )是代数格。是代数格。 代数格代数格等同于等同于（偏序）格（偏序）格 等等 式式 名名 称称 x (y
12、 z)=(x y) z x (y z)=(x y) z 结合律结合律 x y =y x x y= y x 交换律交换律 x (x y) = x x (x y) = x 吸收律吸收律 代数格中的偏序关系代数格中的偏序关系 x, y B, x y =x x y =y 若若 x y =x，则则 x y = (x y) y = y /吸收律吸收律 若若 x y =y，则则 x y = x (x y) = x /吸收律吸收律 x, y B, 定义定义 x y iff x y =x (即即 x y =y) 证明这个关系满足自反性证明这个关系满足自反性、反对称性反对称性、传递性传递性。 这个偏序构成一个格这
13、个偏序构成一个格。 lubx,y 即为即为 x y。 glbx,y 即为即为 x y。 布尔代数布尔代数VS格格 布尔代数是布尔代数是代数格代数格、也是也是（偏序偏序）格格 结合律结合律、交换律交换律、吸收律吸收律 最小上界最小上界x y，最大下界最大下界x y 布尔代数是有补的分配格布尔代数是有补的分配格 分配律分配律、同一律同一律、补律补律 关于格的对偶命题关于格的对偶命题 对偶命题的例子对偶命题的例子 a b a和和a b a互为对偶命题互为对偶命题 对偶命题构成规律对偶命题构成规律 格元素名不变格元素名不变 与与 ， 与与 全部全部互换。互换。 格的对偶原理格的对偶原理 如果命题如果命题P对对一切一切格为真，则格为真，则P的对偶命题的对偶命题P*
