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

为进一步提高逻辑函数的化简速度,提出一种改进的Q-M逻辑函数化简方法。在迭代比较过程中设置2个权值以缩减可合并蕴涵项集合的大小,只对满足条件的蕴涵项进行合并处理,得到全部质蕴涵项。构造质蕴涵项与最小项关联图,利用启发式规则得到能蕴涵全部最小项的最少质蕴涵项集合,从而得到逻辑函数的最小覆盖,完成逻辑函数化简。实验结果表明,该算法能降低迭代次数,减少逻辑函数的化简时间。     

Simplification of Switching Functions Involving a very Large Number of ‘Don't Care’ States†

A method of simplification of switching functions involving a very large number of ‘ don't care’ states is suggested in the present paper. First a tabular technique is suggested which generates all the prime implicants starting from the maxterm type expressions of switching functions, avoiding generation of the prime implicants formed of ‘don't care’ states only. The technique presented is simple and iterative. Next it is suggested how the knowledge of the sets of prime implicants thus obtained can be utilized for finding minimal or other irredundant sums of switching functions.     

Computing prime implicants via transversal clauses

In this paper, the notion of transversal clauses is introduced and subsequently a new algorithm for computing prime implicants is developed. Opposed to the common approach of computing prime implicants of a dnf, the proposed algorithm uses a cnf representation of a propositional formula. The same algorithm applied on a dnf representation yields the set of prime implicates of a formula. Besides its suitability for implementation in a parallel environment and as an incremental algorithm, it has been found to work faster in case, the number of prime implicants is large.     

Nombre moyen de majorants d'une fonction booléenne incomplète Remarques concernant le nombre moyen de monômes premiers

The preliminary computation of the «majorants» enables the determination of the minimal or quasi-minimal disjunctive irredundant forms of an incompletely specified function [3]. In practical cases, the search algorithm for the disjunctive irredundant forms is applicable only if the number of «majorants» is not too large. In this paper formulas are derived to determine the average value of this number. Then the computation of the average number of prime implicants, already given byMileto andPutzolu [4], is rederived in a new form. The result is used to built functions having a great number of prime implicants and yields, for a function ofn variables, a lower bound of the maximal number of prime implicants.     

Useless prime implicants of incompletely specified multiple-output switching functions

In the process of finding a minimal sum representation for an incompletely specified multiple-output switching function, there often occur certain types of prime implicants, referred to as useless, which can be discarded because of the presence of the don't-cares. This paper presents a correction to the definition of useless given by Tison and extends the definition to other notations. A procedure for removing useless prime implicants quickly is presented for the case when multiple-output prime implicants are derived from minterms. The deletion of useless prime implicants can, in many cases, speed up any procedure for finding a minimal sum that begins with the multiple-output prime implicants in both hand calculation and in computer implementation.This work was supported in part by the National Science Foundation under Grant No. MCS-77-09744.     

On Graphical Studies of PEN-IM Sets of Boolean Functions and their Minimizations. Part I†

The graphs of the sets of all penultimate implicants of certain types of Boolean functions are obtained in this part of the paper. Identification of different C.H. Boolean functions with their graphs are then made and terms are coined to designate these functions for the easy pattern recognition of their graphs. Finally formulae are deduced which give the number of prime implicants that must be present in any minimal cover of these functions.     

Bases for closed sets of implicants and implicates in temporal logic

Prime implicates and implicants are used in several areas of Artificial Intelligence. However, their calculation is not always an easy task. Nevertheless, it is important to remark the distinction between (i) computing the prime implicates and implicants and (ii) using the information they contain. In this paper, we present a way in which (ii) can be done without actually doing (i) by limiting prime implicants and implicates management to unitary implicants and implicates. Besides, we outline how the use of this technique is particularly relevant in the field of automated deduction in temporal logics. The information contained in temporal implicates and implicants can be used to design transformations of temporal formulae able to increase the power of automated deduction techniques for temporal logics. Particularly, we have developed a theory for unitary temporal implicates and implicants that can be more efficiently computed than prime implicants, while still providing the information needed to design this kind of transformations. The theory we have developed in this paper is easily extensible to cover different types of temporal logics, and is integrable in different automated deduction methods for these temporal logics. Received: 14 May 1999 / 22 March 2002     

A method of finding simple disjunctive decomposition with one free variable

Simple disjunctive decomposition with one free variable can be obtained by using the prime implicants of the Boolean function. A function is decomposable with its redundant variable as a free variable. A necessary condition for decomposition with a non-redundant variable as free variable is that the number of minterms in an n variable function be 2^(n?1). A sufficient condition is that the variable remain present, in either true or complemented form, in all the prime implicants of the function.     

Simplification of fuzzy switching functions

This paper is concerned with the study of simplification of fuzzy switching functions. A novel algorithm for generating all fuzzy prime implicants is introduced, followed by a new method of simplification of fuzzy switching functions. This algorithm is then reduced to a simple algorithm that produces only those fuzzy prime implicants that are essential. There areonly two other valid techniques for the minimization of fuzzy switching functions in the literature,^(1,2) and those methods are not very suitable for computerized application. Thus, the principal advantages of this technique are the new concept of direct simplification via essential fuzzy prime implicants (without generation of all of the fuzzy prime implicants), and the fact that the algorithm is the first one to be suitable for efficient computer implementation.On leave from the Computer Science Department, New Mexico Institute of Mining and Technology, Socorro, New Mexico.     

关于实质本源蕴涵项的识别问题

本文揭示ＥＳＰＲＥＳＳＯ算法和Ｍｕｒｏｇａ等提出的求绝对最小算法中识别实质本源蕴涵项的方法具有近似的复杂度。文中还给出了一个在产生本源蕴涵项过程中识别实质本源项的算法。     

A minimization method for boolean functions

Algorithms are proposed for constructing one and all prime implicants covering a given point, a DNF consisting of prime implicants, and a reduced DNF. The complexity of the proposed algorithms is investigated.Translted from Kibernetika, No. 5, pp. 44–48, September–October, 1989.     

An Efficient Algorithm to Generate Prime Implicants

In this paper, an efficient recursive algorithm is presented to compute the set of prime implicants of a propositional formula in conjunctive normal form (CNF). The propositional formula is represented as a (0,1)-matrix, and a set of 1's across its columns are termed as paths. The algorithm finds the prime implicants as the prime paths in the matrix using the divide-and-conquer technique. The algorithm is based on the principle that the prime implicant of a formula is the concatenation of the prime implicants of two of its subformulae. The set of prime paths containing a specific literal and devoid of a literal are characterized. Based on this characterization, the formula is recursively divided into subformulae to employ the divide-and-conquer paradigm. The prime paths of the subformulae are then concatenated to obtain the prime paths of the formula. In this process, the number of subsumption operations is reduced. It is also shown that the earlier algorithm based on prime paths has some avoidable computations that the proposed algorithm avoids. Besides being more efficient, the proposed algorithm has the additional advantage of being suitable for the incremental method, without recomputing prime paths for the updated formula. The subsumption operation is one of the crucial operations for any such algorithms, and it is shown that the number of subsumption operation is reduced in the proposed algorithm. Experimental results are presented to substantiate that the proposed algorithm is more efficient than the existing algorithms.     

On the number of core coverable switching functions

Summary The results of an experimental determination of the number of switching functions covered by essential prime implicants are reported. Switching functions of 5, 6, 7, 8, 9 variables have been investigated.     

支持大规模变量集的最小覆盖迭代搜索算法

两级逻辑综合中的多输出逻辑电路最小覆盖的求解是一个NP难解问题,在输出变量集合和质蕴含项集合规模较大的情况下,会出现空间需求过大、处理时间太长等问题,影响多输出最小覆盖求解的可行性．在精选法的基础上,提出一种多输出最小覆盖迭代求解算法．将一次性求解最小覆盖的模式转换为多次迭代逼近最优解的过程,使得在有限的时间和空间范围内获得尽可能优化的最小覆盖结果．同时,对影响算法复杂度的单输出到多输出函数的阵列合并、极值的选择这2个主要环节进行了改进,大幅度降低了多输出最小覆盖求解算法的时间和空间复杂度．     

CNF and DNF Considered Harmful for Computing Prime Implicants/Implicates

Several methods to compute the prime implicants and the prime implicates of a negation normal form (NNF) formula are developed and implemented. An algorithm PI is introduced that is an extension to negation normal form of an algorithm given by Jackson and Pais. A correctness proof of the PI algorithm is given. The PI algorithm alone is sufficient in a computational sense. However, it can be combined with path dissolution, and it is shown empirically that this is often an advantage. None of these variations rely on conjunctive normal form or on disjunctive normal form. A class of formulas is described for which reliance on CNF or on DNF results in an exponential increase in the time required to compute prime implicants/implicates. The possibility of avoiding this problem with efficient structure preserving clause form translations is examined briefly and appears unfavorable.     

The use of linear programming to select an optimal set of prime implicants

This study shows how the selection of an optimal subset of prime implicants from a prime implicant table, as encountered in digital logic design and similar applications, may be formulated as a linear programming problem in zero-one variables.     

基于一致性的中心诊断及中心溯因诊断

本文对溯因诊断的过程和中心溯因诊断的过程进行了刻画。将求中心溯因诊断的过程清晰地分为与领域有关的冲突识别及与领域无关的候选产生两大步骤。不仅指出了基于一致性的中心诊断与中心溯因诊断之间的关系，而且论证了中心溯因诊断与本原蕴含／蕴含式的直接关系。显示出基于一致性的中心诊断空间和中心溯因诊断空间不仅可同时计算，而且可用ＡＴＭＳ这类算法来计算，从而将我们的理论结果与实现联系起来。     

On a convenient division of labor in the generation of prime implicants

A procedure is presented for constructing the Blake canonical form for a switching function (the sum of all its prime implicants) conveniently and rapidly. This procedure combines Blake's method (iterated consensus) with the multiplying method of Samson and Mills.     

刻画基于模型的中心诊断*

虽然对基于模型的诊断存在一系列不同的逻辑定义,但所幸的是存在一个统一的抽象定义,它概括了以往的不同定义.在该定义基础上提出了基于模型的中心诊断的概念.通过刻画基于模型的中心诊断过程,论证了基于模型的中心诊断与本原蕴含/蕴含式的直接关系,从而将其理论结果与ATMS(assumption-based truth maintenance system)这类算法联系起来.进一步指出,对基于一致性中心诊断的刻画仅仅是文中所给出的刻画的一个特殊情形.