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

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 数理逻辑的应用数理逻辑的应用数理逻辑的应用数理逻辑的应用&逻辑电路及其极小化路及其极小化一、逻辑门电路一、逻辑门电路 1.引入引入布尔代数被用来作为电子装置的电路模型。布尔代数被用来作为电子装置的电路模型。这种电子装置的输入和输出都可以认为是集合这种电子装置的输入和输出都可以认为是集合00，1 1中的元素。构中的元素。构成计算机或其他电子装置的电路时根据前两节我们所学习的布尔代成计算机或其他电子装置的电路时根据前两节我们所学习的布尔代数的各种规则来设计的。数的各种规则来设计的。电路的基本原件是所谓的电路的基本原件是所谓的门门，每种类型的门实现一种布尔运算。本，每种类型的门实现一种布尔运算。本节定义了几种类型的门。节定义了几种类型的门。在本章所讨论的电路中，输出都只与输入有关，而与电路的当前在本章所讨论的电路中，输出都只与输入有关，而与电路的当前状态无关，换句话说，这些电路都没有存储能力，这样的电路叫做状态无关，换句话说，这些电路都没有存储能力，这样的电路叫做组合电路组合电路或或选通网络选通网络我们将使用三种元件来构造组合电路。我们将使用三种元件来构造组合电路。三种元件分别是：三种元件分别是：相反器、或门、与门相反器、或门、与门。下面对这三中元。下面对这三中元件分别进行介绍。件分别进行介绍。1）反相器）反相器 它以布尔值作为输入，并产生此布尔值的补作为输出，用它以布尔值作为输入，并产生此布尔值的补作为输出，用符号表示如下：符号表示如下：在图中进入元件的输入画在左边，离开原件的输出画在右边在图中进入元件的输入画在左边，离开原件的输出画在右边2）或门）或门 其输入时两个或两个以上的布尔值，输出时这些值的布尔和。其输入时两个或两个以上的布尔值，输出时这些值的布尔和。用符号表示如下：用符号表示如下：在图中进入元件的输入画在左边，离开原件的输出画在右边在图中进入元件的输入画在左边，离开原件的输出画在右边3）与门）与门 其输入时两个或两个以上的布尔值，输出是这些值的布尔积。其输入时两个或两个以上的布尔值，输出是这些值的布尔积。用符号表示为：用符号表示为：在图中进入元件的输入画在左边，离开原件的输出画在右边在图中进入元件的输入画在左边，离开原件的输出画在右边注：注：与门和或门允许有多个输入，进入元件的输入都画在左边与门和或门允许有多个输入，进入元件的输入都画在左边，离开原件的输出都画在右边，具有，离开原件的输出都画在右边，具有n个输入的与门和或门如个输入的与门和或门如下图所示。下图所示。2.门的组合门的组合使用相反器、或门和与门的组合可以构造组合电路。使用相反器、或门和与门的组合可以构造组合电路。在构造电路的组合时，某些门可能有公共的输入。在构造电路的组合时，某些门可能有公共的输入。有两种方法可以描述公共输入有两种方法可以描述公共输入 一种方法是：对每个输入，将使用这个输入的门画在一个分支一种方法是：对每个输入，将使用这个输入的门画在一个分支 上。上。另一种方法是：对每个门，分别指出其输入。另一种方法是：对每个门，分别指出其输入。下图说明了这两种方法，其中的门有同样的输入值。下图说明了这两种方法，其中的门有同样的输入值。注意：注意：一个一个门的的输出可能被作出可能被作为另一个元件或更多元件的另一个元件或更多元件的输入。入。【example 1】构造产生下列输出的电路：构造产生下列输出的电路：Solution：产生这些输出的电路如图示。产生这些输出的电路如图示。3.电路的例子电路的例子【example 2】某个组织的一切事物都由一个三人委员会决定某个组织的一切事物都由一个三人委员会决定，每个委员对提出的建议可以投赞成票或反对票。一个建议如果，每个委员对提出的建议可以投赞成票或反对票。一个建议如果得到了至少两张赞成票就获得通过。设计一个电路，来判断建议得到了至少两张赞成票就获得通过。设计一个电路，来判断建议是否获得通过。是否获得通过。Solution：如果第一个委员投赞成票，则令如果第一个委员投赞成票，则令x=1;如果这个委员投反对如果这个委员投反对票，则令票，则令x=0。如果第二个委员投赞成票，则令。如果第二个委员投赞成票，则令y=1;若其投反若其投反对票，则令对票，则令y=0。同样道理，第三个委员投赞成票。同样道理，第三个委员投赞成票 则令则令z=1,反反之，之，z=0。必须设计一个电路使得对于输入必须设计一个电路使得对于输入x、y、z，如果其中至少有，如果其中至少有两个为两个为1，则此电路产生输入，则此电路产生输入1。具有这样的输出值的一个布。具有这样的输出值的一个布尔函数表示是尔函数表示是xy+yz+xz。实现这个函数的电路如下图所示。实现这个函数的电路如下图所示。【example 3】有时候灯具需要由多个开关来控制，因此有有时候灯具需要由多个开关来控制，因此有必要设计这样的电路：当灯市关闭时，敲击任何一个开关都必要设计这样的电路：当灯市关闭时，敲击任何一个开关都可以打开此灯；反之，当灯市打开时，敲击任何一个开关都可以打开此灯；反之，当灯市打开时，敲击任何一个开关都可以关闭此灯。在有两个开关或三个开关两种情形下，设计可以关闭此灯。在有两个开关或三个开关两种情形下，设计电路来完成这个任务。电路来完成这个任务。18Solution：首先设计使用两个开关的电路来控制灯具。首先设计使用两个开关的电路来控制灯具。当第一个开关关闭时，令当第一个开关关闭时，令x=1；当它打开时，令；当它打开时，令x=0。当第二。当第二个开关关闭时，令个开关关闭时，令y=1,当它打开时，令当它打开时，令y=0.当灯市打开时，令当灯市打开时，令F(x,y)=1;当灯是关闭时，令当灯是关闭时，令F(x,y)=0。我们可以随意地假定：当两个开关都是关闭时，灯是打开的我们可以随意地假定：当两个开关都是关闭时，灯是打开的，即，即F(x,y)=1.这个假定决定了这个假定决定了F的所有其他值：当两个开关中的所有其他值：当两个开关中有一个是打开的时候，灯变灭了，故有一个是打开的时候，灯变灭了，故F(1,0)=F(0,1)=0；当第二；当第二个开关也被打开的时候，灯又变亮了，故个开关也被打开的时候，灯又变亮了，故F(0,0)=1.下表列出了这些值，我们可以看到下表列出了这些值，我们可以看到 实现这个函数的电路如下所示。实现这个函数的电路如下所示。19 现在设计有三个开关的电路。现在设计有三个开关的电路。设设x、y和和z是三个布尔变元，它们分别指出这三个开关是否是关闭是三个布尔变元，它们分别指出这三个开关是否是关闭的。当第一个开关处于关闭时，令的。当第一个开关处于关闭时，令x=1;当它处于接通时，令当它处于接通时，令x=0.当第当第二个开关处于关闭时，令二个开关处于关闭时，令y=1;当它处于接通时，令当它处于接通时，令y=0.当第三个开关当第三个开关处于关闭时，令处于关闭时，令z=1;当它处于接通时，令当它处于接通时，令z=0。灯亮时，令灯亮时，令F(x,y,z)=1；灯不亮时，令；灯不亮时，令F(x,y,z)=0.当所有开关都关当所有开关都关闭时，我们可以随意指定灯是亮的，即闭时，我们可以随意指定灯是亮的，即F(1,1,1)=1,这确定了这确定了F的其他值的其他值。当一个开关被接通时，灯就变灭，故。当一个开关被接通时，灯就变灭，故F(1,1,0)=F(1,0,1)=F(0,1,1)=0.当又一个开关被接通时，灯又变亮了，当又一个开关被接通时，灯又变亮了，F(1,0,0)=F(0,1,0)=F(0,0,1)=1.最后当三个开关都接通时，灯又变灭了，故最后当三个开关都接通时，灯又变灭了，故F(0,0,0)=0.这个函数的值如下表所示。这个函数的值如下表所示。函数函数F可以表示成积之和展开式：可以表示成积之和展开式：实现这个函数的电路如下所示实现这个函数的电路如下所示4.加法器加法器 一下我们将说明如何用逻辑电路从两个正整数的二进制编码一下我们将说明如何用逻辑电路从两个正整数的二进制编码来执行加法。来执行加法。我们的方法是先构造一些分支电路，然后再从这些分支电路我们的方法是先构造一些分支电路，然后再从这些分支电路来构造加法电路。来构造加法电路。首先构造电路来计算首先构造电路来计算x+yx+y，其中，其中x x和和y y是两个二进制数字。因为是两个二进制数字。因为x x和和y y的值为的值为0 0或或1 1，此电路的输入就是，此电路的输入就是x x和和y y输出由两个二进制数输出由两个二进制数字字s s和和c c构成，其中构成，其中s s和和c c分别是和位与进位。分别是和位与进位。因为这种电路具有多个输出，故称为因为这种电路具有多个输出，故称为多重输出电路多重输出电路。又由于。又由于此电路只是将两个二进制数字相加，而没有开率以前加法所产生此电路只是将两个二进制数字相加，而没有开率以前加法所产生的进位，所以这样的电路称为的进位，所以这样的电路称为半加法器半加法器。右表显示了半加法器的右表显示了半加法器的输入和输出，由此表可以输入和输出，由此表可以看出看出c=xy且且下图显示的电路计算了下图显示的电路计算了x和和y的和位的和位s与进位与进位c。当两个二进制数字与一个进位当两个二进制数字与一个进位相加时，我们用相加时，我们用全加法器全加法器来计算和来计算和位与进位。位与进位。全加法器的输入时这两个二进制全加法器的输入时这两个二进制数字数字x和和y以及此进位以及此进位ci，输出是和，输出是和位位s与新的进位与新的进位ci+1.全加法器的输全加法器的输入和输出如右表所示入和输出如右表所示 全加法器的两个输出（和位全加法器的两个输出（和位s与进位与进位ci+1）可分别由积之和展开式）可分别由积之和展开式 和和表示。但我们并不直接构造全加法器，而是使用半加法器来产生所需表示。但我们并不直接构造全加法器，而是使用半加法器来产生所需的输出。的输出。使用半加法器构造全加法器的方法如下图所示使用半加法器构造全加法器的方法如下图所示 最后下图说明了怎样用全加法器和半加法器来计算两个最后下图说明了怎样用全加法器和半加法器来计算两个3位二位二进制整数进制整数(x2x1x0)2与与(y2y1y0)2和和(s3s2s1s0)2.注意，和中的最高位注意，和中的最高位s3是由进位是由进位c2产生的。产生的。【练习练习】求以下所给电路的输出。求以下所给电路的输出。使用反相器、与门和或门构造产生下列输出的电路。使用反相器、与门和或门构造产生下列输出的电路。二、电路的极小化二、电路的极小化1.引入引入组合电路的有效性依赖于门的个数及安排。组合电路的有效性依赖于门的个数及安排。在组合电路的设计过程中，首先构造一个表，对于每种可能在组合电路的设计过程中，首先构造一个表，对于每种可能的输入值，此表说明对应的输出值。对于任一个电路，总可以用的输入值，此表说明对应的输出值。对于任一个电路，总可以用“积之和展开式积之和展开式”找到一组逻辑门来实现这个电路。找到一组逻辑门来实现这个电路。但是，积之和展开式可能包含许多不必要的项。在一个积之但是，积之和展开式可能包含许多不必要的项。在一个积之和展开式中，若其中的一些项只在一个变元处不一样，即在某个和展开式中，若其中的一些项只在一个变元处不一样，即在某个项中此变元本身出现，而在另一个项中次变元的补出现，则这些项中此变元本身出现，而在另一个项中次变元的补出现，则这些项可以合并。项可以合并。例如，考虑这样的电路，它输出例如，考虑这样的电路，它输出1当且仅当当且仅当x=y=z=1,或或x=z=1且且y=0.此电路的积之和展开式为此电路的积之和展开式为 在这个展开式的两在这个展开式的两个积中，只有一个变元以不同的形式出现，即个积中，只有一个变元以不同的形式出现，即y。它们可以如下。它们可以如下合并：合并：这样，这样，xz也是一个表示这个电路的布尔表达式，但包含更少也是一个表示这个电路的布尔表达式，但包含更少的算子。下面画出这个电路的两种不同实现的图进行比较，第二的算子。下面画出这个电路的两种不同实现的图进行比较，第二个电路只使用一个门，但第一个却使用了三个门和一个反相器。个电路只使用一个门，但第一个却使用了三个门和一个反相器。这个例子个例子说明，在一个明，在一个电路的路的积之和展开式中，将一些之和展开式中，将一些项合并会合并会导出出这个个电路的更路的更简单的表达式。的表达式。下面我们将描述化简积之和展开式的两个不同的方法。下面我们将描述化简积之和展开式的两个不同的方法。1.卡诺图（或卡诺图（或k图）图）(在少于在少于6个变量的最小化电路中非常有用个变量的最小化电路中非常有用)2.奎因奎因-莫可拉斯基方法。莫可拉斯基方法。这两种方法的目的都是为了产生布尔积的布尔和，使其所包含这两种方法的目的都是为了产生布尔积的布尔和，使其所包含的文字之积的个数最少，从而使得这些积中在表示布尔函数的积的文字之积的个数最少，从而使得这些积中在表示布尔函数的积之和中所包含的文字个数最少。寻求这种积之和的过程称为之和中所包含的文字个数最少。寻求这种积之和的过程称为布尔布尔函数的最小化函数的最小化。2.卡诺图卡诺图对于表示电路的一个布尔表达式，为了减少其中项的个数，对于表示电路的一个布尔表达式，为了减少其中项的个数，有必要去发现可以合并的项。如果布尔函数所包含的变元相有必要去发现可以合并的项。如果布尔函数所包含的变元相对较少，可以用一种图形来发现能被合并的项，此法称为对较少，可以用一种图形来发现能被合并的项，此法称为卡卡诺图诺图。卡诺图给出了一种化简积之和展开式的可视化方法，但此法卡诺图给出了一种化简积之和展开式的可视化方法，但此法不适用于将化简过程机械化。不适用于将化简过程机械化。下面首先说明怎么用卡诺图来化简包含两个变元的布尔函数下面首先说明怎么用卡诺图来化简包含两个变元的布尔函数的展开式。的展开式。在具有两个变元在具有两个变元x和和y的布尔函数的积之和展开式种，有四种可能的的布尔函数的积之和展开式种，有四种可能的小项。具有这两个边缘的布尔函数的卡诺图由四个方格组成，如果一小项。具有这两个边缘的布尔函数的卡诺图由四个方格组成，如果一个小项在此展开式中出现，则表示这个小项的方格就被放置个小项在此展开式中出现，则表示这个小项的方格就被放置1，如果一，如果一些方格所表示的小项只在一个处不一样，则称这些方格是些方格所表示的小项只在一个处不一样，则称这些方格是相邻的相邻的。例如，表示例如，表示 的方格与表示的方格与表示xy的方格及表示的方格及表示 的方格都相邻。的方格都相邻。四个方格及其表示的项如右图所示。四个方格及其表示的项如右图所示。【example 1】找出下列各式的卡诺图：找出下列各式的卡诺图：Solution：当一个方格所表示的小项在积之和展开式中出现时，我们就在这当一个方格所表示的小项在积之和展开式中出现时，我们就在这个方格中放置一个个方格中放置一个1.三个卡诺图如图所示三个卡诺图如图所示 我们可以从卡诺图中识别出能够合并的小项。在卡诺图中，一旦我们可以从卡诺图中识别出能够合并的小项。在卡诺图中，一旦两个方格式相邻的，则由这两个方格所表示的小项就可被合并成一个两个方格式相邻的，则由这两个方格所表示的小项就可被合并成一个积，且此积只涉及其中的一个变元。积，且此积只涉及其中的一个变元。例如例如 和和 是由两个相邻的方格表示的他们可以合并成是由两个相邻的方格表示的他们可以合并成一个项，即布尔表达式一个项，即布尔表达式1，它不涉及任何变元。，它不涉及任何变元。在卡诺图中如果一些小项能够合并，则在卡诺图中，我们将在卡诺图中如果一些小项能够合并，则在卡诺图中，我们将表示这些小项的方格所组成的块用圆圈圈起来，然后找出对应的表示这些小项的方格所组成的块用圆圈圈起来，然后找出对应的积之和，其目的是找出可能最大的块，以及以最少的块来覆盖所积之和，其目的是找出可能最大的块，以及以最少的块来覆盖所有的有的1，在此过程中，首先使用最大的块，并总是使用可能最大，在此过程中，首先使用最大的块，并总是使用可能最大的块。的块。【example 2】化简例化简例1的积之和展开式。的积之和展开式。Solution：用这些展开式的卡诺图对小项进行分组的方式如下图所示。用这些展开式的卡诺图对小项进行分组的方式如下图所示。这些积之和式的极小展开式是这些积之和式的极小展开式是(a)y、(b)三个变元的卡诺图是被分成八个方格的矩形，这些方格代表三个变元的卡诺图是被分成八个方格的矩形，这些方格代表由三个变元组成的八个可能的小项。两个方格称为是相邻的，由三个变元组成的八个可能的小项。两个方格称为是相邻的，如果他们表示的小项只在一个文字处不一样。一种画三个变元如果他们表示的小项只在一个文字处不一样。一种画三个变元卡诺图的方法如下图卡诺图的方法如下图a所示，这个卡诺图可以被认为是贴在圆柱所示，这个卡诺图可以被认为是贴在圆柱体的表面上，如图体的表面上，如图b所示。在这个圆柱体的表面上，两个方格有所示。在这个圆柱体的表面上，两个方格有公共边界当且仅当它们是相邻的。公共边界当且仅当它们是相邻的。三个三个变元的卡元的卡诺图(b)为了化简三个变元的积之和展开式，我们用卡诺图来识别由为了化简三个变元的积之和展开式，我们用卡诺图来识别由可以合并的小项组成的块。两个相邻放个组成的块代表了一对小可以合并的小项组成的块。两个相邻放个组成的块代表了一对小项，我们可以合并成两个文字的积。项，我们可以合并成两个文字的积。22和和41方格组成的块代方格组成的块代表可以合并成一个文字的小项，全部八个方格组成的块代表函数表可以合并成一个文字的小项，全部八个方格组成的块代表函数1，它不是任何文字的积。，它不是任何文字的积。12，21，22，41和和42块及其块及其代表的积如下图所示代表的积如下图所示.对应于卡诺图中全是对应于卡诺图中全是1的块的文字之积被称为函数的的块的文字之积被称为函数的隐含数隐含数。如果这个圈如果这个圈1的块不包含在一个更大的由的块不包含在一个更大的由1组成的块中，则称组成的块中，则称它为它为素隐含数。素隐含数。我们的目的是在图中标出最大可能块，然后用最大块优先法我们的目的是在图中标出最大可能块，然后用最大块优先法则以最少的块覆盖所有的则以最少的块覆盖所有的1.1.最大可能的块总是会被选取，但如最大可能的块总是会被选取，但如果卡诺图中只有一个块覆盖一个果卡诺图中只有一个块覆盖一个1 1，则必须选取它，这样的块称，则必须选取它，这样的块称为为本原素隐含数。本原素隐含数。通过使用素隐含数对应的块来覆盖图中所有通过使用素隐含数对应的块来覆盖图中所有的的1，便可以用素隐含数之和来表达积之和。，便可以用素隐含数之和来表达积之和。注意，以最少的块覆盖所有的注意，以最少的块覆盖所有的1可能有不止一种方法。可能有不止一种方法。【example 3】用卡诺图化简下列积之和展开式。用卡诺图化简下列积之和展开式。Solution：这些积之和展开式的卡诺图如上图所示，块的分组表明：布这些积之和展开式的卡诺图如上图所示，块的分组表明：布尔积之布尔和展开式为尔积之布尔和展开式为 在（在（d）中注意：素隐含数）中注意：素隐含数 和和 是本原素隐含数，但素是本原素隐含数，但素隐含数隐含数 则不是本原的，因为它覆盖的方格被其他两个素隐含则不是本原的，因为它覆盖的方格被其他两个素隐含数覆盖了。数覆盖了。四个变元的卡诺图是被分成四个变元的卡诺图是被分成16个方格的正方形，这些方格代个方格的正方形，这些方格代表由四个变元组成的表由四个变元组成的16个可能的小项，一种画四个变元卡诺图个可能的小项，一种画四个变元卡诺图的方法如下图所示。的方法如下图所示。四个四个变元的卡元的卡诺图 两个方格是相邻的当且仅当他们表示的小项只在一个文字处不一样两个方格是相邻的当且仅当他们表示的小项只在一个文字处不一样。因而，每个方格都和另外四个方格相邻。因而，每个方格都和另外四个方格相邻。四个变元的积之和展开式的卡诺图可以被认为是贴在圆环面上，四个变元的积之和展开式的卡诺图可以被认为是贴在圆环面上，因而相邻的方格具有公共的边界。四个变元的积之和展开式的化简也因而相邻的方格具有公共的边界。四个变元的积之和展开式的化简也是通过识别一些块来实现的，这些块可能由是通过识别一些块来实现的，这些块可能由2、4、8或或16个方格组成个方格组成，他们代表的小项必须可以合并，且每个表示小项的方格都必须被用，他们代表的小项必须可以合并，且每个表示小项的方格都必须被用来产生更少个文字的积，或者包含在展开式种。来产生更少个文字的积，或者包含在展开式种。下面我们给出了一些块，这些块表示三个文字的积两个文字的积下面我们给出了一些块，这些块表示三个文字的积两个文字的积或单个文字。或单个文字。就像两个或三个变元的卡诺图的作用一样，我们的目的也是就像两个或三个变元的卡诺图的作用一样，我们的目的也是在图中标出在图中标出1构成的最大块（对应于素隐含数），然后用最大块构成的最大块（对应于素隐含数），然后用最大块优先法则以最少的块覆盖所有的优先法则以最少的块覆盖所有的1，我们也总是使用可能最大的，我们也总是使用可能最大的块。块。下面举例说明四变元卡诺图的使用。下面举例说明四变元卡诺图的使用。【example 4】用卡诺图化简下列积之和展开式。用卡诺图化简下列积之和展开式。Solution：这些展开式的卡诺图如下所示。用所示的块可导出如下的积这些展开式的卡诺图如下所示。用所示的块可导出如下的积之和：之和：可诺图可以实际用于化简五变元或六变元的布尔函数可诺图可以实际用于化简五变元或六变元的布尔函数 ，但对，但对更多变元的函数就很少使用卡诺图了，因为它们会非常复杂。更多变元的函数就很少使用卡诺图了，因为它们会非常复杂。然而卡诺图中用到的概念在更新的算法中起着重要的作用。然而卡诺图中用到的概念在更新的算法中起着重要的作用。而且掌握这些概念有助于理解这些算法及实现算法的计算机辅而且掌握这些概念有助于理解这些算法及实现算法的计算机辅助设计程序。助设计程序。总结3.无需在意的条件无需在意的条件 在某些电路中，由于输入值的一些组合从未出现过，所以我在某些电路中，由于输入值的一些组合从未出现过，所以我们关心电路对输入值的其他组合的输出，这使得我们在生产们关心电路对输入值的其他组合的输出，这使得我们在生产具有所需输出的电路时有很大自由，因为对于所有不出现的具有所需输出的电路时有很大自由，因为对于所有不出现的输入值的组合，其输出值可以任意选择。输入值的组合，其输出值可以任意选择。函数对于这种组合的值称为函数对于这种组合的值称为无需在意的条件无需在意的条件。在卡诺图中，对于那些其函数值可以任意选择的变元值组合在卡诺图中，对于那些其函数值可以任意选择的变元值组合，用，用d对其作记号。在化简过程中，如果输入值的组合在卡诺图对其作记号。在化简过程中，如果输入值的组合在卡诺图中导致最大的块，则我们可以将其赋值中导致最大的块，则我们可以将其赋值1.【example】用二进制数字对十进制展开式进行编码的一种方法是：对用二进制数字对十进制展开式进行编码的一种方法是：对此十进制展开式中的每一位，在编码的二进制展开式中用四个二进制此十进制展开式中的每一位，在编码的二进制展开式中用四个二进制数字对其编码。数字对其编码。例如，例如，873的编码为十进制展开式的这种编码方式的编码为十进制展开式的这种编码方式称为称为十进制数二元编码。十进制数二元编码。因为有因为有16个四位二进制数，但只有个四位二进制数，但只有10个十进个十进制数字，所以还有制数字，所以还有6个四位二进制数没有被用来对数位进行编码。个四位二进制数没有被用来对数位进行编码。假设现在需要构造一个电路使得：如果数位大于等于假设现在需要构造一个电路使得：如果数位大于等于5，则输出，则输出1；若数位小于若数位小于5，则输出，则输出0.怎么仅用与门、或门、和反相器来构造怎么仅用与门、或门、和反相器来构造这个电这个电路？路？Solution：以以F(w,x,y,z)记此电路的输出，其中记此电路的输出，其中wxyz是一个十进制数位是一个十进制数位的二进制表示。的二进制表示。F的值如下表所示，下表的值如下表所示，下表a是是F的卡诺图，其中的的卡诺图，其中的无需在意位置都是无需在意位置都是d。我们可以将。我们可以将d包括在块中或者剔除出去，包括在块中或者剔除出去，这样块就有很多可能的选择。这样块就有很多可能的选择。例如，如果剔除所有的例如，如果剔除所有的d方格，则形成块如图方格，则形成块如图b所示，所产生的所示，所产生的表达式为表达式为 。如果包括某些。如果包括某些d而剔除其余的而剔除其余的，则形成的块如图，则形成的块如图c所示，且产生的表达式为所示，且产生的表达式为 最后，如果包括所有的块，且使用如图最后，如果包括所有的块，且使用如图d所示的块，则产生最所示的块，则产生最简单的展开式，即简单的展开式，即4.奎因奎因-莫可拉斯基方法莫可拉斯基方法 我们已经看到，可以用拉诺图将布尔函数展开为形如布尔积之布我们已经看到，可以用拉诺图将布尔函数展开为形如布尔积之布尔和的极小表达式。但当变元超过四个时，卡诺图就变得难以使用并尔和的极小表达式。但当变元超过四个时，卡诺图就变得难以使用并且卡诺图的使用还要依赖于用目测方法将项分成组，鉴于这些原因，且卡诺图的使用还要依赖于用目测方法将项分成组，鉴于这些原因，需要可以机械化的过程来化简积之和展开式，需要可以机械化的过程来化简积之和展开式，奎因奎因-莫可拉斯基方法莫可拉斯基方法就就是这样一种过程。是这样一种过程。奎因奎因-莫可拉斯基方法可以用于含有任意多个变元的布尔函数。莫可拉斯基方法可以用于含有任意多个变元的布尔函数。其由两部分组成：其由两部分组成：第一部分寻找可能包含在形如布尔积之布尔和的极小展开式中的候选项第一部分寻找可能包含在形如布尔积之布尔和的极小展开式中的候选项第二部分才确定哪些项将真正使用。第二部分才确定哪些项将真正使用。【example】下面说明怎么用奎因下面说明怎么用奎因-莫可拉斯基方法寻找等价于莫可拉斯基方法寻找等价于 的极小展开式。的极小展开式。Solution：用一串二进制数位来表示此展开式中的小项。如果用一串二进制数位来表示此展开式中的小项。如果x出现，则第一出现，则第一位为位为1；如果；如果 出现，则第一位为出现，则第一位为0.如果如果y出现，则第二位为出现，则第二位为1；如果；如果 出现，则第二位为出现，则第二位为0；如果；如果z出现，则第三位为出现，则第三位为1；如果；如果 出现，则出现，则第三位为第三位为0；然后感觉对应数位串中；然后感觉对应数位串中1的个数来对这些项进行分组。的个数来对这些项进行分组。这些信息如下图所示。这些信息如下图所示。可以合并的小项只在一个文字处不一样，所以，对于两个可可以合并的小项只在一个文字处不一样，所以，对于两个可以合并的小项，在表示他们的数位串中，以合并的小项，在表示他们的数位串中，1的个数仅相差的个数仅相差1.当两当两个小项被合并成一个积时，这个积只含有两个文字。两个文字的个小项被合并成一个积时，这个积只含有两个文字。两个文字的积可以如下表示：以短划线来记不出现的变元。积可以如下表示：以短划线来记不出现的变元。下表列出了所有可以合并的成对小项以及它们所产生的积。下表列出了所有可以合并的成对小项以及它们所产生的积。下一步，对于由两个文字构成的积，如果两个这样的积能够下一步，对于由两个文字构成的积，如果两个这样的积能够合并，则将之合并成一个文字。两个这样的积能够合并的条件是合并，则将之合并成一个文字。两个这样的积能够合并的条件是：他们所包含的文字是两个相同变元的文字，并且只有其中变元：他们所包含的文字是两个相同变元的文字，并且只有其中变元的文字不一致。就表示这些积的串来说，它们必定在相同位置有的文字不一致。就表示这些积的串来说，它们必定在相同位置有一个短划线，且在其余的两个位置中必定有一个位置的内容不相一个短划线，且在其余的两个位置中必定有一个位置的内容不相同。所有能够以这种方式合并的项如上页的图所示。同。所有能够以这种方式合并的项如上页的图所示。在上图中，我们还指出了哪些项可以用来形成更少文字的积，这些在上图中，我们还指出了哪些项可以用来形成更少文字的积，这些项不一定在极小展开式中。下一步是找出积的一个极小集合，使之可项不一定在极小展开式中。下一步是找出积的一个极小集合，使之可以用来表示此布尔函数。我们从那些还没有被用来形成更少文字之积以用来表示此布尔函数。我们从那些还没有被用来形成更少文字之积的积着手。的积着手。再下一步，我们构造如下的表，通过合并原来项所形成的每一个候再下一步，我们构造如下的表，通过合并原来项所形成的每一个候选积构成此表的行，原来的项构成列。如果积之和展开式中原来的项选积构成此表的行，原来的项构成列。如果积之和展开式中原来的项被用来形成候选积，则在相应的位置打上被用来形成候选积，则在相应的位置打上，此时称此候选项覆盖了原，此时称此候选项覆盖了原来的小项，我们需要至少一个积覆盖原来的每一个小项。因而一旦此来的小项，我们需要至少一个积覆盖原来的每一个小项。因而一旦此表的某一列只有一个表的某一列只有一个，则此，则此所在的行所对应的积必定被使用。所在的行所对应的积必定被使用。从上表中可以看出，从上表中可以看出，z和和 都是必需的。所以最后的答案是都是必需的。所以最后的答案是 由上面的例子可以得到使用奎因由上面的例子可以得到使用奎因-莫可拉斯基方法化简一系列积之莫可拉斯基方法化简一系列积之和展开式的步骤为：和展开式的步骤为：1）将有）将有n个变元偶成的每一个小项表示成一个长度为个变元偶成的每一个小项表示成一个长度为n的二进制数串，的二进制数串，如果如果xi出现，则此串的第出现，则此串的第i个位置为个位置为1；如果；如果 出现，则此串的第出现，则此串的第i个位置为个位置为0.2）根据串中）根据串中1的个数将串分组。的个数将串分组。3）确定所有这样）确定所有这样n-1个变元的积，它们可以取为此展开式中小项的布个变元的积，它们可以取为此展开式中小项的布尔和。将能够合并的小项表示成二进位串，且这些船只在一个位置尔和。将能够合并的小项表示成二进位串，且这些船只在一个位置不相同。将这些不相同。将这些n-1个变元的积用如下的串表示；如果个变元的积用如下的串表示；如果xi出现在此出现在此积中，则此串的第积中，则此串的第i个位置为个位置为1如果如果 出现，则此位置为出现，则此位置为0；如果此；如果此积中没有涉及积中没有涉及xi的文字，则此位置为短划线。的文字，则此位置为短划线。4）确定所有这样确定所有这样n-2个变元的积，它们可以取为在前一个步骤形成的个变元的积，它们可以取为在前一个步骤形成的n-1个变元的积的布尔和。将能够合并的个变元的积的布尔和。将能够合并的n-1个变元的积表示成如下个变元的积表示成如下的串：在同一位置有一个短划线，且只有一个位置不相同。的串：在同一位置有一个短划线，且只有一个位置不相同。5）只要可能，继续将布尔积合并成更少变元的积。只要可能，继续将布尔积合并成更少变元的积。6）找到所有这样的布尔积；它们虽然出现，但还没有被用来形成少找到所有这样的布尔积；它们虽然出现，但还没有被用来形成少一个布尔积。一个布尔积。7）找到这些布尔积的最小集合，使得这些积的和表示此布尔函数。找到这些布尔积的最小集合，使得这些积的和表示此布尔函数。这可以用如下方法来完成：构造一个表，列出哪些积覆盖了哪些小这可以用如下方法来完成：构造一个表，列出哪些积覆盖了哪些小项。每一个小项必定被至少一个积覆盖。项。每一个小项必定被至少一个积覆盖。【example】用奎因用奎因-莫可拉斯基方法化简积之和展开式莫可拉斯基方法化简积之和展开式Solution：首先将小项表示成二进位串，然后根据串中首先将小项表示成二进位串，然后根据串中1的和数来对项进的和数来对项进行分组，如下表行分组，如下表5所示所示 表表6给出了所有的布尔积，它们可以取为这些积的布尔和。给出了所有的布尔积，它们可以取为这些积的布尔和。没有被用来形成更少变元之积的只有没有被用来形成更少变元之积的只有表表7表明了每个这样的积覆盖的小项，为覆盖这些小项，必须包表明了每个这样的积覆盖的小项，为覆盖这些小项，必须包括括 因为它们是分别覆盖因为它们是分别覆盖 和和 的唯一的积。的唯一的积。一旦这两个积包括进来，我们就可以看到，只有其中的一个是必一旦这两个积包括进来，我们就可以看到，只有其中的一个是必要的。要的。因而因而 或或 都可以看作都可以看作是最后的答案。是最后的答案。本节内容到此结束本节内容到此结束