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

1,离散数学Discrete Mathematics,汪荣贵 教授合肥工业大学软件学院专用课件2010.05,第一章 逻辑与证明,学习内容,1.1 逻辑1.2 命题等价1.3 谓词和量词 1.4 对偶与范式1.5 推理规则1.6 证明导论1.7 证明的方法和策略1.8 数理逻辑的应用,布尔函数及其表示,引入 计算机和其他电子设备中的电路都有输入和输出，输入是0或1，输出也是0或1.电路可以用任何具有两个不同状态的基本元件来构造，开关和光学装置都是这样的元件。1854年，乔治.布尔第一次给出逻辑的基本规则。1938年，克劳德.香农揭示了怎么用逻辑的基本规则来设计电路，这些基本规则形成了布尔代数的基础。在本章中我们对布尔代数的基本性质进行了讨论，并利用布尔代数的基本元素构造的表达式来表示布尔函数，以及介绍一个能产生这些表达式的算法。,1.引言 布尔代数提供的是集合0，1上的运算和规则，这个集合及布尔代数的规则还可以用来研究电子和光学开关。我们用的最多的三个布尔代数运算是补、布尔和与布尔积。下面具体介绍一下这三种运算。1）元素的补 用上划线加以标记，其定义为：和,一、布尔函数,2.布尔和记为+或OR，它的值如下：3.布尔积记为 或AND，它的值如下：注意：为了避免混淆可以删去“”。就像在写代数积时一样。除非使用括号布尔运算的优先级规则是：首先计算所有补，然后是布尔积，然后是布尔和。,【example 1】计算 的值。Solution：根据补、布尔积与布尔和的定义得注：补、布尔积和布尔和分别对应于逻辑运算、和，且0对应于F(假)，1对应于T(真)。关于布尔代数的结果可以直接翻译成关于命题的结果。相反地，关于命题的结果也能翻译成关于布尔代数的命题。,布尔函数定义：设B=0,1,则Bn=(x1,x2,xn)|xi B,1in 是由0和1所能构成的所有n元有序列的集合。变元x如果仅从B中取值，则称该变元为布尔变元，即它的值只可能为0或1.从Bn到B的函数称为n度布尔函数。,2.布尔表达式和布尔函数,【example 2】从布尔变元有序对之取值集合到集合0，1的函数 就是一个2度布尔函数，且F的值如下表所示。,布尔函数也可用由变元和布尔运算构成的表达式来表示。关于变元x1,x2,xn的布尔表达式递归定义如下：1）0，1，x1，x2，xn是布尔表达式；2）如果E1和E2是布尔表达式，则也是布尔表达式。每个布尔表达式都表示一个布尔函数，此函数的值是通过在表达式中用0和1替换变元得到的。,【example 3】求由 表示的布尔函数的值。Solution：这个函数的值由下表所示。,布尔函数还可以用图形来表示，方法是:将n元二进制数组与n方体的顶点一一对应，再标出那些函数值为的顶点。【example 4】例3中从B3到B的函数可如下表示：标出满足 的五个3元组 所对应的顶点。如下图所示，这些顶点用实心的黑圈标出。,n个变元的布尔函数F和G是相等的，当且仅当F(b1,b2,bn)=G(b1,b2,.bn),其中b1,b2,bn 属于B.表示同一个函数的不同的布尔表达式称为是等价的。例如，布尔表达式 都是等价的。布尔函数F的补函数是 此处 设F和G是n度的布尔函数，函数的布尔和F+G与布尔积FG分别为,2度布尔函数是从一个4个元素的集合到B的函数，这4个元素是B=0,1中元素构成的元素对，B是有2个元素的集合，因而有16个不同的2度布尔函数。在下表中我们列出了这16个2度布尔函数的值，这16个不同的2度布尔函数被记为F1,F2,F16.,【example 5】有多少个不同的n度布尔函数？Solution：由计数的乘积规则知：有2n个由0和1构成的不同的n元组。因为布尔函数就是对这2n个n元组中的每一个进行赋值，故乘积规则表明有 个不同的n度布尔函数。下表列出了16度不同布尔函数的个数。,3.布尔代数恒等式布尔代数有许多恒等式，下表中列出了其中最重要的恒等式。这些恒等式对于电路设计的简化特别有用，下表中的每一个恒等式都可以用表来证明。,【example 6】证明分配律 是正确。下表表示此恒等式的验证。这个恒等式成立是因为此表的最后两列相同。,布尔代数恒等式也可以被用来进一步证明其他的恒等式。【example 7】用表5所示的布尔代数的其他恒等式证明吸收律（称为吸收律是因为将x+y吸收进x而保持x不变。）Solution:推导此恒等式的步骤及没不使用的定律如下：布尔和的同一律 布尔和对布尔积的分配律 布尔积的交换律 布尔积的支配律 布尔和的同一律,4.对偶性表5中的恒等式都是成对出现的（除了双重补律、单位元性质及零元性质），为解释每一对恒等式中的两个式子的关系，我们使用“对偶”这个概念。一个布尔表达式的对偶可如下得到：交换布尔和与布尔积，且交换0与1.,【example 8】写出 和 的对偶。Solution：在这两个表达式中交换符号+和、0和1就产生它们的对偶，这两个对偶分别是 和,对偶性原理 布尔表达式所表示的布尔函数F的那个特定的布尔表达式。对于由布尔表达式表示的函数的恒等式，当取恒等式两边的函数的对偶时，等式仍然成立，此结果叫做对偶原理。它对于获得新的恒等式十分有用。,【example 9】通过取对偶的方法，由吸收律 构造一个恒等式。Solution：取此恒等式两边的对偶，得到恒等式它也被称为吸收律，见表5.,5.布尔代数的抽象定义所有关于布尔函数和表达式的结论都可以翻译成成关于命题的结论，也可以翻译成关于集合的结论。因此，抽象地定义布尔代数十分有用。当一个特定的结构被证明是布尔代数，则所有关于布尔代数的一般结果都可应用于这个特定的结构。对布尔代数的定义最常用的方法是指明运算所必须满足的性质，如以下定义所示。,定义1：一个布尔代数是一个集合B，他有两个二元运算和，元素0和1，以及一个一元运算，且对B中的所有元素x、y和z，下列性质成立：,注：使用定义1所给的定律可以证明许多其他的定律，例如幂等律、支配律等。以前讨论过，B=0,1连同OR、AND运算及“非”算子也满足布尔代数的所有性质。类似地，一个全集U的所有子集构成的集合，连同并和交运算、空集和全集及集合的其余算子是一个布尔代数。所以为了建立关于布尔表达式、命题和集合的结果，我们只要证明关于抽象布尔代数的结果即可。,布尔代数也可以用格的概念来定义。一个格L式一个偏序集，其没对元素x、y都有一个最小上界，记为lub(x,y),也有一个最大下界，记为glb(x,y)给定L的两个元素x和y，我们可以定义L的两个运算和如下：x y=lub(x,y)x y=glb(x,y),要使一个格称为定义1所指的一个布尔代数，他必须还有两个性质。一、它必须是可补的。为使一个格称为可补的，它必须有一个 最小元0和一个最大元1，且对格的每个元素x，必须存在一 个元素 使得 且。二、它必须是分配的。所谓“分配的”是指：对于L中的每个x、y和z都有 且,【练习】,求下列表达式的值。求满足下列方程的布尔变元x的值。,Solution：a）=1.1=1 b）=1+0=1 c）=1.0=0 d）=0,Solution：a）因为1.x=x，所以解是x=0.b）因为0+0=0，1+1=1，解为x=0 c）因为1.x=x，对于x=0，x=1都成立，所以0和1都是该题的解 d）本题无解。,3.用表来表示下列每个布尔函数的值。,Solution：a）,b),c),d）,4.求下列布尔表达式的对偶。,Solution a）xy b）c）d）,二、布尔函数的表示本节将研究布尔代数的两个重要问题。第一：给定一个布尔函数，怎样才能找到表示这个布尔函数的 布尔表达式？这个问题将通过证明如下结论来解决：任何一个布尔函数都可由变元及其补的布尔积的布尔和表示。这个问题的答案还说明了任意布尔函数都可用三个布尔算子（.,+和-）表示。第二：有没有一个更小的算子集合可以用来表示所有的布尔函 数？我们将通过证明下列结论来解决这个问题：所有的布尔函数都可仅用一个算子来表示。这两个问题在电路设计中都有特殊的重要性。,【example 1】函数F(x,y,z)和G(x,y,z)如下表所示，求表示这两个函数的布尔表达式。,1.积之和展开式,下面用例子来说明寻找布尔函数的布尔表达式的一个重要方法。,Solution：我们需要这样一个表达式来表示F:当x=z=1且y=0时它的值为1，否则它的值为0.此表达式可取为x,和z的布尔积，这个积 具有值1当且仅当x=z=1,即当且仅当x=z=1且y=0。为表示G，我们需要一个表达式满足：当x=y=1且z=0时，或当x=y=0且z=1时它的值为1。这样的表达式可以取为两个不同的布尔积的布尔和。布尔积 具有值1当且仅当 x=y=1且z=0;类似地，布尔积 具有值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.用运算.和-表示下列布尔函数,Solution：我们使用德摩根定律将s+t替换为 进行简化得到 a）b）c）该题直接使用德摩根定律化简得到 d）与（a）中方法类似可以得到,本节内容到此结束,谢谢大家！,