Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

Yu V. Maximov

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)

    Abstract

    The problem of constructing simple disjunctive normal forms (DNFs) of Boolean functions with a small number of zeros is considered. The problem is of interest in the complexity analysis of Boolean functions and in its applications to data analysis. The method used is a further development of the reduction approach to the construction of DNFs of Boolean functions. A key idea of the reduction method is that a Boolean function is represented as a disjunction of Boolean functions with fewer zeros. In a number of practically important cases, this technique makes it possible to considerably reduce the complexity of DNF implementations of Boolean functions.

    Original languageEnglish
    Pages (from-to)1391-1409
    Number of pages19
    JournalComputational Mathematics and Mathematical Physics
    Volume53
    Issue number9
    DOIs
    Publication statusPublished - Sep 2013

    Keywords

    • algebraic classification methods
    • Boolean function
    • complexity of Boolean function
    • disjunctive normal form
    • probably approximately correct learning

    Fingerprint

    Dive into the research topics of 'Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms'. Together they form a unique fingerprint.

    Cite this