Geodesic
Properties of Boolean functions with the~extremal number of prime implicants
Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 74-93.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, number of prime implicants, asymptotics, order of growth.
Mots-clés : maximal face 
@article{DA_2022_29_1_a5,
     author = {I. P. Chukhrov},
     title = {Properties of {Boolean} functions with the~extremal number of prime implicants},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {74--93},
     publisher = {mathdoc},
     volume = {29},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2022_29_1_a5/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - Properties of Boolean functions with the~extremal number of prime implicants
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2022
SP  - 74
EP  - 93
VL  - 29
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2022_29_1_a5/
LA  - ru
ID  - DA_2022_29_1_a5
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T Properties of Boolean functions with the~extremal number of prime implicants
%J Diskretnyj analiz i issledovanie operacij
%D 2022
%P 74-93
%V 29
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2022_29_1_a5/
%G ru
%F DA_2022_29_1_a5
I. P. Chukhrov. Properties of Boolean functions with the~extremal number of prime implicants. Diskretnyj analiz i issledovanie operacij, Tome 29 (2022) no. 1, pp. 74-93. http://geodesic.mathdoc.fr/item/DA_2022_29_1_a5/

[1] Yu. L. Vasil'ev, V. V. Glagolev, “Metric properties of disjunctive normal forms”, Discrete Mathematics and Mathematical Problems of Cybernetics, Nauka, M., 1974, 99–148 (Russian)

[2] A. A. Sapozhenko, I. P. Chukhrov, “Boolean function minimization in the class of disjunctive normal forms”, J. Sov. Math., 46:4 (1989), 2021–2052

[3] A. P. Vikulin, “Estimation of the number of conjunctions in the complete DNF”, Problems of Cybernetics, 29, Nauka, M., 1974, 151–166 (Russian)

[4] Chandra A. K., Markovsky G., “On the number of prime implicants”, Discrete Math., 24 (1978), 7–11

[5] I. P. Chukhrov, “Connected boolean functions with a locally extremal number of prime implicants”, J. Appl. Ind. Math., 15:1 (2021), 17–38

[6] G. P. Gavrilov, A. A. Sapozhenko, Tasks and Exercises in Discrete Mathematics, Fizmatlit, M., 2005 (Russian)

[7] A. A. Borovkov, Probability Theory, Editorial URSS, M., 1999 (Russian)

[8] I. P. Chukhrov, “About the maximum cardinality of the shadow of an antichain”, Diskretn. Mat., 1:4 (1989), 78–85 (Russian)

[9] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley, Hoboken, NJ, 2000

[10] A. V. Kostochka, “An upper bound of the cardinality of antichain boundary in the $n$-cube”, Discrete Math. Appl., 1:3 (1991), 279–288