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.     

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

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

A Note on the Simplification of Fuzzy Switching Functions

Abstract

This note is concerned with the modification of the definition of fuzzy consensus. The modified version is used to find the set of all fuzzy prime implicants of a fuzzy switching function as defined in [1]. The fuzzy algebra used to derive these functions satisfies the set of axioms of a distributive lattice with unique identities under the operators of maximum and minimum as described in [5], [4], and [3].     

A note on the simplification of fuzzy switching functions

This note is concerned with the modification of the definition of fuzzy consensus. The modified version is used to find the set of all fuzzy prime implicants of a fuzzy switching function as defined previously. The fuzzy algebra used to derive these functions satisfies the set of axioms of a distributive lattice with unique identities under the operators of maximum and minimum as described earlier.     

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.     

Some Further Studies on Determination of all the Minimal Prime Implicant Covers of Switching Functions†

A method of determination of all the minimal prime implicant covers of switching functions by utilizing their connected cover term matrices is suggested in the paper. The method presented is an extension of the technique suggested by the authors in a previous paper (Choudhury and Das 1964). When majority of the prime implicants of a switching function will occur in more than two different columns of the cover table, it is shown that the determination of all the minimal prime implicant covers can often be greatly facilitated by initially dividing the cover table into more than two suitable sub-tables.     

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.     

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.     

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.     

Two-Level Multiple-Output Logic Minimization Using A Single Function

A new method for obtaining a two-level collective minimal cover for a set of incompletely-specified switching functions $S=\{f_1,f_2,\ldots,f_n\}$ is presented. The method relies on the introduction of a single auxiliary function F whose subfunctions (restrictions) with respect to some additional auxiliary variables $y_1,y_2,\ldots,y_{n-1}$ are certain members of S . The complete sum of F has full information on the multiple-output prime implicants (MOPIs) of the set of functions S . A particularly constrained minimal cover for F contains only labeled versions of some paramount prime implicants (PPIs) of S and can be used to construct a multiple-output minimal cover for S . The present method can proceed by map, algebraic or tabular techniques, though only the map version is presented herein. This version employs a single map whose construction avoids the ANDing operations needed in the classical method, and whose size is almost one half the total size of the maps used by the classical method, and whose entries can be variable as well as constant. The minimization process is a direct two-step technique that avoids constructing the set of all PPIs as it produces only these PPIs needed in the minimal cover. Details of the method are carefully explained and illustrated via a typical example.     

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.     

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.     

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.     

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

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

Applications of fuzzy algebra to hazard detection in combinational switching circuits

This paper presents some theoretical considerations for the detection of hazards in combinational switching systems. The application of fuzzy models to hazard detection in binary systems is discussed, and this leads to methods of detection for multiple zero and one hazards. Finally, a method for theorem proving applicable to the detection method is presented.On leave from the Computer Science Department, New Mexico, Institute of Mining and Technology, Socorro, New Mexico.     

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.     

Minimization of Boolean functions of any number of variables using decimal labels

This paper deals with the problem of minimization of a Boolean function, particularly when the number of variables is very large. Using the decimal labels of the minterms, a table is worked out which helps to determine all the prime implicants and the essential prime implicants. A systematic method of sorting out the dominating and the dominated columns is then given, which helps to reduce the number of successive cover tables considerably.     

模糊相容图

本文提出了模糊开关函数极小化的新方法,建立了一种模糊相容图,用它求函数的极小覆 盖,既不用模糊本原蕴含总集,也不要分解短语,可有效地用于多变量函数的模糊逻辑开关系 统或连续逻辑开关系统的设计.