Some Methods for Simplifying Switching Circuits Using “Don't Care” Conditions
- 1 October 1961
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 8 (4), 497-512
- https://doi.org/10.1145/321088.321092
Abstract
Several methods for simplifying switching circuits using “don't-care” conditions are suggested. One of the methods uses the following procedure: Let the given circuit be represented by the truth function F . Let the given “don't-care” conditions be denoted by D = 0. (For example, if x 1 = 1 and x 2 = 0 represent the combination of input signals which never takes place, then D = x 1 x 2 .) Generate all the irredundant disjunctive and conjunctive forms which are equivalent to F whenever D = 0. From these forms, the simplest ones may then be chosen according to a given measure of simplicity. They correspond to the simplest two-level AND/OR or OR/AND switching circuits which, under the “don't-care” conditions, perform the same function as the given circuit. Several methods for generating the equivalent irredundant forms are suggested. They are generalizations of those due to Quine, Ghazala and Mott, and may be programmed for use on computers. Alternative simplification methods are also given.Keywords
This publication has 7 references indexed in Scilit:
- Algebraic Topological Methods for the Synthesis of Switching Systems—Part III: Minimization of Nonsingular Boolean TreesIBM Journal of Research and Development, 1959
- Absolute Minimal Expressions of Boolean FunctionsIEEE Transactions on Electronic Computers, 1959
- Algebraic topological methods for the synthesis of switching systems. ITransactions of the American Mathematical Society, 1958
- Minimization of Boolean Functions*Bell System Technical Journal, 1956
- A Way to Simplify Truth FunctionsThe American Mathematical Monthly, 1955
- Weak simplest normal truth functionsThe Journal of Symbolic Logic, 1955
- The Problem of Simplifying Truth FunctionsThe American Mathematical Monthly, 1952