Abstract:
The survey focuses on minimization of boolean functions in the class of disjunctive normal forms (d.n.f.s) and covers the publications from 1953 to 1986. The main emphasis is on the mathematical direction of research in boolean function minimization: bounds of parameters of boolean functions and algorithmic difficulties of minimal d.n.f. synthesis). The survey also presents a classification of minimization algorithms and gives some examples of minimization heuristics with their efficiency bounds.