Properties of Boolean Functions with Extremal Number of Prime Implicants

The known lower bound for the maximum number of prime implicants (maximal faces) of a Boolean function differs from the upper bound by a factor of \( O(\sqrt {n}) \) and is asymptotically attained on a symmetric belt function. To study the properties of extremal functions, we define subsets of functions that have the minimum and maximum vertices of the maximal faces in the belts \( n/3 \pm r_n \) and \( 2n/3 \pm r_n \), respectively. Here the fraction of the number of vertices in each layer is at least \( \varepsilon _n \), and for any such vertex the ratio of the number of maximal faces to the maximum possible number is at least \( \varepsilon _n \). Conditions on the parameters \( \varepsilon _n \) and \( r_n \) are obtained under which the number of prime implicants of a Boolean function in such a subset is equal to the maximum value asymptotically or in the order of growth.