Shortest and minimal disjunctive normal forms of complete functions

Yu V. Maximov

    Research output: Contribution to journalArticlepeer-review


    It was previously established that almost every Boolean function of n variables with k zeros, where k is at most log2n–log2log2n + 1, can be associated with a Boolean function of 2k–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.

    Original languageEnglish
    Pages (from-to)1242-1255
    Number of pages14
    JournalComputational Mathematics and Mathematical Physics
    Issue number7
    Publication statusPublished - 27 Jul 2015


    • Boolean function
    • complexity of implementing Boolean functions by disjunctive normal forms
    • disjunctive normal form


    Dive into the research topics of 'Shortest and minimal disjunctive normal forms of complete functions'. Together they form a unique fingerprint.

    Cite this