罗平翻译的高等离散结构教材.ppt

例1 下面是以x, y和z为变量的布尔多项式。 p1(x, y, z)=(x∨y)∧z p2(x, y, z)=(x∨y?)∨(y∧1) p3(x, y, z) = (x∨( y?∧z))∨(x∧( y∧1)) p4(x, y, z) = (x∨( y∨z?))∧((x?∧z)?∧( y?∨0)) 通常有几个变量的多项式，例如x2y + z4, xy + yz + x2y2, x3y3 + xz4等，一般理解为表示未指定数值的代数计算表达式。所以，它们应服从通常的算术法则。因此，多项式x2+2x+1和(x+1)(x+1)被认为是相等的，x(xy + yz)(x + z)和x3y +2x2yz + xyz2也是相等的，因为在每一种情况下，可以用代数运算使它们互相转化。 * 类似地，布尔多项式也可以理解为表示未指定的B中元素即0和1的布尔计算。因此，这些多项式应服从布尔算术法则，即布尔代数中∧，∨和?所服从的法则。与通常的多项式一样，如果能把两个布尔多项式用布尔运算互相转化，则认为这两个布尔多项式是等价的。 在5.1节给出了怎样用通常的多项式通过替换产生函数。该过程所使用的多项式包含一个变量或者几个变量。因此，多项式xy+yz3通过设f?(x, y, z) = xy + yz3产生一个函数f∶R3→R。例如，f?(3, 4, 2) = (3)(4) +(4)(23) = 44。用类似的方法，含有n个变量的布尔多项式产生从Bn到B的函数。这些布尔函数是5.2节所介绍的那些函数的一个自然推广。 * 例2 考虑布尔多项式 p(x1, x2, x3)=( x1∧x2)∨(x1∨(x2?∧x3))， 为由此布尔多项式所确定的布尔函数f∶B3→B构造真值表。 解 布尔函数f∶B3→B可以通过用B中所有23个有序三元组替代x1, x2和x3来描述。所得函数的真值表如图6.72所示。 * 布尔多项式也能用图示或图解的方式表达。如果x和y是变量，那么在图6.73中用图解方式给出了基本多项式x∨y，x∧ y和x?。左边的每条符号线代表变量，右边的一条线表示整个多项式。代表x∨y的符号称作或门，代表x∧y的符号称作与门，代表x?的符号称作反相器。出现逻辑名字是因为由x∨y和x∧y表示的函数所给出的真值表确实分别类似于联结词“或”和“与”的真值表。 回顾从Bn到B的函数能够用来描述n个0或1输入和一个0或1输出的理想电路的情况。至于对应于布尔多项式x∨y，x∧y和x?的函数，这些理想电路能够被实现，并且常用图6.73的图解形式来表示这些电路。通过重复地用这些图解形式替代∨，∧和?，能够用图解形式表示任何布尔多项式。由于上述这些原因，这种图称作多项式的逻辑图。 * 例3 设p(x, y, z)=(x∧y)∨(y∧z?)，图6.74(a)给出了对应函数f∶B3→B的真值表，图6.74(b)给出了p的逻辑图。 * 假设p是有n个变量的布尔多项式，f是从Bn到B的对应函数，那么f可以看成是描述有n个输入和一个输出的电路情况。同样，p的逻辑图能够看成是描述至少是根据与门、或门以及反相器这种电路构造。因此，如果描述理想电路的函数f能够通过布尔多项式p产生，那么p的逻辑图将给出构造这种情况电路的一种方法。一般地，许多不同的多项式会产生相同的函数。这些多项式的逻辑图为构造理想的电路提供了可选择的方法，它对计算机电路研究的重要性怎样估计都不过分。尽管所有的电路设计基本上都是通过软件包实现的，但是理解本节和下一节所总结的电路设计基本原理是非常重要的。 * 例12 设L是一个全序集，如果a,b∈L，那么或者a≤b或者b≤a。从定理2可知L是一个格，因为每对元素有最小上界和最大下界。定理3 设L是一个格，那么 1. 幂等性质 (a) a∨a = a (b) a∧a = a 2. 交换性质 (a) a∨b = b∨a (b) a∧b = b∧a 3. 结合性质 (a) a∨(b∨c) = (a∨b)∨c (b) a∧(b∧c) = (a∧b)∧c 4. 吸收性质 (a) a∨(a∧b) = a (b) a∧(a∨b) = a 证明 1. 命题从LUB和GLB的定义可得到。 2. LUB和GLB的定义对a和b是对称的，所以结论成立。 * 3. (a) 从LUB的定义得到a≤a∨(b∨c)和b∨c≤a∨(b∨c)。而且b≤b∨c和c≤b∨c，于是由传递性得b≤a∨(b∨c)和c≤a∨(b∨c)。因此，a∨(b∨c)是a和b的一个上界，所以由最小上界的定义有 a∨b≤a∨(b∨c) 因为