当前位置：文档之家 › 改进的Q-M逻辑函数化简方法

改进的Q-M逻辑函数化简方法

  • 格式：pdf
  • 大小：243.24 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

2.5逻辑函数的化简(2011)

2.5逻辑函数的化简(2011)
= BC D + BC D = BD
消去B
11 10
结论： 1、 2 n 个最小项合并，消去n 个变量。 2、消去K圈中变量取值发生过 变化的量。保留取值没有变 化的量。
ABC D + ABC D + ABC D + ABC D
消去A、C
A BCD + ABCD + ABCD + A BCD + ABC D + ABC D + ABC D + ABC D = ACD + ACD + AC D + AC D = CD + C D = C
消去A、B、D
4、 用卡诺图化简逻辑函数 （1）求最简与或式 化简的步骤： • 作出逻辑函数的卡诺图； • 圈卡诺圈； • 将每个卡诺圈中的最小项合并成相应的与项。 圈卡诺圈的原则： 在卡诺图上，以最少的卡诺圈数和尽可能大的卡诺圈覆盖所有填1的 方格。（即：最小覆盖原则） 注释： • 将 2 n个相邻的填1方格圈起来，圈子尽可能大； • 所有填1格都必须被圈过，在此前提下K圈的个数尽可能少； • 任何一个填1格可以被不同的K圈多次圈过，但如果在一个K圈中， 所有的1格均已被别的K圈圈过，则该圈为多余的。
F = A BC + ABC + D + AD
AB CD
01
11
10
00 01
11 10
1 0 0 1
1 0 1 0
1 0 1 0
0 1 0 1 1 1 1 1 1 1 1 1 1 1
原则：分别寻找各与项中变量相交的小方格填1. （0——反变量，1——原变量）
（3）由或与式填卡诺图（填0） 举例：
F = ∏ M (0, 2, 6) = ( A + B + C )( A + B + C )( A + B + C )

2.6 逻辑函数的化简方法

2.6 逻辑函数的化简方法

A
C
23
2.
R= BC +ABD + ACD AB+AC=0（约束条件） D 1 B 1 1 R=BC +CD +BD A C
1 1 1
24
2.6.4卡诺图的运算 1、判断逻辑函数相等 2、卡诺图的或运算：
C 1 1 +
卡诺图完全相同
C 1
A
1
A
1
B
1
B 将对应小方格中的 值求逻辑和 1 A
C 1
1
B
1
25
3、卡诺图的与运算：
C
1 1 1 . 1 1CΒιβλιοθήκη AA1 B
B 将对应小方格中的 值求逻辑乘
C
1
A B 1
26
4、卡诺图的异或运算：
C 1 A B 1 + A 1
C
1
1
B
1
将对应小方格中的 值相异或
C 1
A
1 B
27
例:X=AB+BC+CD+AD
Y=AB+BD+BD+AC
Z=ABD+ACD 试用卡诺图求:
8
D
1 5 3 2
1
1
7
1
6
13
9
15
11
14
10
1
A
F= CD +ABD +BD
1
C
16
“两个最少”原则：
1、变量最少原则：包围圈尽可能的大，但 变量的个数必须是2n;与中轴线对称的小方格 也是相邻项。
2、与项最少原则：包围圈的数量最少，画 圈时应该使每个包围圈至少包含一个没被包 围过的方格。

逻辑函数的化简省名师优质课赛课获奖课件市赛课一等奖课件

逻辑函数的化简省名师优质课赛课获奖课件市赛课一等奖课件

Y ( A B )(C D E)
Y ABC DE
Y A BC D E
对偶规则旳意义在于：假如两个函数相等，则它们旳对偶函 数也相等。利用对偶规则,能够使要证明及要记忆旳公式数目降低 二分之一。例如：
AB AB A
(A B) (A B) A
A(B C) AB AC
A BC ( A B)(A C)
退出
逻辑函数旳化简
在逻辑运算中有些逻辑函数往往不是以最简旳形式给出，这既
不利于判断这些逻辑函数旳因果关系，也不利于用至少旳电子器 件来实现这些逻辑函数，因而有必要对这些逻辑函数进行化简。 化简措施有代数法和卡诺图法。
一、逻辑函数体现式旳类型和最简式旳含义
1、体现式旳类型
一种逻辑函数，其体现式旳类型是多种多样旳。人们常按照逻 辑电路旳构造不同，把体现式提成5类：与-或、或-与、与非-与 非、或非-或非、与-或-非。
证明等式： AB A B
A B AB AB A B A+B 0 0 0 1 11 1 0 1 0 1 10 1 1 0 0 1 01 1 1 1 1 0 00 0
3.1逻辑代数旳公式、定理和规则
1、逻辑代数旳公式和定理
（1）常量之间旳关系
与运算：0 0 0
或运算：0 0 0
非运算： 1 0
2、吸收法 （１）利用公式Ａ＋ＡＢ＝Ａ，消去多出旳项。
Y1 AB ABCD(E F ) AB
利用摩根定律
假如一种乘积项
旳反是另一种乘积 项旳因子，则这个 因子是多出旳。
二、代数法化简逻辑函数
代数法化简就是反复使用逻辑代数旳基本公式和 定理，消去多出旳乘积项和每个乘积项中旳多出因 子，从而得到最简体现式。
若两个乘积项中分别 包括同一种因子旳原变量 和反变量，而其他因子都 相同步，则这两项能够合 并成一项，并消去互为反 变量旳因子。

基本逻辑电路的化简方法

基本逻辑电路的化简方法

第二章逻辑代数基础2.1 逻辑代数运算提纲：⏹逻辑变量与逻辑函数，⏹逻辑代数运算，⏹逻辑代数的公理和基本公式，⏹逻辑代数的基本定理（三个），⏹逻辑代数的常用公式。

2.1.1 逻辑变量与逻辑函数采用逻辑变量表示数字逻辑的状态，逻辑变量的输入输出之间构成函数关系。

逻辑常量：逻辑变量只有两种可能的取值：“真”或“假”，习惯上，把“真”记为“1”，“假”记为“0”，这里“1”和“0”不表示数量的大小，表示完全对立的两种状态。

2.1.2 逻辑代数运算基本逻辑运算——与、或、非；复合逻辑运算。

描述方法：逻辑表达式、真值表、逻辑符号（电路图）。

定义：真值表——描述各个变量取值组合和函数取值之间的对应关系。

逻辑电平——正逻辑与负逻辑。

2.1.3 逻辑代数的公理和基本公式2.1.3.1 逻辑代数公理有关逻辑常量的基本逻辑运算规则，以及逻辑变量的取值。

(1) 常量的“非”逻辑运算(2~4) 常量的与、或逻辑运算(5) 逻辑状态只有”0”和”1”两种取值2.1.3.2 逻辑代数的基本公式（基本定律）所谓“公式”，即“定律”，如表2. 1：表2. 1 逻辑代数的公式（基本公式部分）2.1.3.3 逻辑代数的三个基本定理所谓“定理”，即代数运算规则。

基本的三个定理：⏹代入定理——在任何一个包含逻辑变量A的逻辑等式中，若以另外的逻辑式代入式中的所有．．A的位置，则等式依然成立。

，⏹反演定理，⏹对偶定理。

2.1.3.3.1 反演定理所谓“反演定理”，得到逻辑函数的“反”的定理。

定义（反演定理）：将函数Y式中的所有…⏹（基本运算符号）“与”换成“或”，“或”换成“与”；⏹（逻辑常量）“0”换成“1”，“1”换成“0”；⏹原变量换成反变量，反变量换成原变量；注意：●变换时要保持原式中逻辑运算的优先顺序；●不属于单个变量上的反号应保持不变；则，所得到的表达式是Y的表达式。

例2.1: 已知)]([F E D C B A Y ++⋅=，求。

qm化简法

qm化简法

QM化简法
QM化简法是一种布尔代数化简方法，它基于卡诺图和奎因-麦克拉斯基方法，可以将复杂的布尔函数转换为最简形式。

QM化简法的基本原理是将布尔函数中的逻辑函数转换为最小项，并通过合并最小项来简化布尔函数。

QM化简法的具体步骤如下：
1. 将布尔函数中的逻辑函数用最小项表示。

2. 对于每个最小项，找到它的等价形式。

等价形式可以通过卡诺图的圈合并来找到。

3. 合并最小项，得到更简单的等效布尔函数。

需要注意的是，QM化简法的最终结果不唯一，因为卡诺图的圈合并方法不唯一。

在实际应用中，可以根据具体情况选择合适的圈合并方法，以得到最优的化简结果。

[精品]1.3逻辑函数公式化简法

[精品]1.3逻辑函数公式化简法

逻辑函数的公式法化简
[例] 证明公式 A BC ( A B)( A C ) [解] 方法2：真值表法 A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 C B C A BC A B A C ( A B)( A C ) 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1
A ( BC B C ) A ( BC BC )
A B C A( B C ) A
逻辑函数的公式法化简
二、吸收法：
A AB A
[例 1] Y AB AD BE
A B AD BE A B
[例2] Y AB ACD BCD
) A
(3) A AB ( A A)( A B) A B (4) AB AC BC AB AC
(5) AB AB A B AB
逻辑函数的公式法化简
公式 (4) 证明：
AB AC BC AB AC
左 AB AC ( A A) BC A AB A
取反（即还原），最后用摩根定理去掉反号。
[例] 写出函数 Y AB AC 的最简或与式。
[ 解]
Y = ( A + B)( A + C) = AC + AB + BC
= AC + AB + BC
Y AB AC AB AC ( A B ) ( A C )
逻辑函数的公式法化简
相等
相等
逻辑函数的公式法化简

逻辑函数的图形化简法

逻辑函数的图形化简法

4
每个乘积 项因子最 少，即卡 诺圈最大
卡诺图上的最小项合并规律
具有相邻性的最小项 可合并，消去不同因子
卡诺图化简
在卡诺图中，最小项的相邻性 可以从图形中直观地反映出来
1、两个相邻项的合并：消去一对因子
卡诺圈中保持不变的变量相与，每个与项最后相或，得到最后 化简的结果
A' B '
卡诺圈
AC'
2、四个相邻项的合并：消去2对因子
逻辑函数的卡诺图化简法
化简步骤
1、函数化为最小项之和形式
2、用卡诺图表示逻辑函数
3、找出可合并的最小项
4、化简后的乘积项相加（卡诺圈中保持 不变的变量相与，每个与项最后相或）
卡诺图化简原则
卡诺图化简原则
1
卡诺圈中包含 的1的个数一 定是2^n个
2
化简后的 乘积项应 包含函数 式的所有 最小项
3
乘积项的 数目最少 ，即卡诺 圈个数最 少
圈“1”的方式不同 ，可导致化简结果 不唯一
卡诺图化简 总结 圈“0”步骤：用卡诺图表达 出待化简的逻辑函数，然后 在图上圈“0”，并且，0表示 原变量，1表示反变量，变量 相“或”得到每一个或项， 最后所有的或项相“与”
如果卡诺图圈“0” ，会是什么形式？---最简或与式
1、同一个“1”可以被圈在多个卡诺圈里； 2、每个卡诺圈必须拥有至少一个“1”是自己独有的；
BC
AB
3、八个相邻项的合并：消去3对因子
D'
AB
00 00 1 01 1 11 1 10 1
Hale Waihona Puke CD01 0 0 1 1
11 0 0 1 1
A
10 1 1 1 1

改进的Q-M逻辑函数化简方法

改进的Q-M逻辑函数化简方法

改进的Q-M逻辑函数化简方法徐俊平;程利新【期刊名称】《计算机工程》【年(卷),期】2011(037)020【摘要】为进一步提高逻辑函数的化简速度,提出一种改进的Q-M逻辑函数化简方法.在迭代比较过程中设置2个权值以缩减可合并蕴涵项集合的大小,只对满足条件的蕴涵项进行合并处理,得到全部质蕴涵项.构造质蕴涵项与最小项关联图,利用启发式规则得到能蕴涵全部最小项的最少质蕴涵项集合,从而得到逻辑函数的最小覆盖,完成逻辑函数化简.实验结果表明,该算法能降低迭代次数,减少逻辑函数的化简时间.%In order to improve the simplification speed of logic functions, this paper proposes an improved Q-M method for simplification of logic functions. The size of implicants set is decreased by using a pair of weights in the iteration process of comparison, only the implicates which satisfy the conditions is merged. And all prime implicants are obtained at last. Bipartite graph which is consists of prime implications and minterms is structured. The least prime implicants containing all of the minterns, that is, the minimum coverage of logic functions is obtained by heuristic approach. Experimental results show that the number of iterations can be reduced, and the speed of simplification can be accelerated.【总页数】3页(P30-32)【作者】徐俊平;程利新【作者单位】哈尔滨工程大学计算机科学与技术学院,哈尔滨150001;哈尔滨工程大学计算机科学与技术学院,哈尔滨150001【正文语种】中文【中图分类】TP331.1【相关文献】1.逻辑函数的另一种化简方法--Q-M化简法 [J], 张冰2.一种新型逻辑函数化简方法——立体化简法 [J], 陶永明3.基于改进遗传算法的逻辑函数化简 [J], 朱海燕4.用解逻辑方程的方法化简互斥多变量逻辑函数 [J], 周亮5.具有大非号逻辑项的较复杂逻辑函数化简的简便方法 [J], 邱志川;李满成因版权原因，仅展示原文概要，查看原文内容请购买。

利用Q-M原理进行的逻辑化简程序

利用Q-M原理进行的逻辑化简程序

引言：逻辑函数化简在数字电路中有着非常重要的作用。

如果一个逻辑函数的表达式比较简单，那么实现它的电路使用的元器件就少，设备就简单，运算速度就快。

在本文中讨论的逻辑函数化简，是将一个逻辑函数的表达式简化成最简或-与式。

所谓最简或-与式，是或-与表达式中乘积项（与项）的个数最少，而且力求每一个乘积项中包含的变量数最少。

我们熟悉的逻辑函数化简方法是卡诺图法。

卡诺图法具有简单、直观的优点，但当变量数目达到或超过5个以后，卡诺图将变得很复杂，甚至无法使用。

而列表法对于解决多变量逻辑函数化简具有显著的优越性，并且这种方法有严格规则和步骤，便于计算机操作。

列表法最早由Quine和Mcluskey提出，因此该法又称为Q-M法。

许多数字电路课本上给出了便于手工计算的列表法，但并没有给出实际利用计算机语言实现的方法。

本文探讨利用C语言实现Ｑ-M法。

一：制作内容：利用Quine-McCluskey表格法原理，用c++语言实现一个简易的逻辑代数化简程序，求出最简表达式，做到准确，迅速，方便人们进行逻辑化简。

二：实验原理：算法简述：1，列出函数的所有最小项2，找出所有的质蕴涵项（第一步和第二步）3，第一步：将最小项按重量（1的个数）分组。

4，第二步：穷尽地找出所有的质蕴涵项。

5，找出最小的质蕴涵项覆盖（第三步和第四步）6，构造质蕴涵项表7，选择最小数目的质蕴涵项覆盖（最小覆盖）覆盖过程(Covering Procedure)1，第一步：标示出所有只被某个PI覆盖的最小项，将这些PI加入覆盖中（实质蕴含项）。

2，第二步：在质蕴涵项图中去掉所有在第一步中标示出的PI覆盖的行，同时去掉被这些PI覆盖的最小项的列。

3，规则1：如果一行被其它行覆盖，去掉该行4，规则2：如果一列覆盖其它列，去掉该列5,第三步：如果第二步的结果是一个循环图表，进入第五步。

否则再次执行第一部和第二步。

6,第四步：如果第三步的结果是一个循环图表，进入第五步。

电工电子技术-逻辑函数的化简

电工电子技术-逻辑函数的化简

（2）吸收法
运用公式 A AB A 消去多余的项，其中，A、B可以是
任意一个复杂的逻辑式。例如：
Y1 AB AC DEB AB
Y2 AB ABC ABD AB D E AB AB C D D E AB
（3）消去法
运用公式 A AB A B 消去多余的因子。例如：
例如：逻辑函数Y的卡诺图。 Y ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
（3）用卡诺图化简逻辑函数式 使用卡诺图化简逻辑函数所依据的原理是：具有相邻性 的最小项可以合并消去不同的因子。 ①2个相邻的最小项结合（用一个包围圈表示），可以消 去1个取值不同的变量而合并为1项，如下图所示。
00 01 11 10 00
01 11 10
②4个相邻的最小项结合（用一个包围圈表示），可以消 去2个取值不同的变量而合并为l项，如下图所示。
00 01 11 10 00
01 11 10
③8个相邻的最小项结合（用一个包围圈表示），可以消 去3个取值不同的变量而合并为l项，如下图所示。
00 01 11 10 00
②化简具有无关项的逻辑函数 在卡诺图中用×表示无关项。使用卡诺图化简逻辑函数 式时，要充分利用无关项可以当0也可以当1的特点，尽量扩 大卡诺圈，使逻辑函数式更简。
（2）卡诺图
卡诺图就是将n变量的全部最小项各用一个小方块表示，
并使具有逻辑相邻性的最小项在几何位置上也相邻的排列起 来所得的图形。下图所示为2到4变量最小项的卡诺图。
若要画出某一逻辑函数的卡诺图，只需将该逻辑函数式 化为最小项之和的标准形式后，在卡诺图中这些最小项对应 的位置上填入1，在其余的位置上填入0即可。
1．公式化简法

逻辑函数的化简

逻辑函数的化简

1.3.4 逻辑函数的化简•对逻辑函数进行化简，可以求得最简逻辑表达式，也可以使实现逻辑函数的逻辑电路得以简化，这样既有利于节省元器件，也有利于提高可靠性。

•逻辑函数有如下三种化简方法：•公式化简法：利用逻辑代数的基本公式和规则来化简逻辑函数。

•图解化简法：又称卡诺图（Karnaugh Map）化简法。

•表格法：又称Q－M（Quine-McCluskey）化简法。

1.逻辑函数的公式化简法同一个逻辑函数，可以用不同类型的表达式表示，主要有以下五类：“与或”表达式、“或与”表达式、“与非”-“与非”表达式、“或非”-“或非”表达式、“与或非”表达式。

例如函数：=+Z AC AB“与或”表达式A B A C“或与”表达=++()()式AC AB“与非”-“与非”表达=⋅式=+++A B A C“或非”-“或非”表达式“与或非”表达式判断最简“与或”表达式的条件如下：(1)乘积项（即与项）个数最少的“与或”表达式；(2)当乘积项个数相等，则每个乘积项中因子（即变量）的个数最少的“与或”表达式。

例1-5 以下4个“与或”表达式是相等的，即它们表示同一个函数：(1)(2)(3)(4)=+++=++=++=++Z AC BC AB ACAC ABC ACAC BC ACAC AB AC 试判断哪一个是最简“与或”表达式。

(1)(2)(3)(4)=+++=++=++=++Z AC BC AB ACAC ABC ACAC BC ACAC AB AC 解：根据判断条件（1），式（1）含有4个与项，而式（2）～（4）都含有3个与项，因此，式（2）～（4）有可能最简；进一步比较与项中个数，式（3）和式（4）中，各与项都含2个变量，而式（2）中有一个与项含3个变量。

结论：式（3）和式（4）同为该函数的最简“与或”表达式。

公式法化简：借助定律和定理化简逻辑函数，常用以下几种方法。

(1)并项法利用互补率1A A +=()+=+=A BC A BC A B C C A B()()+++=⋅⊕+⋅⊕=A BC BC A BC BC A B C A B C A+=B ABD B，将两项合并为一项，合并时消去一个变量，如：(2)吸收法利用定理1（A + AB = A ），吸收掉（即除去）多余的项，如：(3)消去法利用定理2（+=+A AB A B ()++=++=+=+AB A C BC AB A B C AB ABC AB C(4)配项法根据互补律，利用()=+B A A B +A A ()()+++=+++++AB BC BC AB AB BC A A BC AB C C =+++++AB BC ABC A BC ABC ABC()()()=+++++AB ABC BC ABC A BC ABC =++AB BC A C），消去多余的因子，如：，先添上（）作配项用，以便最后消去更多的项。

C语言实现基于Q-M算法的逻辑化简程序

C语言实现基于Q-M算法的逻辑化简程序
而利用胡凯同学的程序，得到的输出结果如下: A'.B'.C'.D+A.B'.C.D.E'+B.C'.D'.E'+A.B.D.E+ A'.C'.E' 显然两者无法匹配。 经过分析后发现，这是由于对程序测试时只采用了教材中有限的几个例子，而这几个例 子的代表性又不够造成的。具体错误成因分析如下： 上式中的五变量函数经过列表法化简后得到的 PRIME IMPLICANT TABLE 如下： 表 1.必要质蕴涵项产生表 0 10110 0001-1000 01-10 0111-1111 11-11 0-0-0 √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ 2 3 8 10 14 15 22 √ 24 27 31
输入表达式时，结果如下：
输入表达式：AB+ABC+C’时 输出：AB+C’ 显然结果是正确的。 选用教材中的例子，输入 A’BC+A’B’D+AC’D+BC’D’+A’BC’D，得到的结果如下图：
与教材中 P211 页的结果一致。 修改程序中的#define 的最大位宽上限值，还可以求更大位宽的逻辑化简。
n
个“1” 方格所
对应的最小项都是函数的蕴涵项。 质蕴涵项: 若函数的一个蕴涵项不是该函数中其它蕴涵项的子集, 则此蕴涵项称为质蕴涵项 ( Prime Implication) , 简称为质项。显然, 在函数卡诺图中, 按照最小项合并规律, 如果某个 卡诺圈不可能被其它更大的卡诺圈包含, 那么该卡诺圈所对应的“与”项为质蕴涵项。 必要质蕴涵项: 若函数的一个质蕴涵项所包含的某一个最小项不被函数的其它任何质蕴涵 项包含，则此质蕴涵项被称为必要质蕴涵项( Essential Prime Implication) , 简称为必要质项。 在函数卡诺图中,若某个卡诺圈包含了不可能被任何其它卡诺圈包含的 1 方格, 那么该卡诺 圈所对应的“与”项为必要质蕴涵项。 2) 系统列表化简法的思路和化简步骤 2.1 系统列表化简法的思路 系统列表化简法的思路是通过找出函数 F 的全部质蕴涵项、必要质蕴涵项以及最简质蕴涵 项集来求得最简表达式。 它与卡诺图化简法所不同的是, 在 Q ) M 化简法中上述结果都是通 过约定形式的表格, 按照一定规则求得的。 2.2 系统列表化简法的化简步骤 系统列表化简法的化简步骤一般可以概括为以下四步: 第一步: 将函数表示成/ 最小项之和 0 形式, 并用二进制码表示每一个最小项。 第二步: 找出函数的全部质蕴涵项。寻找函数全部质蕴涵项的方法是先将 n 个变量函数中 的相邻最小项合并, 消去相异的) 个变量, 得到( n- 1) 个变量的“与”项, 再将相邻的 ( n-1) 个变量的“与”项合并, 消去相异的变量, 得到( n- 2) 个变量的“与”项, 依此 类推, 直到不能再合并为止。 所得到的全部不能再合并的 “与”项 包括不能合并的最小项) , 即所要求的全部质蕴涵项。 第三步: 找出函数的必要质蕴涵项。 第四步: 找出函数的最小覆盖。 以上各步均是通过表格进行。

逻辑函数的化简逻辑函数的最简形式逻辑函数的公式化简法

逻辑函数的化简逻辑函数的最简形式逻辑函数的公式化简法

AB BC
上页
11
下页
返回
2019/1/10
第五节 逻辑函数的化简
根据公式
A A 1
( A A) ，
可在逻辑函数式中的某一项乘
然后拆成两项分别与其他项合并。 [例2.5.13]： Y
BC AC AB
( A A)BC AC AB
ABC ABC AC AB
Y A( BC ) ABC [例2.5.3]： A(( BC ) BC ) A
上页
5
下页
返回
2019/1/10
第五节 逻辑函数的化简
[例2.5.4]：用并项法将
Y BCD BCD BCD BCD
化简为最简与-或表达式。 解： Y BCD BCD BCD BCD
AB AC
上页
12
下页
返回
2019/1/10
第五节 逻辑函数的化简
综合法
[例2.5.14]：
Y AC BC BD CD A( B C ) ABCD ABDE
AC BC BD CD A( BC ) ABCD ABDE AC ( BC A( BC )) BD (CD ABCD) ABDE
上页
10
下页
返回
2019/1/10
第五节 逻辑函数的化简
5.配项法 根据公式
A A A
可在逻辑函数式中重复写入某一项。 [例2.5.12]： Y
ABC ABC ABC
ABC ABC ABC ABC
AB(C C ) ( A A)BC
返回

qm法化简逻辑表达式

qm法化简逻辑表达式

qm法化简逻辑表达式
要使用QM法对逻辑表达式进行简化，首先需要将逻辑表达式转换为真值表。

然后，按照QM法的步骤进行简化：1. 将真值表中值为1的项组成一组初始最小项集合。

2. 使用QM法将最小项集合进行配对，找到可以合并的项组成较大项。

3. 对较大项再次进行配对合并，直到无法再进行合并。

4. 将无法合并的项组成最终的简化表达式。

下面是一个例子：假设我们有一个逻辑表达式为：A'B + AC + ABC'首先，将逻辑表达式转换为真值表： A B C A'B AC ABC' 0 0 0 1 0 0 0 0 1 1 0 0
0 1 0 0 0 0 0 1 1 0 0 0 1
0 0 0 0 0 1 0 1 0 1 1 1 1
0 0 0 0 1 1 1 0 0 0 从真值表中可以得到初始最小项集合：{A'B, AC, ABC'}接下来，进行配对合并：首先，A'B可以和ABC'合并为：A'B + ABC'然后，再次进行合并，AC可以和A'B + ABC'合并为：AC最后，无法再进行合并，所以最终的简化表达式为：AC因此，逻辑表达式经过QM法化简后变为AC。

4逻辑函数的化简方法

4逻辑函数的化简方法

m9 m11 m10
卡诺图的特点：具有循环邻接的特性。
（14）
5变量卡诺图
CDE AB
000 001 011 010 110 111 101 100 m0 m8 m1 m3 m2 m m66 m7 m55 m m44 m
00 01
m9 m11 m10 m m13 m12 m14 13 m 12 14 m15 m
10
1
1
B
A
有重复“1”者，只填一个“1”。
C
（28）
例1: F1 (A, B, C, D) AB BD ABD ABCD AB CD 填公因子 A B 00
包含的项
刷项：
D
01
11 10
00
01
公因子: BD 11
1 1
1 1
B
A
10
有重复“1”者，只填一 F1 (A, B, C, D) AB BD ABD ABCD AB CD 填公因子 A B 00
11
10
0 1 0 1
1 0 0 1
0 0 1 1
0 1 0 1
（20）
化简原则
• 如果两个最小项相邻，可以合并为一项 并消去一对因子； • 如果四个最小项相邻，可以合并为一项 并消去两对因子； • 如果八个最小项相邻，可以合并为一项 并消去三对因子； • 如果2n 个最小项相邻，可以合并为一项 并消去n对因子。
（18）
L m(15,13,10,6,0)
所以，L的卡诺图为：
CD 00 AB 00 01 01 11 10
0
1 1 1
1
1 0 1
1
1 0 1
1
0 1 0

一种改进的卡诺图化简法

一种改进的卡诺图化简法

一种改进的卡诺图化简法作者：严单贵来源：《科教导刊》2013年第25期摘要针对传统卡诺图化简逻辑函数存在的问题，提出一种改进的卡诺图化简法，其改进主要体现在卡诺图的构建、逻辑函数中最小项的标示和卡诺图的填写等方面。

利用改进后的卡诺图化简逻辑函数，可使化简过程更加直观、易懂，从而有利于改善分析效果，提高工作效率。

关键词逻辑函数卡诺图化简中图分类号：TB112 文献标识码：A0 前言逻辑函数的化简有公式法、卡诺图法和系统简化法。

公式法是利用逻辑函数的基本定律和常用公式化简逻辑函数，要求熟练掌握逻辑代数的基本公式，且化简后的表达式是否最简很难判断；系统简化法主要针对多变量（5变量以上）的逻辑函数，其化简过程复杂，需要借助计算机工具；卡诺图法是由美国工程师卡诺（Karnaugh）提出的一种描述逻辑函数的特殊方法，这种方法是将个变量的逻辑函数，按循环码的规则来排列变量的取值组合，填入一个矩形或正方形的二维空间中，把矩形或正方形划分成个小方格，这些小方格分别代表变量逻辑函数的个最小项（最大项），每个最小项（最大项）占一格。

卡诺图法由于具有直观、方便、无需记忆逻辑代数的基本公式，以及无需担心化简后的表达式是否是最简等优点，成为广大工程设计人员化简逻辑函数最常用的方法。

本文在传统卡诺图化简法的基础上，给出一种改进的卡诺图化简法，利用这种方法，可使化简过程变得更加直观、易懂，从而有利于改善分析效果，提高工作效率。

1 传统的卡诺图化简法传统的卡诺图化简，通常先将逻辑函数变换为最小项表达式，然后将卡诺图中对应最小项的小方格填“1”，其余小方格填“0”，圈“1”合并最小项得到最简与或式，圈“0”得到最简或与式。

以圈“1”得到最简与或式为例，考虑以下逻辑函数的简化：= + + + + + + （1）作出卡诺图，如图1所示：按照传统卡诺图化简步骤，得到化简后的函数表达式：= + + + = + + +（2）按照以上方法化简，笔者在分析中发现，主要存在以下几个问题：（1）首先必须正确填写卡诺图，即将逻辑函数中的所有最小项对应到卡诺图的小方格中，并在小方格中填上“1”，这就要求对用最小项表示（逻辑变量表示）的逻辑函数和用二进制代码（数字）标示的卡诺图之间的对应关系要非常清楚，这实际上是比较困难的，而一旦填写出错，哪怕是其中的一个小方格填错，则整个的化简结果就会出错。

化简逻辑函数的新方法

化简逻辑函数的新方法

收稿日期：!""!#"!#!$；修改稿收到日期：!""!#"%#&’作者简介：宋海声（&$()—），男，甘肃甘谷人，讲师*主要研究方向为计算机应用与电子技术应用*化简逻辑函数的新方法宋海声（西北师范大学物理与电子工程学院，甘肃兰州’+""’"）摘要：代数法化简逻辑函数的难点在于没有固定的方法和步骤，因而也无函数式是否化简到了最简的判别方法*为解决这些难题，提出了“镜像消元法”，给出了化简的具体步骤和方法*对于(个以上变量的逻辑函数的化简，镜像消元法优于卡诺图法*关键词：数字电路；逻辑函数；代数化简法；镜像对称中图分类号：,’&；,-))文献标识码：.文章编号：&""&#$//!（!""!）"+#""+’#"%01234564789:;<96=9>?<4?9@6A>@294>8BC-D EF9#831>?（G4<<1?146H3=89@8F>5I<1@274>9@I>?9>1179>?，-4723J182-47:F<K>9L17892=，MF>N34A ’+""’"，DF>8A ，G39>F ）!"#$%&’$：,3171F71>471?A<F7:12345F>5821;8647951>296=9>?231<4?9@6A>@294>89>2319789:;<17647:8*BA@359669@A<29183FL1O11>4L17@4:159>2398J47P O=F;;<9@F294>46231:977478=::127=:12345，F>5231@4>@712189:;<96=9>?821;8F71?9L1>*,31;7181>2:1234598O1221723F>QF7>FA?3:F;;9>?64789:;<96=9>?<4?9@6A>@294>846:47123F>89R LF79FO<18*()*+,%-#：59?92F<@97@A92；<4?9@6A>@294>；F<?1O7F9@F<89:;<969@F294>；:977478=::127=逻辑函数的化简是电子技术中最重要的基本理论之一*在数字电路的分析和设计中，逻辑函数式越简单，它所表示的逻辑关系越明显，同时也利于用最少的电子器件实现这个逻辑函数*一般直接根据逻辑要求归纳出来的逻辑函数式，往往不是最简形式，这就需要通过化简的手段得到最简形式*现有的化简方法主要有卡诺图法和代数法*&代数化简法代数化简法是使用逻辑代数的基本定律和基本公式进行化简，其优点是没有变量个数的局限性［&］*人们对代数化简的方法已做过许多探讨，提出了不少化简的方法，如吸收法、配方法、消因子法［!，+］，等等，但面对要化简的逻辑函数往往不能快速准确地化简，主要还靠经验技巧，而且不易判断是否已最简，这使得代数化简法的应用受到限制*针对上述问题，笔者提出了“镜像消元法”*一些文献在阐述卡诺图化简逻辑函数的基本原理时，普遍是从卡诺图的几何相邻与逻辑函数的逻辑相邻的一致性上来解释的，认为“卡诺图是逻辑函数的最小项方块图表示法，它用几何位置上的相邻，形象地表示了组成逻辑函数的各个最小项之间在逻辑上的相邻性”［)］*笔者将这种解释简称为“一致性原理”*该原理符合!元、+元、)元卡诺图逻辑化简的实际过程，取得了积极的成效*!卡诺图化简的“一致性原理”!"#卡诺图表示法将!变量的全部最小项用小方块表示，并使具有逻辑相邻性的最小项在几何位置上也相邻地排列起来，图&给出了!变量到%变量卡诺图的画法*’+第+/卷!""!年第+期西北师范大学学报（自然科学版）S4<T+/!""!-4T+U4A7>F<46-4723J182-47:F<K>9L17892=（-F2A7F<B@91>@1）万方数据!!""!#!#""#$#%（&）$变量"、!的卡诺图!$ "!" !""!!#!#"#%#$ "#’#(#)#*（+）%变量"、!、$的卡诺图#!$!""!%!""! !!#!#"#%#$"#’#(#)#* ""#"$#"%#"(#"’!#,#-#""#"!（.）’变量"、!、$、%的卡诺图&!"$!"!""!%!""!!""!!!#!#"#%#$#",#"-#")#"* "#’#(#)#*#$$#$%#$"#$!""#"$#"%#"(#"’#%!#%"#$-#$, !#,#-#""#"!#$*#$)#$(#$’（/）(变量"、!、$、%、&的卡诺图图"$0(变量卡诺图图形两侧标注的!和"表示使对应小方格内最小项为"的变量取值，为保证几何位置相邻的最小项在逻辑上也具有相邻性，这些二进制数码不能按自然二进制数顺序排列，必需排成循环码1从图"知，处在任何一行或一列两端的最小项也具有逻辑相邻性，因此从几何位置上应当把卡诺图看成是上下、左右闭合的图形1!"!卡诺图化简法如果有$’个最小项相邻（’2"，$，……），并排列成一个矩形组，则它们可合并为一项，并消去’个因子1合并后的结果中仅包含这些最小项的公共因子［$］1这样反复应用"3!"2"的关系，就可使逻辑表达式得到化简1图$画出了$、’、,个最小项相邻的几种情况1例如在图$（&）中：!"!$（#%）和"!$（#)）相邻，故可合并为!"!$3"!$2（!"3"）!$2!$1合并后将!"和"消去，只余下公共因子!和$1在图$（+）中：!"!!$%（#(）、!"!$%（#)）、"!!$%（#"%）和"!$%（#"(）相邻，故可合并为!"!!$%3!"!$%3"!!$%3"!$%2!"!%（!$3$）3"!%（!$3$）2!%1合并后将"和!"、$和!$消去，余下公共因子!和%1同理，在图$（.）中，上边,个最小项（#!，#"，#%，#$，#’，#(，#)，#,）相邻，可合并为一项，结果为!"1但是，在(元以上的多元卡诺图中，一致性原理遇到了困难，即在(元以上的多元卡诺图中，出现了“逻辑相邻”而“几何不相邻”的情况，如例"所示1例#化简逻辑表达式!"!!$"%&(3!"!!$%&(3"!!$"%&(3"!!$%&(解法#（公式法）!"!!$"%&(3!"!!$%&(3"!!$"%&(3"!!$%&(2!"!!$&(（%3"%）3"!!$&(（%3"%）2!"!!$&(3"!!$&(2!!$&(（!"3"）2!!$&(1解法!（卡诺图法）例"所示逻辑表达式的卡诺图如图%所示，几何不相邻1为了叙述方便，我们将例"揭示的逻辑相邻而几何不相邻的现象称为“非一致现象”1显然，“非,%西北师范大学学报（自然科学版）第%,卷45678&95:;57<=>?@<;57#&9A8BC?7@B<D（;&<67&9E.B?8.?）F59G%,万方数据一致现象”在!元以下的卡诺图中是不存在的，它只存在于"元及"元以上的多元卡诺图中#“非一致现象”的存在是多元卡诺图实际使用困难的根源，它使许多专业人员感到困惑#正如文献［!］指出的那样：“当逻辑变量多于$个时，不仅画图十分麻烦，而且即使画出来了，许多小方块———最小项是否具有逻辑上的相邻性也难以辨别#”因此深入讨论“非一致现象”，总结其内在规律，就成为多元卡诺图能否得到实际应用的关键#（%）&个最小项相邻（’）!个最小项相邻（(）)个最小项相邻图&最小项相邻的几种情况*镜像对称图*所绘出的$元卡诺图中的!个最小项虽然不具有几何相邻的特性，但是却鲜明地显示和谐的对称性，仔细地观察和分析不难看出，这些逻辑相邻的最小项具有线对称的明显特征#例如我们把变量!和!!的分界线"+"比做镜子，那么关于变量!逻辑相邻的最小项"#"$%!!和#"$%!&’在卡诺图上恰恰关于镜面"+"对称，既互为镜像位置#大量的计算表明，上述现象是普遍存在的，因此，我们可以得出如下的结论：以某变量(和"(的分界线)+)为镜面，卡诺图中的最小项凡在镜像位置也有最小项与之对应时，则它们之间关于变量(的逻辑相邻成立，这些最小项可合并同时将(变量元消去#由上述结论还可得出以下推论：推论!卡诺图的几何相邻项都可按镜像操作的特例看待，卡诺图的变量元到!个以下时，镜像关系退变为几何相邻关系#推论"多元卡诺图应被看作是多层次的镜像,*&--&年第*期宋海声：化简逻辑函数的新方法&--&./0*1234/56/789:;<96=9>?@/?9(AB>(39/>C 万方数据系统，分析高层次成像关系时，应将低层次系统做为一个整体来操作!推论!镜像操作过程中，可将某些最小项做为"个或#个以上的其他最小项的项!图#$元卡诺图%实例研究例"!（"，#，$，%，&，’）&!（’，#，%，(，)，*，+"，+#，"’，"+，"*，",，#+，#%，#(，#*，#,，%"，%(，%$，(’，(%，(*，$+，$"，$#）!解绘$元卡诺图如图%所示（附文后）!图中黑点和连线表示镜像对称关系!（(’，(%，(*，(+"）关于镜面)-)和*-*对称，消去%、$变元，结果为"""#"&"’!（(#，()，(#(，(#,）关于镜面)-)和+-+对称，消去%、"变元，结果为"#"$&’!（((，(%，(+#，(+"，(",，("*，("+，("’）关于镜面,-,、*-*和!-!对称，消去#、$、’变元，结果为""%"&!（(+#，(",，($+，(%(）关于镜面+-+、,-,对称，消去"、#变元，结果为$%"&’!（(#+，(",，($#，($+）关于镜面+-+、---对称，消"、&变元，结果为#$%’!（((’，((%，((*，($"，(%"，(%$，(#%，(#*）关于镜面,-,、*-*、)-)对称，消去#、$、%变元，结果为"&"’!最后得到最简结果为!（"，#，$，%，&，’）&"""#"&"’."#"$&’.""%"&.$%"&’.#$%&."&"’!(讨论卡诺图的几何相邻与逻辑函数的逻辑相邻在" /%元卡诺图中表现出的一致，使人很难去怀疑它的正确性，甚至在多元逻辑函数化简遇到困难时也不抛弃众所公认的卡诺图!+,),、+,*’年有些学者早已已注意到多元卡诺图中逻辑相邻的最小项的对称性，但没有引起广泛的重视和深入的理论探讨!本文提出的镜像操作是对卡诺图化简机制的新的探索，进一步的分析还表明，卡诺图中的逻辑相邻最小项可能还具有某些点对称特性，从几何相邻的狭隘观点拓宽到几何对称的境界，我们会进一步’%西北师范大学学报（自然科学版）第#*卷0123456178139:;<=9813>56?4@A<3=@9B（8592356CD@<4D<）E16F#*万方数据认清卡诺图的本质，并为应用计算机编排卡诺图软件建立起具有扎实的理论基础的数学模型!图"例#卡诺图参考文献：［$］李士雄，康源!数字集成电子技术教程［%］!北京：高等教育出版社，$&&’!［#］阎石!数字电子技术基础［%］!北京：高等教育出版社，$&&#!’(—’)!［’］康华光!电子技术基础［%］!北京：高等教育出版社，$&**!$$—’*!［"］清华大学电子学教研室!数字电子技术基础简明教程［%］!北京：高等教育出版社，$&*(!$*&!（责任编辑孙晓玲）$"#++#年第’期宋海声：化简逻辑函数的新方法#++#,-.’%/01-23-45678963:6;<=-<6>?@;>06-;A 万方数据。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

ｓｒｃｕ ｅ ｔｕ ｔｒｄ．Ｔ ｅ ｌａ ｔｐ ｍｅ ｉ ｌｃ ｎｓｃ ｎａｎｎ ｌｏ ｎｅ ｓ ｈａ ｓ ｈｅ ｍｉｉ ｍ ｏｖ ｒｇ ｆｌｇｃ ｆ ｎ ｔｏ ｓｉ ｂａｎ ｄ ｂ ｅ ｒｓｉ ｈ ｅ ｓ ｒ ｉ ｍｐ ｉａ ｔ ｏ ｔｉｉｇ ａ ｆｔ ｍｉｔｍ ，ｔ ｔｉ，ｔ ｎｍｕ ｃ ｅ ａ ｅ ｏ ｏ ｉ ｕ ｃｉｎ ｓｏ ｔｉｅ ｙ ｈ ｕ ｔ ｌ ｈｅ ｉ ｃ
关奠诩 ：逻辑 函数化 简；Ｑ Ｍ 方法 ；质蕴涵项 ；二分 图；最小覆盖 —
Ｉ ｒ ｖ ｄＱ－ Ｍｅｈ ｄｆｒ ｉ ｌ ｃ ｔ ｎ０ ｏ ｉ Ｆ ｎ ｔ ｎ ｍｐ ｏ ｅ Ｍ ｔｏ ｍｐｉ ａｉ ｆ ｇｃ ｕ ｃｉ ｓ ｏＳ ｉ ｆ ｏ Ｌ ｏ
ＸＵ ｕ ・ ｉ ｇ ＣＨＥＮＧ ・ｉ Ｊ ｎｐｎ ． Ｌｉ ｎ ｘ
涵 项集合 的大小 ，只对满足条件 的蕴涵项进行合并处理 ，得到全部质蕴涵项 。构造 质蕴涵项与最小项关联图 ， 用启 发式规 则得到能蕴涵 利
全部最小项 的最少质蕴 涵项集合 ，从而得到逻辑 函数 的最小覆盖 ，完成逻辑函数化简 。实验结果表明 ， 算法能降低 迭代次数 ，减少逻辑 该
函数 的化 简时间。
ａ ｐ ｏ ｃ ． ｐ ｒｍｅ ｔ ｌ ｅ ｕ ｔ ｈ ｗ ａ ｅｎ ｍｂｅ ｆ ｔｒ ｔ ｎ ａ ｅ ｒ ｄ ｃ ｄ ａ ｄ ｔ ｅ ｓ ｅ ｄ ｏ ｍｐ ｉ ｃ ｔｏ ａ ｅ ａ ｃ ｌ ｒ ｔ ｄ ｐ ｒ ａ ｈ Ｅｘ ｅ ｉ ｎ ａ ｓ ｌ ｓ ｏ ｔ ｔｔ ｕ ｒ ｓ ｈ ｈ ｒｏ ｅ ａ ｉ ｓｃ ｎ ｂ ｅ ｕ ｅ ， ｎ ｈ ｐ ｅ ｆｓ ｉ ｏ ｉ ｌ ａｉｎＣ ｂ ｃ ｅｅａｅ ． ｉ ｆ ｎ
ｈ ｏ ｄ ｔ ｎｓ ｉ ｒ ｅ ．Ａｎ ｌ ｐ ｍ ｅ ｉ ｐ ｉ ａ ｔ ｒ ｂ ａｎ ｄ ａ ａ ｔ ｔ ｅ ｃ ｎ ｉ ｏ ｓ ｍｅ ｇ ｄ ｉ ｄ ａｌ ｒ ｉ ｍ ｌ ｎ ｓ ａ ｅ ｏ ｔ ｉ ｅ ｔ ｌ ｓ．Ｂｉ ａ ｔ ｅ ｇ ａ ｈ ｗｈ ｃ ｓ ｃ ｓｓｓ ｏ ｒｍｅ ｉ ｌｃ ｔ ｎ ｎ ｎ ｅ ｍｓ ｉ ｃ ｐ ｒ ｔ ｒ ｐ ｉ ｈ ｉ ｏｎ ｉｔ ｆ ｐ ｉ ｉ ｍｐ ｉ ａ ｉ ｓ ａ ｄ ｍｉ ｔｒ ｓ ｏ
中圈分类号ｔ Ｐ３． ３１ Ｔ １
改进 的 Ｑ－ 逻辑 函数化 简方法 Ｍ
徐ቤተ መጻሕፍቲ ባይዱ平 ， 利新 程
（ 哈尔滨工程大学计算机科学与技术学院 ，哈尔滨 １０ ０ ） ５０ １
摘 要 ：为进 一步提 高逻辑 函数的化 简速 度，提 出一种 改进的 Ｑ Ｍ 逻辑函数化简方法 。在迭代比较过程 中设置 ２个权 值以缩减可合并蕴 —
（ ｌ ｇ ｆ ｏ ｕｅ ｃｅ ｃ ｎ ｅｈ ｏｏ ｙＨａｂｎＥ ｇｎ ｅ ｎ ｎｖｒｉ ， ｒｉ ５ ０ １Ｃ ｉａ Ｃｏｌ ｅ ｍｐ ｔｒ ｉｎｅａｄＴ ｃ ｎ ｌｇ ， ｒｉ ｎ ｉｅｒ ｇＵ ｉｅｓｙ Ｈａｂｎ１０ ０ ， ｈｎ） ｅ ｏＣ Ｓ ｉ ｔ
［ ｂ ｔ ｃ］ ｎ ｒ ｒｏ ｍ ｒｖ ｅ ｉ ｌｉ ｔ ｎｓｅｄ ｆｏ ｉｆｎ ｔ ｎ， ｉ ｐｐ ｒ ｒｐ ｓｓ ｐｏ ｅ — ｍ ｔ ｄ ｏ ｍ ｌｉ ｔ ｎ ｆｏ ｉ Ａ ｓ ａ ｔ Ｉ ｏ ｅ ｔ ｉ ｐｏ ｅｈ ｍｐ ｆ ａ ｏ ｅ ｇ ｃ ｏ ｓｔ ｓ ａｅ ｏ ｏｅ ｉ ｒｖｄ Ｍ ｅ ｏ ｒｉ ｐ ｆ ａ ｏ ｇ ｒ ｄ ｔ ｓ ｉｃ ｉ ｐ ｏ ｌ ｃ ｕ ｉ ｈ ｐ ｎ ａ ｍ Ｑ ｈ ｆ ｓ ｉｃ ｉ ｏ ｌ ｃ
［ ｅ ｏ ｄ ｌｓ ｌ ｃｔ ｎ ｆｏｉ ｆｎ ｔ ｎ； — ｍ ｔ ｄ ｐ ｍ ｐ ｃ ｎ ； ｉ ｒｔ ｇａｈ ｍ ｎ ｕ ｖｒｇ Ｋ ｙ ｒ ｓ ｉ ｉ ａ ｏ ｇ ｃ ｏ ｓＱ Ｍ ｅ ｏ ； ｒ ｅ ｍ ｌ ａ ｔ ｂ ａｔ ｐ ； ｉｉ ｍ ｃ ｅ ｅ ｗ ｍｐ ｆ ｉ ｏ ｌ ｃ ｕ ｉ ｉ ｈ ｉ ｉ ｉ ｓ ｐ ｉ ｒ ｅ ｍ ｏ ａ
第３ ７卷 第 ２ 期 ０
Ｖｌ －７ ０ ３ ｌ
・
计
算
机
工
程
２１ ０ １年 １ ０月
０ ｃｏｂ ｒ ２０１ ｔ ｅ １
Ｎ Ｏ．０ ２
Ｃｏ ｕｔｒＥｎ ｉ ｅ ｒｎｇ ｍｐ ｅ ｇ ｎ ｅ ｉ
软件 技术 与数 据库 ・
‘ 文章一号ｔ ０ ４８ ０１ 一 ３ ３ 文献标识码ｉ ｏ ２（ ｌ） ＿ ０ ｌ ２ ２ ｏ Ａ
ＤＯＩ １ ． ６０ｉ ｎ１０ —４ ８２ １．００ １ ： ０３ ９ ．ｓ ． ０３ ２ ．０ １２ ．１ ９ ｓ ０
ｌ 概述
逻辑 函数化简是数字集成 电路 自动设计的关键 步骤 ，其 目的是使 电路设计最简 、成本最低 。传统的逻辑函数化 筒方 法——Ｑ Ｍ 化简法Ｄ２ ・ －以真值表为基础 ，具有较强的规 律性 ， ］ 但随着逻辑变量数 目的增加 ，迭代 比较的次数 也大大增 加 ， 运行 时间呈指数增长。 献［］ 用链表及树 的结构实现 Ｑ— 文 ３ 使 Ｍ 化简法 ，文献［】 ４采用矩阵代数求解质蕴涵项和最小覆盖 。文 献【］ ５采用十进制数来表示 多维体 ，从复合多维体中选择一对 十进制数 ，通过判别规则来确定质蕴涵项 ，然 后用选择极值
ｆ ｎ ｔ ｎ ． ｅｓｚ ｆｉ ｌ ａ ｔ ｅ ｓｄ ｃ ｅ ｓｄｂｙｕ ｉｇａｐ ｉ ｏ ｉｈｓｉ ｈ ｅ ａｉｎｐ ｏ ｅ ｓｏ ｏ ａｉｏ ｏ ｌ ｅｉ ｐｉａ ｔ ｉｈｓｔｓｙ ｕ ｃｉ ｓ Ｔｈ ｉｅｏ ｏ ｍｐｉ ｎｓｓ ｔ ｅ ｒａ ｅ ｓｎ ａｒ ｆ ｃ ｉ ｗｅｇ ｔ ｎｔｅｉ ｒｔｏ ｒ ｃ ｓ ｆｃ ｍｐ ｒｓ ｎ， ｎｙｔ ｔ ｈ ｍ ｌ ｎ ｓｗｈｃ ａｉｆ ｃ