Computational Aids for Determining the Minimal Form of a Truth Function

ABSTRACT

The literature concerned with methods for finding the minimal form of a truth function is, by now, quite extensive. This article extends this knowledge by introducing an algorithm whereby all calculations are performed on decimal numbers obtained from binary-decimal conversion of the terms of the Boolean function. Several computational aids are presented for the purpose of adapting this algorithm to the solution of large-scale problems on a digital computer.

REFERENCES

• 1: URBANO, R ~-~ , AND ~V{UELLER, R K A topologlcal method tor the determination of the minimal forms of a Boolean function, IRE Trans , Vol. EC-5, pp 126-132, September, 1956.
• 2: MUELLEa, R K On the synthesis of a minimal representation of a logic function, Cambridge, Mass., Air Force Cambridge Research Center, AFCRC-7R-55-104, April, 1955
• 3: Bernard Harris has suggested one means of representation, whereby the binary digits are interpreted as though they were of Radix three HAums, BERNARD, An algorithm for determining minimal representations of a logic function, {RE Trans , Vol. EC-6, pp 103-108, June, 1957.
• 4: A basic cell corresponds exactly to what Quine calls a "prime implicant" See QUINE, W V, The problem of simplifying truth functions, Amer Math Month. 59 (1952), 521-531.
• 5: CALDWELL, S. H., Sw~tcMng C~rcu~ts and Logical Design, pp. 165-169. John Wiley and Sons, New York.
• 6: McCLVSKEr, E. J., JR, Minimization of Boolean functions, Bell Syslem Tech. J 85 (1956), 1417-1444.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Theory