Properties of Boolean functions with the~extremal number of prime implicants

I. P. Chukhrov

Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 74-93

Résumé

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.

Détail

Keywords: Boolean function, prime implicant, number of prime implicants, asymptotics, order of growth.
Mots-clés : maximal face