Shortest and minimal disjunctive normal forms of complete functions

摘要

It was previously established that almost every Boolean function of n variables with k zeros, where k is at most log(2) n-log(2)log(2) n + 1, can be associated with a Boolean function of 2 (k-1)-1 variables with k zeros (complete function) such that the complexity of implementing the original function in the class of disjunctive normal forms is determined only by the complexity of implementing the complete function. An asymptotically tight bound is obtained for the minimum possible number of literals contained in the disjunctive normal forms of the complete function.