5.2 布尔表达式.ppt

1、11.2 布尔表达式与布尔函数,定义 设是布尔,代数,如下递归定义B上布尔表达式,(1)布尔常元和布尔变元(取值于,布尔代数B的常元和变元)是布尔,表达式.通常布尔常元用a,b,c表示,布尔变元用x,y,z表示。,(2)如果e1, e2为布尔表达式，,那么(e1),( e1e2),( e1e2)也都是,布尔表达式。,(3)除有限次使用条款(1)(2)生成的,表达式是布尔表达式外，,没有别的布尔表达式。,为了省略括号，我们约定运算的,优先级高于运算和，,并约定表达是最外层括号省略。,例 设是一个,布尔代数,那么,(23)(xy)(xz),一个变元布尔表达式,0 x,(1x)y,两个变元布尔表达式

2、,三个变元布尔表达式,常用f(x1, x2, xn), g(x1, x2, xm),等表示含有n个变元或m个变元的,布尔表达式。,给定布尔表达式并确定其中变元,的取值后,该表达式对应于一个确,定的B中的元素，,该元素就是布尔表达式的值。,定义 布尔表达式f(x1, x2, xn),所定义的函数,称为布尔函数。,例 设是一个,布尔代数，其上有表达式,f(x1, x2)=( x1a)x2,f(x1, x2, x3)=,( x1x2x3)(x1x2x3),则有：,f(1, b),=(1a)b,= ab=0,f(a, b,0)=(ab0)(ab0),=0(aa)=1,定义 布尔表达式 a1a2an,称

3、为n个变元的极小项，其中ai为,变元xi或xi。,布尔表达式 a1a2an 称为,n个变元的极大项，其中ai为变元,xi或xi。,n个变元极小项和极大项各有2n个,极小项,极大项,满足以下性质：,定义 布尔表达式f(x1, x2, xn),的主析取范式和主合取范式分别,指下列布尔表达式：,其中，ai为布尔常元，mi和Mi分别,是极小项与极大项，且两式对,x1, x2, xn一切的取值均与,f(x1, x2, xn)等值。,求主析取范式和主合取范式方法,将布尔常元看作变元,做同样处理,利用德摩根律将运算符号深入到,每个变元(常元)上。,利用分配律展开。,构成极小项或极大项缺少变元x时,加合取项(

4、xx)或析取项(xx),处理,计算合并常元、变元和表达式,(只要可能，这一步骤可随时进行),例,求布尔代数,上的布尔函数：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),的主析取范式和主合取范式。,解：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),f(0, 0)= 0,f(1, 0)= a,f(1, 1)= a,f(0, 1)= a,主析取范式,主合取范式,另解,主析取范式为：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),= ( (ax1)(x1x2) )( (bx1),(x1x2) ),= (ax1)(ax1x2),(bx1x1)(b

5、x1x2),= (ax1)(bx1x2),= ( (ax1)(x2x2 ) )(bx1x2),= (ax1x2)(ax1x2 ),(ax1x2),主合取范式为：,f(x1, x2)= ( (ax1)(bx1) )(x1x2),=( (ax1)(bx1 ) )(x1x2),= ( (ax1)b )( (ax1)x1 )(x1x2),= (ab )(bx1)(ax1 ),(x1x2),= a(ax1)(ax1 )(x1x2),(b=a),= a(x1x2),=(ax1x2)( ax1x2 ),( ax1x2)( ax1x2 ),(x1x2 ),= (x1x2 )( ax1x2 ),( ax1x2)

6、( ax1x2 ),从主析取范式和主合取范式定义,可看出，的不同的,n元主析取范式和主合取范式分别,是,个。,因在主析取范式和主合取范式中,各有|B|种取值可能。,表明,B上不同的n元布尔函数至多,是,个。,因此应当注意并非所有的Bn到B的,函数都是布尔函数，,Bn到B的函数共有,个。,另一点值得注意的是，,当主析取范式中,均取0时，该式值为0。,故0的主析取范式常简单规定为0,它表示函数f(x1, x2, xn)=0。,在主合析取范式中,均取1时，该式值为1。,故1的主析取范式常简单规定为1,它表示函数f(x1, x2, xn)=1。,计算机或其他电子装置是由许多,电路构成的,而电路就是根据布尔,代数的规则来设计的。,电路的基本元件是所谓的门，,每种类型的门实现一种布尔