离散数学课件-第1章-8(上.ppt

1 离散数学 Discrete Mathematics 汪荣贵贵 教授 合肥工业业大学软软件学院专专用课课件 2010.05 第一章第一章 逻辑与证明逻辑与证明 类似地，布尔积 具有值1当且仅当x=z=0且y=1. 这两个布尔积的布尔和 就表示G,因为它具有值1当 且仅当x=y=1且z=0，或x=z=0且y=1。 例1说明了一个过程，用这个过程可以构造布尔表达式来表示 具有给定值的函数。如果变元值的一个组合使得函数值为1， 则此组合确定了变元或其补的一个布尔积。 定义1： 布尔变元或其补称为文字。布尔变元x1,x2,xn的小项 是一个布尔积y1y2yn,其中 或 。因此小项是n 个文字的积，每个文字对应于一个变元。 注：一个小项对一个且只对一个变元值的组合取值1，更确切地 ，小项y1y2yn为1当其仅当每个yi为1，当且仅当 时xi 为1， 时xi为0. 通过取不同小项的布尔和，就能构造布尔表达式，使其具有给定的 值集合。 特别地，小项的布尔和具有值1仅当和中的某个小项具有值1时才成立； 对于变元值的其他组合，它具有值0.因此，给定一个布尔函数，可以构造小 项的布尔和使得：当此布尔函数具有值1时它的值为1，当次布尔函数具有值0 时它的值为0.此布尔和中的小项与使得此函数值为1的值的组合相对应。表示 布尔函数的小项的和称为此函数的积之和展开式或析取范式。 【example 2】求一个小项项使得：当x1=x3=0且x2=x4=x5=1时时 ，它为为1；否则则它为为0。 得到小项项 具有正确的值值。 【example 3】求函数 的积之和展开式。 Solution： 下面用两种方法求 的积之和展开式。 第一种方法就是用布尔恒等式将这个积展开然后化简。过程如下 ： 构造积之和展开式的第二种方法是： 对x、y和z所有可能的取值都计算出F的值，这些值见下表。 F的积积之和展开式是三个小项项的布尔积积，这这三个小项对应项对应 于下 表 的三行，它们们使此函数的值为值为 1.从而 也可以通过取布尔和的布尔积来求一个布尔表达式，使其表 示一个布尔函数，所得到的展开式称为这个函数的合取范式 或和之积展开式，这个展开式可以通过求积之和展开式的对 偶而得到。 2. 函数完全性 每个布尔函数都可以表示为小项的布尔和。每个小项都是布 尔变元或其补的布尔积。 这说明了每个布尔函数都可以用布尔运算.、+和- 来表示。因 为每个布尔函数都可以由布尔运算表示，我们称集合 是 函数完全的。 还有没有更小的函数完全运算集合呢？如果这三个运算中的 某一个能够由其余两个表示，则就还有。用德摩根律可以做到这 一点。 使用等式 可以消去所有布尔和，这意味着. , - 是函数完全的。 类似地，使用等式 可以消去所有布尔积，因此 +，-是函数完全的。 注意：+，. 不是函数完全的，因为用这两个运算不可能表示 布尔函数 。 我们已经找到了一些含有两个运算的函数完全集合，还能 不能找到只含一个运算集合的函数完全集合呢？ 这个集合是存在的。定义运算“|”或 “NAND” 如下：1|1=0 且 1|0=0|1=0|0=1。定义运算“ ” 或“ NOR”如下： 且 集合 | 和 都是函数完全的 。因为. ,-是函数完全的，故要说明|是函数完全的，只要 证 明两个运算. 和-都可以由运算|表示，这由下面两式完成： 求布尔变元x 、y、z或其补的布尔积，使得它具有值 为1当且仅当 【练习】 Solution： a） b） c） d） 2.求下列布尔函数的积之和展开式。 Solution： a）我们可以得到 简化本式得到F(x,y)为 b）该题目中布尔函数的形式已经是积之和展开式。 c）化简得到该题中布尔函数的积之和展开式形式为 d）该题得到 3. 求布尔函数F(x,y,z)的积之和展开式，F(x,y,z)等于1 当且仅当 Solution： a） b） c） d） 4.用运算.和-表示下列布