布尔表达式与布尔函数

1、8.2 布尔表达式与布尔函数 定义定义8.4 设设 是布尔代数是布尔代数, B上的上的 布尔表达式布尔表达式递归定义如下递归定义如下 (1) 布尔常元和布尔变元布尔常元和布尔变元 (取值于布尔代数取值于布尔代数B的常元和的常元和 变元变元)是布尔表达式是布尔表达式. 通常布尔常元用通常布尔常元用a, b, c表示表示, 布尔布尔 变元用变元用x, y, z表示表示. (2) 如果如果e1, e2为布尔表达式为布尔表达式, 那么那么(e1), ( e1e2), ( e1e2) 也都是布尔表达式也都是布尔表达式. (3) 除有限次使用除有限次使用 (1) (2)生成的表达式是布尔表达式生成的表达式

2、是布尔表达式 外外, 再没有别的布尔表达式再没有别的布尔表达式. 为了省略括号为了省略括号, 约定约定 的运算优先级高于的运算优先级高于和和的的 运算优先级运算优先级, 并约定表达并约定表达式式最外层括号省略最外层括号省略. 8.2.1 8.2.1 布尔表达式与布尔函数布尔表达式与布尔函数 例例8.4 设设 是一个是一个 布尔代数布尔代数, 那么那么 都是布尔表达式都是布尔表达式, 并分别是含有一个变元、两个并分别是含有一个变元、两个 变元、三个变元的布尔表达式变元、三个变元的布尔表达式. 0 x，(1x)y， (23)(xy)(xz) 通常用通常用 f(x1, x2, xn), g(x1,

3、x2, xm)等表示等表示 当给定布尔表达式并确定其中变元的取值当给定布尔表达式并确定其中变元的取值 后后, 该表达式对应于一个确定的该表达式对应于一个确定的B中的元素中的元素, 该元该元 素就是布尔表达式的值素就是布尔表达式的值. 含有含有n个变元或个变元或m个变元的布尔表达式个变元的布尔表达式. 定义定义8.5 布尔表达式布尔表达式 f (x1, x2, xn)所定义的函数所定义的函数 称为称为布尔函数布尔函数. BBf n : 例例8.5 设设 是一个布尔是一个布尔 代数代数, （a,b互为补元）其上有表达式互为补元）其上有表达式 f(x1, x2)=( x1a)x2 f(x1, x2,

4、 x3)=( x1x2x3)(x1x2 x3) 则则: f(1, b)=(1a)b=ab= 0 f(a, b, 0)= (ab0)(ab 0) = 0(aa)=1 定义定义8.6 布尔表达式布尔表达式 a1a2an 称为称为n个个 变元的变元的极小项极小项，其中，其中ai为变元为变元xi或或xi . 布尔表达布尔表达 式式 a1a2an 称为称为n个变元的个变元的极大项极大项, 其中其中 ai为变元为变元 xi 或或 xi . 说明说明: n个变元的极小项和极大项各有个变元的极小项和极大项各有2n个个, 分别用分别用 和 12 10 , n mmm., 12 10 来表示 n MMM 极小项和

5、极大项满足以下性质：极小项和极大项满足以下性质： )(1, 0jiMMmm jiji (1) (2) 0, 1 12 10 12 10 nn MMMmmm 定义定义8.7 布尔表达式布尔表达式 f(x1, x2, , xn)的的主析取范式主析取范式 和和主合取范式主合取范式分别指下列布尔表达式：分别指下列布尔表达式： )()()( )()()( 1212 1100 1212 1100 nn nn MaMaMa mamama 其中其中: ai为布尔常元为布尔常元, mi和和Mi分别是极小项与极分别是极小项与极 大项大项, 且两式对且两式对x1, x2, , xn的一切取值均与的一切取值均与 f(

6、x1, x2, , xn)等值等值. 5) 计算合并常元、变元和表达式计算合并常元、变元和表达式.（可随时（可随时 进行）进行） 主析取范式和主合取范式的求法：主析取范式和主合取范式的求法： 1) 将布尔常元看作变元做同样的处理将布尔常元看作变元做同样的处理; 2) 利用德摩根律将运算符号利用德摩根律将运算符号 深入到每个变深入到每个变 元元 (常元常元)上上. 3) 利用分配律展开利用分配律展开. 4) 构成极小项或极大项缺少变元构成极小项或极大项缺少变元x时时, 用添加合用添加合 取项取项(xx)或析取项或析取项(xx)来处理来处理. 取范式和主合取范式取范式和主合取范式. 例例8.6 求

7、布尔代数求布尔代数 上布上布 尔函数尔函数 f(x1, x2)= (ax1)(bx1) (x1x2)的主析的主析 解解: 主析取范式为主析取范式为 f(x1, x2)= (ax1)(bx1) (x1x2) = (ax1x2)(ax1x2 )(ax1x2) (b=a) = (ax1)(x1x2) (bx1)(x1x2) = (ax1 x1)(ax1x2) (bx1x1)(bx1x2) = (ax1)(bx1x2) = ( (ax1)(x2x2 ) )(bx1x2) = (ax1 )(ax1x2)(bx1x1)(bx1x2) 主合取范式为：主合取范式为： f(x1, x2)= (ax1)(bx1)

8、 (x1x2) = (ax1)(bx1 ) (x1x2) = (ax1)b )( (ax1)x1 (x1x2) = (ab )(bx1)(ax1 )(x1x1)(x1x2) = (ab )(bx1)(ax1 )(x1x2) = a(ax1)(ax1 )(x1x2) (b=a) = a (a（x1x1 )）(x1x2) = a a(x1x2) = a(x1x2) = (ax1x2)( ax1x2 )( ax1x2) ( ax1x2 )(x1x2 ) = (x1x2)(ax1x2)(ax1x2)(ax1x2) 说明说明: 1) 从主析取范式和主合取范式的定义可以看出从主析取范式和主合取范式的定义可

9、以看出, 的不同的的不同的n元主析取范式和主元主析取范式和主 合取范式分别是合取范式分别是 n B 2 |个，个， 因为在主析取范式和主因为在主析取范式和主 合取范式中，合取范式中， 12 10 , n aaa 各有各有|B|种取值可能种取值可能. 这表明这表明, B上不同的上不同的n元布尔函数至多是元布尔函数至多是 n B 2 | 个，个， 因此并非所有的因此并非所有的Bn到到B的函数都是布尔函数的函数都是布尔函数. 2) 当主析取范式中当主析取范式中 12 10 , n aaa 均取均取0时时, 该式该式 的值为的值为0， 因此因此0的主析取范式常简单的规定为的主析取范式常简单的规定为0， 它表示函数它表示函数 f(x1, x2, , xn)= 0. 当主合取范式中当主合取范式中 12 10 , n aaa 均取均取1时时, 该式该式 的值为的值为1， 因此因此1的主合取范式常简单的规定为的主合取范式常简单的规定为1， 它表示函数它表示函数 f(x1, x