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

,DSPST,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,DSPST,research,宁波大学数字技术与软件应用研究所,*,*,DSPST,DSPST,research,宁波大学数字技术与软件应用研究所,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,Click to edit Master title style,Click to edit Master text stylesgood1,Second levelgood2,Third levelgood3,Fourth levelgood4,Fifth levelgood5,*,*,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,则,B,n,=(x,1,x,2,x,n,) | x,i,B, 1in ,是由,0,和,1,所能构成的所有,n,元有序列的集合。变元,x,如果仅从,B,中取值，则,称该变元为,布尔变元,，即它的值只可能为,0,或,1.,从,B,n,到,B,的函数,称为,n,度布尔函数。,2.,布尔表达式和布尔函数,【example 2】,从布尔变元有序对之取值集合到集合,0,，,1,的函数 就是一个,2,度布尔函数，且,F,的值如下表所示。,布尔函数也可用由变元和布尔运算构成的表达式来表示。关,于变元,x,1,x,2,x,n,的布尔表达式递归定义如下：,1,）,0,，,1,，,x,1,，,x,2,，,，,x,n,是布尔表达式；,2,）如果,E1,和,E2,是布尔表达式，则,也是布尔表达式。,每个布尔表达式都表示一个布尔函数，此函数的值是通过在,表达式中用,0,和,1,替换变元得到的。,【example 3】,求由 表示的布尔函数的值。,Solution,：,这个函数的值由下表所示。,布尔函数还可以用图形来表示，方法是,:,将,n,元二进制数组与,n,方体的顶点一一对应，再标出那些函数值为的顶点。,【example 4】,例,3,中从,B,3,到,B,的函数,可如下表示：标出满足 的五个,3,元组,所对应的顶点。如下图所示，这些顶点用实心的黑圈标出。,n,个变元的布尔函数,F,和,G,是相等的，当且仅当,F( b,1,b,2,b,n,)=G( b,1,b,2,.b,n,),其中,b,1,b,2,b,n,属于,B.,表示,同一个函数的不同的布尔表达式称为是,等价的,。,例如，布尔表达式 都是等价的。布尔函,数,F,的,补函数,是 此处,设,F,和,G,是,n,度的布尔函数，函数的,布尔和,F+G,与,布尔积,FG,分,别为,2,度布尔函数是从一个,4,个元素的集合到,B,的函数，这,4,个元素,是,B=0,1,中元素构成的元素对，,B,是有,2,个元素的集合，因而有,16,个不同的,2,度布尔函数。在下表中我们列出了这,16,个,2,度布尔,函数的值，这,16,个不同的,2,度布尔函数被记为,F,1, F,2, , F,16,.,【example 5】,有多少个不同的,n,度布尔函数？,Solution,：,由计数的乘积规则知：有,2n,个由,0,和,1,构成的不同的,n,元组。,因为布尔函数就是对这,2,n,个,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,）,x,y,z,1,1,1,0,0,1,1,0,0,0,1,0,1,0,0,1,0,0,0,0,0,1,1,1,1,0,1,0,1,1,0,0,1,1,0,0,0,0,1,0,b),x,y,z,yz,x+yz,1,1,1,1,1,1,1,0,0,1,1,0,1,0,1,1,0,0,0,1,0,1,1,1,1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,c),x,y,z,+,1,1,1,0,0,1,0,0,1,1,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,0,0,1,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,1,0,0,1,1,d,）,x,y,z,yz,1,1,1,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,1,1,0,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,： 布尔变元或其补称为,文字,。布尔变元,x,1,x,2,x,n,的,小项,是一个布尔积,y,1,y,2,y,n,其中 或 。因此小项是,n,个文字的积，每个文字对应于一个变元。,注：,一个小项对一个且只对一个变元值的组合取值,1,，更确切地,，小项,y,1,y,2,y,n,为,1,当其仅当每个,y,i,为,1,，当且仅当 时,x,i,为,1,， 时,x,i,为,0.,通过取不同小项的布尔和，就能构造布尔表达式，使其具有给定的,值集合。,特别地，小项的布尔和具有值,1,仅当和中的某个小项具有值,1,时才成立；,对于变元值的其他组合，它具有值,0.,因此，给定一个布尔函数，可以构造小,项的布尔和使得：当此布尔函数具有值,1,时它的值为,1,，当次布尔函数具有值,0,时它的值为,0.,此布尔和中的小项与使得此函数值为,1,的值的组合相对应。表示,布尔函数的小项的和称为此函数的,积之和展开式,或,析取范式,。,【example 2】,求一个小项使得：当,x,1,=x,3,=0,且,x,2,=x,4,=x,5,=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,）中方法类似可以得到,本节内容到此结束,谢谢大家！,