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

《离散数学课件-第1章-8(上).ppt》由会员分享，可在线阅读，更多相关《离散数学课件-第1章-8(上).ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1离散数学Discrete Mathematics 第一章第一章 逻辑与证明逻辑与证明&学习内容学习内容1.1 1.1 逻辑逻辑逻辑逻辑1.2 1.2 命题等价命题等价命题等价命题等价1.3 1.3 谓词和量词谓词和量词谓词和量词谓词和量词 1.4 1.4 对偶与范式对偶与范式对偶与范式对偶与范式1.5 1.5 推理规则推理规则推理规则推理规则1.6 1.6 证明导论证明导论证明导论证明导论1.7 1.7 证明的方法和策略证明的方法和策略证明的方法和策略证明的方法和策略1.8 1.8 数理逻辑的应用数理逻辑的应用数理逻辑的应用数理逻辑的应用&布布尔函数及其表示函数及其表示引入引入 计算机和其他

2、电子设备中的电路都有输入和输出，输入是计算机和其他电子设备中的电路都有输入和输出，输入是0或或1，输，输出也是出也是0或或1.电路可以用任何具有两个不同状态的基本元件来构造，开电路可以用任何具有两个不同状态的基本元件来构造，开关和光学装置都是这样的元件。关和光学装置都是这样的元件。1854年，乔治年，乔治.布尔第一次给出逻辑的基本规则。布尔第一次给出逻辑的基本规则。1938年，克劳德年，克劳德.香农揭示了怎么用逻辑的基本规则来设计电路，这些基本规则形成了香农揭示了怎么用逻辑的基本规则来设计电路，这些基本规则形成了布尔代数的基础。布尔代数的基础。在本章中我们对布尔代数的基本性质进行了讨论，并利用

3、布尔代在本章中我们对布尔代数的基本性质进行了讨论，并利用布尔代数的基本元素构造的表达式来表示布尔函数，以及介绍一个能产生这数的基本元素构造的表达式来表示布尔函数，以及介绍一个能产生这些表达式的算法。些表达式的算法。1.引言引言 布尔代数提供的是集合布尔代数提供的是集合0，1上的运算和规则，这个集合上的运算和规则，这个集合及布尔代数的规则还可以用来研究电子和光学开关。及布尔代数的规则还可以用来研究电子和光学开关。我们用的最多的三个布尔代数运算是我们用的最多的三个布尔代数运算是补、布尔和补、布尔和与与布尔积。布尔积。下面具体介绍一下这三种运算。下面具体介绍一下这三种运算。1）元素的补元素的补 用上

4、划线加以标记，其定义为：用上划线加以标记，其定义为：和和2.布尔和记为布尔和记为+或或OROR，它的值如下：，它的值如下：3.布尔积记为布尔积记为 或或AND AND ，它的值如下：，它的值如下：注意：注意：为了避免混淆可以删去为了避免混淆可以删去“”。就像在写代数积时一样。就像在写代数积时一样。除非使用括号布尔运算的优先级规则是：首先计算所有补，除非使用括号布尔运算的优先级规则是：首先计算所有补，然后是布尔积，然后是布尔和。然后是布尔积，然后是布尔和。【example 1】计算计算 的值。的值。Solution：根据补、布尔积与布尔和的定义得根据补、布尔积与布尔和的定义得注：注：补、布尔积和

5、布尔和分别对应于逻辑运算补、布尔积和布尔和分别对应于逻辑运算、和和，且，且0 0对应于对应于F(F(假假)，1 1对应于对应于T(T(真真)。关于布尔代数的结果可以直接翻译。关于布尔代数的结果可以直接翻译成关于命题的结果。相反地，关于命题的结果也能翻译成关于布成关于命题的结果。相反地，关于命题的结果也能翻译成关于布尔代数的命题。尔代数的命题。布尔函数定义：布尔函数定义：设设B=0,1,则则Bn=(x1,x2,xn)|xi B,1in 是由是由0和和1所能构成的所有所能构成的所有n元有序列的集合。变元元有序列的集合。变元x如果仅从如果仅从B中取值，则中取值，则称该变元为称该变元为布尔变元布尔变元

6、，即它的值只可能为，即它的值只可能为0或或1.从从Bn到到B的函数的函数称为称为n n度布尔函数。度布尔函数。【example 2】从布尔变元有序对之取值集合到集合从布尔变元有序对之取值集合到集合0，1的函数的函数 就是一个就是一个2度布尔函数，且度布尔函数，且F的值如下表所示。的值如下表所示。布尔函数也可用由变元和布尔运算构成的表达式来表示。关布尔函数也可用由变元和布尔运算构成的表达式来表示。关于变元于变元x1,x2,xn的布尔表达式递归定义如下：的布尔表达式递归定义如下：1）0，1，x1，x2，xn是布尔表达式；是布尔表达式；2）如果）如果E1和和E2是布尔表达式，则是布尔表达式，则也是布

7、尔表达式。也是布尔表达式。每个布尔表达式都表示一个布尔函数，此函数的值是通过在每个布尔表达式都表示一个布尔函数，此函数的值是通过在表达式中用表达式中用0和和1替换变元得到的。替换变元得到的。【example 3】求由求由 表示的布尔函数的值。表示的布尔函数的值。Solution：这个函数的值由下表所示。这个函数的值由下表所示。布尔函数还可以用图形来表示，方法是布尔函数还可以用图形来表示，方法是:将将n元二进制数组与元二进制数组与n方体的顶点一一对应，再标出那些函数值为的顶点。方体的顶点一一对应，再标出那些函数值为的顶点。【example 4】例例3中从中从B3到到B的函数的函数可如下表示：标出

8、满足可如下表示：标出满足 的五个的五个3元组元组 所对应的顶点。如下图所对应的顶点。如下图所示，这些顶点用实心的黑圈标出。所示，这些顶点用实心的黑圈标出。n个变元的布尔函数个变元的布尔函数F和和G是相等的，当且仅当是相等的，当且仅当F(b1,b2,bn)=G(b1,b2,.bn),其中其中b1,b2,bn 属于属于B.表示表示同一个函数的不同的布尔表达式称为是同一个函数的不同的布尔表达式称为是等价的等价的。例如，布尔表达式例如，布尔表达式 都是等价的。布尔函都是等价的。布尔函数数F的的补函数补函数是是 此处此处 设设F和和G是是n度的布尔函数，函数的度的布尔函数，函数的布尔和布尔和F+G与与布

9、尔积布尔积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

10、构成的不同的构成的不同的n元组。元组。因为布尔函数就是对这因为布尔函数就是对这2n个个n元组中的每一个进行赋值，故乘元组中的每一个进行赋值，故乘积规则表明有积规则表明有 个不同的个不同的n度布尔函数。度布尔函数。下表列出了下表列出了16度不同布尔函数的个数。度不同布尔函数的个数。3.布尔代数恒等式布尔代数恒等式布尔代数有许多恒等式，下表中列出了其中最重要的恒等式布尔代数有许多恒等式，下表中列出了其中最重要的恒等式。这些恒等式对于电路设计的简化特别有用，下表中的每一个恒。这些恒等式对于电路设计的简化特别有用，下表中的每一个恒等式都可以用表来证明。等式都可以用表来证明。【example 6】证明分

11、配律证明分配律 是正确。是正确。下表表示此恒等式的验证。这个恒等式成立是因为此表的最下表表示此恒等式的验证。这个恒等式成立是因为此表的最后两列相同。后两列相同。布尔代数恒等式也可以被用来进一步证明其他的恒等式。布尔代数恒等式也可以被用来进一步证明其他的恒等式。【example 7】用表用表5所示的布尔代数的其他恒等式证明所示的布尔代数的其他恒等式证明吸收律吸收律（称为吸收律是因为将（称为吸收律是因为将x+y吸收进吸收进x而保持而保持x不变。）不变。）Solution:推导此恒等式的步骤及没不使用的定律如下：推导此恒等式的步骤及没不使用的定律如下：布尔和的同一律布尔和的同一律 布尔和对布尔积的分

12、配律布尔和对布尔积的分配律 布尔积的交换律布尔积的交换律 布尔积的支配律布尔积的支配律 布尔和的同一律布尔和的同一律4.对偶性对偶性表表5中的恒等式都是成对出现的（除了双重补律、单位元性质中的恒等式都是成对出现的（除了双重补律、单位元性质及零元性质），为解释每一对恒等式中的两个式子的关系，我们及零元性质），为解释每一对恒等式中的两个式子的关系，我们使用使用“对偶对偶”这个概念。这个概念。一个布尔表达式的对偶可如下得到一个布尔表达式的对偶可如下得到：交换布尔和与布尔积，且交换交换布尔和与布尔积，且交换0 0与与1.1.【example 8】写出写出 和和 的对偶。的对偶。Solution：在这两

13、个表达式中交换符号在这两个表达式中交换符号+和和 、0和和1就产生它们的对偶就产生它们的对偶，这两个对偶分别是，这两个对偶分别是 和和 对偶性原理对偶性原理 布尔表达式所表示的布尔函数布尔表达式所表示的布尔函数F的那个特定的布尔表达式。对的那个特定的布尔表达式。对于由布尔表达式表示的函数的恒等式，当取恒等式两边的函数的于由布尔表达式表示的函数的恒等式，当取恒等式两边的函数的对偶时，等式仍然成立，此结果叫做对偶时，等式仍然成立，此结果叫做对偶原理对偶原理。它对于获得新的恒等式十分有用。它对于获得新的恒等式十分有用。【example 9】通过取对偶的方法，由吸收律通过取对偶的方法，由吸收律 构造一

14、个恒等式。构造一个恒等式。Solution：取此恒等式两边的对偶，得到恒等式取此恒等式两边的对偶，得到恒等式它也被称为吸收律，见表它也被称为吸收律，见表5.5.布尔代数的抽象定义布尔代数的抽象定义所有关于布尔函数和表达式的结论都可以翻译成成关于命所有关于布尔函数和表达式的结论都可以翻译成成关于命题的结论，也可以翻译成关于集合的结论。因此，抽象地题的结论，也可以翻译成关于集合的结论。因此，抽象地定义布尔代数十分有用。定义布尔代数十分有用。当一个特定的结构被证明是布尔代数，则所有关于布尔代当一个特定的结构被证明是布尔代数，则所有关于布尔代数的一般结果都可应用于这个特定的结构。数的一般结果都可应用于

15、这个特定的结构。对布尔代数的定义最常用的方法是指明运算所必须满足的对布尔代数的定义最常用的方法是指明运算所必须满足的性质，如以下定义所示。性质，如以下定义所示。定义定义1：一个：一个布尔代数布尔代数是一个集合是一个集合B，他有两个二元运算，他有两个二元运算和和，元素，元素0和和1，以及一个一元运算，以及一个一元运算，且对，且对B中的所有元素中的所有元素x、y和和z，下列性质成立：，下列性质成立：注：注：使用定义使用定义1所给的定律可以证明许多其他的定律，例如幂等律所给的定律可以证明许多其他的定律，例如幂等律、支配律等。、支配律等。以前讨论过，以前讨论过，B=0,1连同连同OR、AND运算及运算

16、及“非非”算子也满算子也满足足布尔代数的所有性质。类似地，一个全集布尔代数的所有性质。类似地，一个全集U的所有子集构成的集的所有子集构成的集合，连同并和交运算、空集和全集及集合的其余算子是一个布尔合，连同并和交运算、空集和全集及集合的其余算子是一个布尔代数。所以为了建立关于布尔表达式、命题和集合的结果，我们代数。所以为了建立关于布尔表达式、命题和集合的结果，我们只要证明关于抽象布尔代数的结果即可。只要证明关于抽象布尔代数的结果即可。布尔代数也可以用格的概念来定义。布尔代数也可以用格的概念来定义。一个格一个格L式一个偏序集，其没对元素式一个偏序集，其没对元素x、y都有一个最小上都有一个最小上界，

17、记为界，记为lub(x,y),也有一个最大下界，记为也有一个最大下界，记为glb(x,y)给定给定L的两个元素的两个元素x和和y，我们可以定义，我们可以定义L的两个运算的两个运算和和如下：如下：x y=lub(x,y)x y=glb(x,y)要使一个格称为定义要使一个格称为定义1所指的一个布尔代数，他必须还有两所指的一个布尔代数，他必须还有两个性质。个性质。一、它必须是一、它必须是可补可补的。为使一个格称为可补的，它必须有一个的。为使一个格称为可补的，它必须有一个 最小元最小元0和一个最大元和一个最大元1，且对格的每个元素，且对格的每个元素x，必须存在一，必须存在一 个元素个元素 使得使得 且

18、且 。二、它必须是二、它必须是分配分配的。所谓的。所谓“分配的分配的”是指：是指：对于对于L中的每个中的每个x、y和和z都有都有 且且【练习练习】1.求下列表达式的值。求下列表达式的值。2.求满足下列方程的布尔变元求满足下列方程的布尔变元x的值。的值。Solution：1.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.用

19、表来表示下列每个布尔函数的值。用表来表示下列每个布尔函数的值。Solution：a）xyz1110011000101001000001111010110011000010 b)xyzyzx+yz1111111001101011000101111010000010000000 c)xyz +1110010011000011101110111001101101100011010000110011001100010011d）xyzyz1110010101100100001011000001001101110110010100100100000011000000001101104.求下列布尔表达式的对

20、偶。求下列布尔表达式的对偶。Solution a）xy b）c）d）二、布尔函数的表示二、布尔函数的表示本节将研究布尔代数的两个重要问题。本节将研究布尔代数的两个重要问题。第一：给定一个布尔函数，怎样才能找到表示这个布尔函数的第一：给定一个布尔函数，怎样才能找到表示这个布尔函数的 布尔表达式？布尔表达式？这个问题将通过证明如下结论来解决：任何一个布尔函数都可由这个问题将通过证明如下结论来解决：任何一个布尔函数都可由变元及其补的布尔积的布尔和表示。这个问题的答案还说明了任意变元及其补的布尔积的布尔和表示。这个问题的答案还说明了任意布尔函数都可用三个布尔算子（布尔函数都可用三个布尔算子（.,+,+

21、和和-）表示。）表示。第二：有没有一个更小的算子集合可以用来表示所有的布尔函第二：有没有一个更小的算子集合可以用来表示所有的布尔函 数？数？我们将通过证明下列结论来解决这个问题：所有的布尔函我们将通过证明下列结论来解决这个问题：所有的布尔函数都可仅用一个算子来表示。数都可仅用一个算子来表示。这两个问题在电路设计中都有特殊的重要性。这两个问题在电路设计中都有特殊的重要性。【example 1】函数函数F(x,y,z)和和G(x,y,z)如下表所示，求表示这两如下表所示，求表示这两个函数的布尔表达式。个函数的布尔表达式。Solution：我们需要这样一个表达式来表示我们需要这样一个表达式来表示F:

22、当当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当且仅当当

23、且仅当x=z=0且且y=1.这两个布尔积的布尔和这两个布尔积的布尔和 就表示就表示G,因为它具有值因为它具有值1当当且仅当且仅当x=y=1且且z=0，或，或x=z=0且且y=1。例例1说明了一个过程，用这个过程可以构造布尔表达式来表示说明了一个过程，用这个过程可以构造布尔表达式来表示具有给定值的函数。如果变元值的一个组合使得函数值为具有给定值的函数。如果变元值的一个组合使得函数值为1，则此组合确定了变元或其补的一个布尔积。则此组合确定了变元或其补的一个布尔积。定义定义1：布尔变元或其补称为布尔变元或其补称为文字文字。布尔变元。布尔变元x1,x2,xn的的小项小项是一个布尔积是一个布尔积y1y2

24、yn,其中其中 或或 。因此小项是。因此小项是n个文字的积，每个文字对应于一个变元。个文字的积，每个文字对应于一个变元。注：注：一个小项对一个且只对一个变元值的组合取值一个小项对一个且只对一个变元值的组合取值1，更确切地，更确切地，小项，小项y1y2yn为为1当其仅当每个当其仅当每个yi为为1，当且仅当，当且仅当 时时xi为为1，时时xi为为0.通过取不同小项的布尔和，就能构造布尔表达式，使其具有给定的通过取不同小项的布尔和，就能构造布尔表达式，使其具有给定的值集合。值集合。特别地，小项的布尔和具有值特别地，小项的布尔和具有值1仅当和中的某个小项具有值仅当和中的某个小项具有值1时才成立；时才成

25、立；对于变元值的其他组合，它具有值对于变元值的其他组合，它具有值0.因此，给定一个布尔函数，可以构造小因此，给定一个布尔函数，可以构造小项的布尔和使得：当此布尔函数具有值项的布尔和使得：当此布尔函数具有值1时它的值为时它的值为1，当次布尔函数具有值，当次布尔函数具有值0时它的值为时它的值为0.此布尔和中的小项与使得此函数值为此布尔和中的小项与使得此函数值为1的值的组合相对应。表示的值的组合相对应。表示布尔函数的小项的和称为此函数的布尔函数的小项的和称为此函数的积之和展开式积之和展开式或或析取范式析取范式。【example 3】求函数求函数 的积之和展开式。的积之和展开式。Solution：下面

26、用两种方法求下面用两种方法求 的积之和展开式。的积之和展开式。第一种方法就是用布尔恒等式将这个积展开然后化简。过程如下：第一种方法就是用布尔恒等式将这个积展开然后化简。过程如下：构造积之和展开式的第二种方法是：构造积之和展开式的第二种方法是：对对x、y和和z所有可能的取值都计算出所有可能的取值都计算出F的值，这些值见下表。的值，这些值见下表。也可以通过取布尔和的布尔积来求一个布尔表达式，使其表也可以通过取布尔和的布尔积来求一个布尔表达式，使其表示一个布尔函数，所得到的展开式称为这个函数的示一个布尔函数，所得到的展开式称为这个函数的合取范式合取范式或或和之积展开式和之积展开式，这个展开式可以通过

27、求积之和展开式的对，这个展开式可以通过求积之和展开式的对偶而得到。偶而得到。2.函数完全性函数完全性每个布尔函数都可以表示为小项的布尔和。每个小项都是布每个布尔函数都可以表示为小项的布尔和。每个小项都是布尔变元或其补的布尔积。尔变元或其补的布尔积。这说明了每个布尔函数都可以用布尔运算这说明了每个布尔函数都可以用布尔运算.、+和和-来表示。因来表示。因为每个布尔函数都可以由布尔运算表示，我们称集合为每个布尔函数都可以由布尔运算表示，我们称集合 是是 函数完全的函数完全的。还有没有更小的函数完全运算集合呢？如果这三个运算中的还有没有更小的函数完全运算集合呢？如果这三个运算中的某一个能够由其余两个表

28、示，则就还有。用德摩根律可以做到这某一个能够由其余两个表示，则就还有。用德摩根律可以做到这一点。一点。使用等式使用等式 可以消去所有布尔和，这意味着可以消去所有布尔和，这意味着.,-是函数完全的。是函数完全的。类似地，使用等式类似地，使用等式 可以消去所有布尔积，因此可以消去所有布尔积，因此+，-是函数完全的。是函数完全的。注意：注意：+，.不是函数完全的，因为用这两个运算不可能表示不是函数完全的，因为用这两个运算不可能表示 布尔函数布尔函数 。我们已经找到了一些含有两个运算的函数完全集合，还能我们已经找到了一些含有两个运算的函数完全集合，还能不能找到只含一个运算集合的函数完全集合呢？不能找到

29、只含一个运算集合的函数完全集合呢？这个集合是存在的。定义运算这个集合是存在的。定义运算“|”或或“NAND”如下：如下：1|1=0 且且 1|0=0|1=0|0=1。定义运算。定义运算“”或或“NOR”如下：如下：且且 集合集合|和和 都是函数完全的都是函数完全的。因为。因为.,-是函数完全的，故要说明是函数完全的，故要说明|是函数完全的，只要证是函数完全的，只要证明两个运算明两个运算.和和-都可以由运算都可以由运算|表示，这由下面两式完成：表示，这由下面两式完成：1.求布尔变元求布尔变元x、y、z或其补的布尔积，使得它具有值或其补的布尔积，使得它具有值 为为1当且仅当当且仅当【练习练习】So

30、lution：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）中方法类似可以得到）中方法类似可以得到本节内容到此结束本节内容到此结束