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

1
离散数学(二)
布尔表达式
布尔表达式
11
布尔表达式主范式与布尔代数
2
主要内容:
布尔表达式的定义
重点:
重点和难点:
布尔表达式与布尔代数的关系
3
布尔表达式主范式
难点:
一、布尔表达式
问题的引入:
我们知道在布尔代数<B,∨,∧,ˉ>上, “∨”关于“∧”是可分配
的, 所以
a∨(b∧c)=(a∨b)∧(a∨c)
是<B,∨,∧,ˉ>上的一个恒等式.
那么如何判定<B,∨,∧,ˉ>上的两个表达式是恒等式? <B,∨,∧,ˉ>
上有多少种互不恒等的表达式?
为了回答这些问题,我们先引入布尔表达式的概念, 然后通过把
表达式化为规范形式的方法来判定两个表达式是否恒等.
一、布尔表达式
设<B,∨,∧,ˉ>是一个布尔代数,现在考虑一个从Bn到B的函数。
设B={0, 1}, 下表给出了一个从B3到B的函数f。
一、布尔表达式
设B={0,a,b,1}, 右表给出
了一个从B2到B的函数。
一、布尔表达式
下面我们试图用别的方法来描述函数,
入布尔表达式的概念。
定义1 设<B,∨,∧,ˉ>是一个布尔代数,取值于B中元素的变元称为布尔
变元; B中的元素称为布尔常元。
定义2 设<B,∨,∧,ˉ>是一个布尔代数,这个布尔代数上的布尔表达式定
义如下:
(1)单个布尔常元是一个布尔表达式;
(2)单个布尔变元是一个布尔表达式;
(3)如果e1和e2是布尔表达式,则
( ),(e1∨e2),(e1∧e2)也是布尔表达式;
(4) 有限次应用规则1-3形成的字符串是布尔表达式。
一、布尔表达式
定义3 一个含有n个相异变元的布尔表达式,称为n元布尔表达式, 记为E
(x1,x2,…,xn)或f (x1,x2,…,xn), 其中x1, x2,…, xn是式中可能含有的布尔变元。
我们约定运算“∨”、“∧”和“ˉ”的优先级依次为“ˉ”,“∧”,
“∨”。这样一来, 布尔表达式中的某些圆括号可以省略, 约定类似于
命题公式。
例2 设<{0, a, b, 1}, ∨, ∧,ˉ, 0, 1>是布尔代数,则
f1=a f2=0∧x f3=(1∧x1)∨x2
f4=
f5=
f6=
都是这个布尔代数上的布尔表达式。
一、布尔表达式
定义4 布尔代数<B,∨,∧,ˉ>上的布尔表达式f(x1,x2,…,xn)的值是指:将B的元素作为变元xi(i=1,2,…,n)的值而代入表达式以后(即对变元赋值),计算出来的表达式的值。
例3
(a) 取x1=a, x2=b,则例2中的f3的值是
f3=(1∧a)∨b=a∨b=1
(b) 设布尔代数<{0,1},∨,∧,ˉ, 0, 1>上的表达式
f(x1,x2,x3)= , 则
f (1,0,1)=(0∧1)∧(0∨1)∧=0∧1∧0=0
一、布尔表达式
定义5 布尔代数<B,∨,∧,ˉ, 0, 1>上两个n元布尔表达式f1(x1,x2,…,xn)和f2(x1,x2,…,xn),如果对n个变元的任意指派, f1和f2的值均相等,则称这两个布尔表达式是等价的或相等的。记作f1(x1,x2,…,xn)=f2(x1,x2,…,xn)。
在实践上,如果能有限次应用布尔代数公式,将一个布尔表达式化成另一个表达式,就可以判定这两个布尔表达式是等价的。
例4 在布尔代数<{0,1},∨,∧,ˉ>上的两个布尔表达式f1(x1, x2, x3)=(x1∨x2)∧(x1∨x3)和f2(x1, x2, x3)=x1∨(x2∧x3)是等价的。
二、布尔表达式主范式与布尔代数
定义5给出的等价(或相等)关系将n元布尔代数表达式集合划分成等价类,处于同一个等价类中的表达式都相互等价(或相等) 。可以证明当|B|有限时,等价类数目是有限的。为此,我们考察以下定义。
定义6 给定n个布尔变元x1,x2,…,xn, 表达式
称为极小项。这里表示xi或两者之一。
定义7 具有如下形式
的布尔表达式称为主析取范式。这里mi是极小项,αi是布尔常元。(i=0,1,2,…2n-1)。