ON THE THEORY OF BOOLEAN FORMULAS: SHORTEST AND PRIME FORMULAS.

Abstract

The notion of prime implicant is defined and studied at a high level of generality. All the usual results are preserved and deepened and some new ones obtained. Paramount are those relating prime implicants and shortest sums. This theoretical development may be applied to the minimization of Boolean formulas built from formulas of an arbitrarily given set S (for example, the set of formulas realized by devices of a particular kind) and representing a given incomplete switching function. Several computational processes are briefly discussed. The general theory is supplemented by results particular to the 'classical' case in which S is the set of the products of literals. (Author)

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1966
Accession Number
AD0631074

Entities

People

  • E. W. Samson
  • L. Calabi

Organizations

  • Air Force Cambridge Research Laboratories

Tags

DTIC Thesaurus Topics

  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Computational Processes
  • Computing-Related Activities
  • Cooperation
  • Group Dynamics
  • Switching

Fields of Study

  • Mathematics

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Calculus or Mathematical Analysis