离散数学第12讲布尔表达式

1、1离散数学（二）离散数学（二）布尔表达式布尔表达式布尔表达式布尔表达式1 11 1布尔表达式主范式与布尔代数布尔表达式主范式与布尔代数2 2主要内容主要内容: :布尔表达式的定义布尔表达式的定义重点重点: : 重点和难点重点和难点: :布尔表达式与布尔代数的关系布尔表达式与布尔代数的关系3 3布尔表达式主范式布尔表达式主范式难点难点: : 一、布尔表达式一、布尔表达式问题的引入问题的引入: : 我们知道在布尔代数上, “”关于“”是可分配的, 所以a(bc)=(ab)(ac) 是上的一个恒等式. 那么如何判定上的两个表达式是恒等式? 上有多少种互不恒等的表达式? 为了回答这些问题,我们先引入布

2、尔表达式的我们先引入布尔表达式的概念概念, 然后通过把然后通过把表达式化为规范形式的方法来判定两个表达式是表达式化为规范形式的方法来判定两个表达式是否恒等否恒等.一、布尔表达式一、布尔表达式 设是一个布尔代数,现在考虑一个从Bn到B的函数。设B=0, 1, 下表给出了一个从B3到B的函数f。一、布尔表达式一、布尔表达式设B=0,a,b,1, 右表给出了一个从B2到B的函数。一、布尔表达式一、布尔表达式 下面我们试图用别的方法来描述函数,使之具有紧凑的形式.为此先引入布尔表达式的概念。 定义定义1 设是一个布尔代数,取值于B中元素的变元称为布尔布尔变元变元; B中的元素称为布尔常元布尔常元。 定

3、义定义2 设是一个布尔代数,这个布尔代数上的布尔表达式定义如下: (1)单个布尔常元是一个布尔表达式; (2)单个布尔变元是一个布尔表达式; (3)如果e1和e2是布尔表达式,则 ( ),(e1e2),(e1e2)也是布尔表达式;1e(4) 有限次应用规则1-3形成的字符串是布尔表达式布尔表达式。一、布尔表达式一、布尔表达式 定义定义3 一个含有n个相异变元的布尔表达式,称为n元元布尔表达式布尔表达式, 记为E(x1,x2,xn)或f (x1,x2,xn), 其中x1, x2, xn是式中可能含有的布尔变元。 我们约定运算“”、“”和“”的优先级依次为“”,“”,“”。这样一来, 布尔表达式中

4、的某些圆括号可以省略, 约定类似于命题公式。 例例2 设是布尔代数,则 f1=a f2=0 x f3=(1x1)x2 f4= f5= f6= 都是这个布尔代数上的布尔表达式。 1212()(1)()abxxxx ) )()()( (3121xxxxba)(3211xxxx一、布尔表达式一、布尔表达式 定义定义4 布尔代数上的布尔表达式f(x1,x2,xn)的值是指:将B的元素作为变元xi(i=1,2,n)的值而代入表达式以后(即对变元赋值),计算出来的表达式的值。 例例3 (a) 取x1=a, x2=b,则例2中的f3的值是 f3=(1a)b=ab=1 (b) 设布尔代数上的表达式 f(x1,

5、x2,x3)= , 则 f (1,0,1)=(01)(01) =010=0)()()(322121xxxxxx) 10( 一、布尔表达式一、布尔表达式 定义定义5 布尔代数上两个n元布尔表达式f1(x1,x2,xn)和f2(x1,x2,xn),如果对n个变元的任意指派, f1和f2的值均相等,则称这两个布尔表达式是等价的或相等的等价的或相等的。记作f1(x1,x2,xn)=f2(x1,x2,xn)。 在实践上,如果能有限次应用布尔代数公式,将一个布尔表达式化成另一个表达式,就可以判定这两个布尔表达式是等价的。 例例4 在布尔代数上的两个布尔表达式f1(x1, x2, x3)=(x1x2)(x1

6、x3)和f2(x1, x2, x3)=x1(x2x3)是等价的。二、布尔表达式主范式与布尔代二、布尔表达式主范式与布尔代数数 定义5给出的等价(或相等)关系将n元布尔代数表达式集合划分成等价类,处于同一个等价类中的表达式都相互等价(或相等) 。可以证明当|B|有限时,等价类数目是有限的。为此,我们考察以下定义。 定义定义6 给定n个布尔变元x1,x2,xn, 表达式称为极小项极小项。这里 表示xi或 两者之一。 12nxxxixix 定义定义7 具有如下形式的布尔表达式称为主析取范式主析取范式。这里mi是极小项,i是布尔常元。(i=0,1,2,2n-1)。12121100nnmamama二、布

7、尔表达式主范式与布尔代二、布尔表达式主范式与布尔代数数 德德摩根定律摩根定律非(P 且 Q)(非 P)或(非 Q) 非(P 或 Q)(非 P)且(非 Q) 定义定义7中的主析取范式个数: 因为i有|B|种取法,故不同的主析取范式有 个。特别, B=0,1时有 个。2nB22n 任何一个n元布尔表达式都唯一地等价于一个主析取范式。把一个n元布尔表达式化成等价的主析取范式,主要应用德摩根定律等,其方法与“数理逻辑”中化成主析取范式的方法完全一致。 二、布尔表达式主范式与布尔代二、布尔表达式主范式与布尔代数数平行地可讨论极大项极大项和主合取范式主合取范式: 定义定义8 给定n个布尔变元x1,x2,x

8、n, 表达式称为极大项极大项。这里 表示xi或 两者之一。ixixnxxx21显然,有2n个不同的极大项, 分别记为M0, M1, M2 , .21nM定义定义9 具有如下形式的布尔表达式称为主合取范式主合取范式。这里Mi是极大项, i是布尔常元, (i=0,1,2,2n-1) 。 )()()(12121100nnMaMaMa 任何一个n元布尔表达式都唯一地等价于一个主合取范式。2n个极大项最多只能造出 个不同的主合取范式。所以,一个n元布尔表达式必等价于这 个主合取范式之一。2nB2nB二、布尔表达式主范式与布尔代二、布尔表达式主范式与布尔代数数例例5 将布尔代数上的布尔表达式 化成主析取范

9、式。 )()()(),(2121121xxbxxxaxxf)()()(),(2121121xxbxxxaxxf)()()()()()()()()()()(132121212121211212111mamxxaxxxxbxxaxxaxxbxaxxbxxaxxa三、布尔函数三、布尔函数 布尔代数上的任一n元布尔表达式f(x1,x2,xn), 对n个变元的每一指派, 都可得到相应的表达式的值, 这值属于B。所以, f(x1,x2,xn)可视为Bn到B的函数。但n个变元的主析取范式(或主合取范式)最多只有 个,所以,至多只能代表 个不同的函数。从Bn到B的函数共有 个。现分情况讨论:2nB2nBnBB(1) B=0,1时,从Bn到B的函数共有 个, 主析取范式也有 个,恰好每一主范式代表一个函数。所以,在B=0,1时,每一函数均可用布尔表达式表示.22n22n(2) B0,1时,例如B=0,a,b,1时,从Bn到B的函数共有 个,但主析取范式仍只有 个,所以,不是每一函数都可用布尔表达式表示。44n24n三、布尔函数三、布尔函数 定义定义10 设是一个布尔代数,一个从Bn到B的函数,如果能够用该布尔代数