You are here: Home :: Area NEM :: Mathematics

K. D. Kirichenko

An upper bound for complexity of polynomial normal forms of Boolean functions

We consider the problem of minimisation of Boolean functions in the class of polynomial normal forms. We suggest an algorithm for constructing polynomial normal forms for arbitrary Boolean functions such that the length of the obtained formula depends on the number of variables of the function only. As the input of the algorithm, along with the function, we take the solution of a covering problem. The number of elementary conjunctions in the obtained formula is equal to the cardinality of the covering. For the introduced covering problem we find an approximate solution. We succeed to prove that the complexity of Boolean functions in the class of polynomial normal forms is less than 2ⁿ⁺¹(log₂ n + 1)/n, which allows us to conclude that for almost any Boolean function the complexity of its representation in the polynomial normal form is less than its representation in the disjunctive normal form.

Discrete Mathematics and Applications, Walter de Gruyter

Print ISSN: 0924-9266
Volume: 15, 05/2005
Pages: 351 - 360

Show full article (external site)

Show all available items of this journal

 

Area NEM