Simple disjunctive normal forms of Boolean functions with a restricted number of zeros

DOI10.1134/S1064562412040102MaRDI QIDQ1761058zbMATH OpenFDO

Authors Yu. V. Maksimov

Publication date 15 November 2012

Published in Doklady Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S1064562412040102

zbMATH Keywords

Boolean functioncomplexitydisjunctive normal formpattern recognition

Mathematics Subject Classification ID

Boolean functions (06E30) Pattern recognition, speech recognition (68T10)

Review text

From the introduction: ``This paper studies the complexity of disjunctive normal forms (DNFs) of Boolean functions defined by their matrices of zeros. The best available bounds are obtained for the minimum number of conjunctions making up a DNF of a Boolean function with a restricted number of zeros. The results can be used to implement characteristic functions of classes in patterns with binary data.

Recommendations

• Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms
• Comparative analysis of the complexity of Boolean functions with a small number of zeros
• scientific article; zbMATH DE number 3961508
• Implementation of a class of Boolean functions with a small number of zeros by irredundant disjunctive normal forms
• scientific article; zbMATH DE number 4089620

Cites work

• An algorithm for constructing a disjunctive normal form equivalent to the product of the left-hand sides of Nelson Boolean equations
• Disjunctive normal forms of Boolean functions with a small number of zeros

Cited in

(8)

• Implementation of a class of Boolean functions with a small number of zeros by irredundant disjunctive normal forms
• Comparative analysis of the complexity of Boolean functions with a small number of zeros
• scientific article; zbMATH DE number 3961508 (Why is no real title available?)
• scientific article; zbMATH DE number 4053526 (Why is no real title available?)
• Disjunctive normal forms of Boolean functions with a small number of zeros
• Shortest and minimal disjunctive normal forms of complete functions
• scientific article; zbMATH DE number 2205679 (Why is no real title available?)
• Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms

This page was built for publication: Simple disjunctive normal forms of Boolean functions with a restricted number of zeros

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1761058)