南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）代数系统——第20章 布尔代数

布尔代数 离散数学一代数结构 南京大学计算机科学与技术系

布尔代数 离散数学－代数结构 南京大学计算机科学与技术系

内容提要 ·布尔函数 ·布尔代数 ·布尔代数的抽象定义 。布尔代数的性质 ·有限布尔代数 ·布尔代数与数字逻辑电路设计

内容提要  布尔函数  布尔代数  布尔代数的抽象定义  布尔代数的性质  有限布尔代数  布尔代数与数字逻辑电路设计 2

布尔函数 ●令B=0,1},B={c1,,x川x,∈B,i=1,,n,从B到B 的函数称为n度布尔函数，f:Bn→B。 ·取值范围为B的变元称为布尔变元，x∈B。 ●n度布尔函数的个数：2个2n(22,24,28,…) ·三种说法 。含个命题变量的命题逻辑表达式 ●n度布尔函数f:Bm→B 。有n个输入和一个输出的逻辑电路 3

布尔函数  令B={0, 1}, Bn={(x1 , …, xn )| xiB, i =1, …, n}, 从Bn到B 的函数称为n度布尔函数， f : BnB。  取值范围为B的变元称为布尔变元 ，xB。  n度布尔函数的个数：22 n (22 , 24 , 28 , …)  三种说法  含n个命题变量的命题逻辑表达式  n度布尔函数 f : BnB  有n个输入和一个输出的逻辑电路 3

一个逻辑电路设计的例子 举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效，设计一个电子打分器，输出一个结果：“成功” 或”失败”。 布尔函数：fc,y,z)=1if.xy,z fx,v,) 至少有两个为1。 0 0 0 0 0 0 1 0 0 1 0 0 相应的布尔表达式： 0 1 1 1 (x'NNZ)V (AV)V 1 0 0 0 AVAZ)V (XAVAZ) 1 0 1 1 0 1 1 1 1

一个逻辑电路设计的例子  举重比赛中三个裁判中两个或者两个以上判定为成功则该 次成绩有效, 设计一个电子打分器, 输出一个结果: “成功” 或”失败”。 布尔函数: f(x,y,z)=1 iff. x,y,z 至少有两个为1。 x y z 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) 4

回顾：命题表达式的主析取范式 。求(p→)分r的主析取范式 (pAr)v(MAr)V(PA-qN-T)(析取范式) PΛr←→PΛ(qVq)Λr →(pΛq∧r)V(pΛqΛ) 9∧→(p∧IAr)V(pΛ4Ar) 。(PAqA)V(-p∧qΛ)V(PAqA)Y (pAgn-T) ●(P∧qΛ)V(P∧qΛ)V(PAqA)VpΛq∧) 001 011 100 111 5

回顾：命题表达式的主析取范式  求 (pq)  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)  001 011 100 111 ¬p  r  ¬p  (¬q  q)  r  (¬p  ¬q  r )  (¬p  q  r ) q  r  ( p  q  r )  (¬p  q  r ) 5

集合{0,1}上的运算 ·布尔和 ●1+1=1,1+0=1,0+1=1,0+0=0 ·布尔积 ●11=1,1.0=0,0.1=0,00=0 。补 。0=1,1=0 6

集合{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 6

布尔函数上的运算 ●布尔和 (f+g)(x12...,)=f(x1,...,xn)tg(x1,...,xn) ●布尔积 (fg)(x12...,xn)=f(12...,xn).g(1,...,xn) ·补函数 ●f(c1,,xn=f1,,Xn 7

布尔函数上的运算  布尔和  (f+g)(x1 , …, xn )= f(x1 , …, xn )+g(x1 , …, xn )  布尔积  (f g)(x1 , …, xn )=f(x1 , …, xn ) g(x1 , …, xn )  补函数  f (x1 , …, xn )= f(x1 , …, xn ) 7

布尔恒等式（1) 等式 名称 元=X 双重补律 x+x=x 幂等律 xx=x x+0=x 同一律 x.1=x x+1=1 支配律 x0=0 x+y=y+x 交换律 xy=yx R

布尔恒等式（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 交换律 8

布尔恒等式(2) 等式 名称 x+0y+z)=(x+y)+z 结合律 x0yz=(xy)·z x+(v-)=(x+y)(x+) 分配律 x.y+)=xy+x. (x.y)=x+j 德摩根律 x+y=天.y x+(xy)=x 吸收律 x.(x+y)=x x+x=1 补律 x·x=0 9

布尔恒等式（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+(xy)=x x (x+y)=x 吸收律 x + x =1 x  x =0 补律 9

布尔代数的抽象定义 。一个布尔代数是一个集合B,它有二元运算V和入、一元运 算-以及特殊元素0和1，且x,y,z∈B,下列性质成立： xv(vz)=(xvy)vz 结合律 xΛy入Z=(xΛy∧Z xV(AZ)=(xV)A(xVZ) 分配律 xA(VZ)=(xA)V(xAZ) XAV EAX 交换律 xVy-yvx xv0=x 同一律 X∧1=X xvx=1 补律 xA元=0 o

布尔代数的抽象定义  一个布尔代数是一个集合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 =1 x  x =0 补 律 10