5.2 布尔表达式.ppt

布尔表达式与布尔函数
定义设<B,∨,∧,’,0,1>是布尔
代数,如下递归定义B上布尔表达式
(1)布尔常元和布尔变元(取值于
布尔代数B的常元和变元)是布尔
,b,c表示
布尔变元用x,y,z表示。
(2)如果e1, e2为布尔表达式,
那么(e1’),( e1∨e2),( e1∧e2)也都是
布尔表达式。
(3)除有限次使用条款(1)(2)生成的
表达式是布尔表达式外,
没有别的布尔表达式。
为了省略括号,我们约定运算’的
优先级高于运算∨和∧,
并约定表达是最外层括号省略。
例设<{0,1,2,3},∨,∧,’,0,1>是一个
布尔代数,那么
((2∨3)’∧(x∨y)∧(x∨z)’)
一个变元布尔表达式
0∧x
(1∨x’)∧y
两个变元布尔表达式
三个变元布尔表达式
常用f(x1, x2,…, xn), g(x1, x2,…, xm)
等表示含有n个变元或m个变元的
布尔表达式。
给定布尔表达式并确定其中变元
的取值后,该表达式对应于一个确
定的B中的元素,
该元素就是布尔表达式的值。
定义布尔表达式f(x1, x2,…, xn)
所定义的函数
称为布尔函数。
例设<{0,1,a,b},∨,∧,’,0,1>是一个
布尔代数,其上有表达式
f(x1, x2)=( x1’∨a)∧x2
f(x1, x2, x3)=
( x1∧x2∧x3)’∨(x1∧x2’∧x3’)
则有:
f(1, b)
=(1’∨a)∧b
= a∧b=0
f(a, b,0)=(a∧b∧0)’∨(a∧b’∧0’)
=0’∨(a∧a)=1
定义布尔表达式 a1∧a2∧…∧an
称为n个变元的极小项,其中ai为
变元xi或xi’。
布尔表达式 a1∨a2∨…∨an 称为
n个变元的极大项,其中ai为变元
xi或xi’。
n个变元极小项和极大项各有2n个
极小项
极大项
满足以下性质:
定义布尔表达式f(x1, x2,…, xn)
的主析取范式和主合取范式分别
指下列布尔表达式:
其中,ai为布尔常元,mi和Mi分别
是极小项与极大项,且两式对
x1, x2,…, xn一切的取值均与
f(x1, x2,…, xn)等值。
求主析取范式和主合取范式方法
将布尔常元看作变元,做同样处理
利用德摩根律将运算符号’深入到
每个变元(常元)上。
利用分配律展开。
构成极小项或极大项缺少变元x时