离散数学6-5.ppt

主要内容
用偏序集定义的格
1
用代数系统定义的格
2
特殊格
3
布尔代数
4
布尔表达式
5
1
设<A,∨,∧, - >是布尔代数,考虑一个从An到A的函数,
例如设A={0,1},则下表表示了一个A3到A的函数 f
< x1, x2 , x3 > f
< 0, 0, 0 > 1
< 0, 0, 1 > 0
< 0, 1, 0 > 1
< 0, 1, 1 > 0
< 1, 0, 0 > 1
< 1, 0, 1 > 1
< 1, 1, 0 > 0
< 1, 1, 1 > 1
2
定义1:设<A,∨,∧, - >是一个布尔代数,并在这个布尔代数上
定义布尔表达式如下:
1、A中任何元素是一个布尔表达式
2、任何变元是一个布尔表达式
3、如果e1和e2是布尔表达式,则e1、(e1∨e2)和
(e1∧e2)也都是布尔表达式。
4、只有有限次使用规则2和3所得到的符号串是
布尔表达式。
定义2:一个含有n个相异变元的布尔表达式,称为
含有n元的布尔表达式。
记为E(x1,x2,…,xn),其中x1,x2,……,xn为变元。
3
定义3:布尔代数<A,∨,∧, - >上的一个含有n元的布尔表达式
E(x1,x2,…,xn)的值是指:将A中的元素作为变元xi
(i=1,2,…,n)的值来代替表达式中相应的变元(即对变
元赋值),从而计算出表达式的值。
例:布尔代数<{0,1},∨,∧, - >上布尔表达式
E (x1,x2,x3) = ( x1∨x2 )∧( x1∨x2 )∧( x2∨x3 )
若给定变元赋值 x1=1, x2=0, x3=1,
则可求出布尔表达式的值:
E ( 1, 0, 1) = ( 1∨0 )∧( 1∨0 )∧( 0∨1 )
= 1∧1∧0 = 0
4
定义4:布尔代数<A,∨,∧, - >上的两个n元的布尔表达式为
E1(x1,x2,…,xn)和E2(x1,x2,…,xn),如果对n个变元的任
意赋值 xi = xi*, xi*A 时都有
E1(x1*,x2*,…,xn*) = E2(x1*,x2*,…,xn*)
则称这两个布尔表达式是等价的(相等的)。
记为 E1(x1,x2,…,xn) = E2(x1,x2,…,xn)
5
例:布尔代数<{0,1},∨,∧, - >上两个布尔表达式
E1 (x1,x2,x3) = ( x1∧x2 )∨(x1∧x3 )
E2 (x1,x2,x3) = x1∧(x2 ∨x3 )
求证 E1 = E2
证明:(1)按照布尔表达式相等的定义证明
< x1, x2 , x3 > E1 E2
< 0, 0, 0 > 0 0
< 0, 0, 1 > 0 0
< 0, 1, 0 > 0 0
< 0