Abstract:
The known lower bound for the maximum number of prime implicants (of maximal faces) of a Boolean function differs from the upper bound by $O(\sqrt{n}) $ times and is asymptotically attained on a symmetric belt function. To study the properties of extremal functions, subsets of functions are defined that have the minimum and maximum vertices of the maximum faces in the belts $n/3 \pm {{r}_{n}}$ and $ 2n/3 \pm {{r}_{n}} ,$ respectively. In this case, the fraction of the number of vertices in each layer is not less than $ {{\varepsilon}_{n}} $ and for any such vertex the fraction of the number of maximum faces of the maximum possible number is not less than ${{\varepsilon}_{n}} .$ Conditions are obtained for ${{\varepsilon}_{n}} $ and ${{r}_{n}}$ under which a Boolean function from such a subset has the number of prime implicants equal to the maximum value asymptotically or in order of growth of the maximum value. Bibliogr. 10.
Keywords:Boolean function, prime implicant, maximal face, number of prime implicants, asymptotics, order of growth.
Fulltext:
PDF file (358 kB)