离散数学课件：6-4布尔表达式.ppt

四、布尔表达式
（一）布尔表达式
设<A, , , >是布尔代数，
布尔常元：A中的元素；
布尔变元：以A为取值范围的变元；
布尔表达式 (Boolean expressions ) ：
(1)A中任何元素（即布尔常元）是布尔表达式；
(2)任何布尔变元是布尔表达式；
(3)若e1, e2是布尔表达式，则 (e1 e2), (e1 e2)都是布尔表达式；
(4)有且只有通过有限次地运用规则(2), (3)所构造的符号串是布尔表达式.
我们见过类似的定义方式：命题演算的合式公式；谓词演算的合式公式.
<A, , , >是布尔代数，则
(1)
a,
(1  x1) x2,
1  x1,
含有两个变元x1, x2的布尔表达式；
这里(2), (3), (4)式分别称为
都是布尔表达式，这里x1, x2, x3是布尔变元.
四、布尔表达式
(2)
(3)
(4)
含有单个变元x1的布尔表达式；
含有三个变元x1, x2, x3的布尔表达式.
n元布尔表达式
布尔表达式的值：设<A, , , >是布尔代数，n元布尔表达式E(x1, x2, …, xn)的值是指：将A中的布尔常元作为变元xi的值来代替表达式中相应的变元（即对变元赋值），从而计算得出的表达式的值.
n元布尔表达式：一个含n个相异变元的布尔表达式，称为n元布尔表达式，记作
E(x1, x2, …, xn),
其中x1, x2, …, xn为布尔变元.
n元布尔表达式
E(x1, x2, x3)=
<{0, 1}, , , >上的一个三元布尔表达式为
当赋值为x1=1, x2=0, x3=1时, 其值为：
E(1,0,1)=
=110
=0.
布尔表达式的等价
布尔表达式的等价：设 E1(x1, x2, …, xn)和E2(x1, x2, …, xn)是布尔代数<A, , , >上的两个n元布尔表达式，若对n个变元的任意赋值xi=ai, aiA, i=1, 2,…, n均有
E1(a1, a2, …, an)= E2(a1, a2, …, an)
则称布尔表达式E1, E2是等价的，记作：
E1(x1, x2, …, xn)=E2(x1, x2, …, xn).
这类似于定义“命题公式的等价”、“谓词公式的等价”.
<{0, 1}, , , >上的两个布尔表达式
是等价的.
E1(x1, x2, x3)=
E2(x1, x2, x3)=
方法一：对{x1, x2, x3}的8组可能取值一一验证，比如：
E1(0, 0, 0)=
=00
=0,
E2(0, 0, 0)=
=01
=0.
方法二：直接由运算规律验证：
E2(x1, x2, x3)=
=E1(x1, x2, x3).
（二）布尔函数
设 E(x1, x2, …, xn)是布尔代数<A, , , >上的一个n元布尔表达式，因为运算, , 在A上封闭，任意有序n元组<a1, a2, …,an>(aiA), 可以对应着布尔表达式E(x1, x2, …, xn)的一个值，这个值必属于A.
因此，E(x1, x2, …, xn)确定了一个由An到A的函数.
布尔函数： 设<A, , , >是布尔代数，一个由An到A的函数若能用<A, , , >上的一个n元布尔表达式来表示，则称该函数为布尔函数.
一个由An到A的函数不一定能用<A, , , >上的一个布尔表达式来表示.
={0, 1}, 下面的表格表示了一个从A3到A的函数f,问该函数是否是布尔函数?
解：
因为f可以表示为布尔表达式：
E1(x1, x2, x3)=
x1
0
0
0
0
1
1
1
1
x2
0
0
1
1
0
0
1
1
x3
0
1
0
1
0
1
0
1
f
0
0
1
0
1
1
0
1
所以f是布尔函数.
小项&大项
一个含有n个变元x1,x2,…, xn 的布尔表达式，如果它有形式
( )( )…( )
其中()是xi或 中的任一个，则我们称这个布尔表达式为小项.
如果它有形式
( )( )…( )
其中()是xi或 中的任一个，则我们称这个布尔表达式为大项.
每个位置xi或 必出现且仅出现一次.
小项