Decomposition of Boolean Relations and Functions in Logic Synthesis and Data Analysis

Document Type



This paper shows that the problem of decomposing a finite function f(A, B) into the form h (g(A), B), where g is a Boolean function, can be resolved in polynomial time, with respect to the size of the problem. It is also shown that omission of the characteristic of the g function can significantly complicate the problem. Such a general problem belongs to the N P-hard class of problems. The work shows how the problem of decomposition of a finite function can be reduced to the problem of coloring the vertices of a graph. It is also shown that the problem of decomposition of relations can be reduced to coloring the vertices of their hypergraphs. In order to prove the validity of the theorems, combinatory properties of Helly are used.


Computer algorithms; Decomposition method


Computer Engineering | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications


Use Find in Your Library, contact the author, or use interlibrary loan to garner a copy of the article. Publisher copyright policy allows author to archive post-print (author’s final manuscript). When post-print is available or publisher policy changes, the article will be deposited