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’)∧(x1,x2,…,xn),g(x1,x2,…,xm)等表示含有n个变元或m个变元的布尔表达式。给定布尔表达式并确定其中变元的取值后,该表达式对应于一个确定的B中的元素,该元素就是布尔表达式的值。(x1,x2,…,xn)所定义的函数称为布尔函数。例设<{0,1,a,b},∨,∧,’,0,1>是一个布尔代数,其上有表达式f(x1,x2)=(x1’∨a)∧x2f(x1,x2,x3)=(x1∧x2∧x3)’∨(x1∧x2’∧x3’)则有:f(1,b)=(1’∨a)∧b=a∧b=0f(a,b,0)=(a∧b∧0)’∨(a∧b’∧0’)=0’∨(a∧a)=∧a2∧…∧an称为n个变元的极小项,其中ai为变元xi或xi’。布尔表达式a1∨a2∨…∨an称为n个变元的极大项,其中ai为变元xi或xi’。:(x1,x2,…,xn)的主析取范式和主合取范式分别指下列布尔表达式:其中,ai为布尔常元,mi和Mi分别是极小项与极大项,且两式对x1,x2,…,(x1,x2,…,xn)等值。求主析取范式和主合取范式方法将布尔常元看作变元,做同样处理利用德摩根律将运算符号’深入到每个变元(常元)上。利用分配律展开。