Open AccessMethods of decomposition of Boolean functions
Author(s) -
N I Gdanskiy,
A.A. Denisov,
M L Rysin
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/862/4/042026
Subject(s) - decomposition , boolean function , computer science , minification , decomposition method (queueing theory) , hypergraph , theoretical computer science , mathematics , algorithm , discrete mathematics , programming language , ecology , biology
The article considers on of the main types of Boolean functions conversion – their decomposition. The decomposition is being used in many applications for studying and designing complex objects and systems with logical methods. Firstly, the article observes decomposition of Boolean functions represented in the truth table. Among traditional decomposition approaches, the article describes formulas presented by Boole and Shannon and special methods of orthonormal expansions. Then, the paper considers contemporary decomposition techniques and their classification. Next, the article discusses representation of Boolean functions in normal forms and essential features of that representation, important for decomposition. After that, the article reviews decomposition techniques for boolean functions represented in conjunctive normal forms (CNF). The study mentions CNF partitioning as hypergraph partitioning. Then the paper discusses applications generating large CNFs. Minimization of large CNFs with traditional methods is impossible. Their minimization is possible only using decomposition techniques. The separate class of tasks is minimization of Horn formulas. Finally, at the conclusion, the study discusses decomposition for parallelization of SAT problem.