Geodesic
Connected Boolean functions with a locally extremal number of prime implicants
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 68-96.

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

The well-known lower bound for the maximum number of prime implicants of a Boolean function (the length of the reduced DNF) differs by $\Theta(\sqrt{n})$ times from the upper bound and is asymptotically attained at a symmetric belt function with belt width $n/3$. To study the properties of connected Boolean functions with many prime implicants, we introduce the notion of a locally extremal function in a certain neighborhood in terms of the number of prime implicants. Some estimates are obtained for the change in the number of prime implicants as the values of the belt function range over a $d$-neighborhood. We prove that the belt function for which the belt width and the number of the lower layer of unit vertices are asymptotically equal to $n/3$ is locally extremal in some neighborhood for $d \le \Theta(n)$ and not locally extremal if $d \ge 2^{\Theta(n)}$. A similar statement is true for the functions that have prime implicants of different ranks. The local extremality property is preserved after applying some transformation to the Boolean function that preserves the distance between the vertices of the unit cube. Bibliogr. 10.
Keywords: Boolean function, connected function, prime implicant, the number of prime implicants, local extremum.
Mots-clés : maximum face 
@article{DA_2021_28_1_a3,
     author = {I. P. Chukhrov},
     title = {Connected {Boolean} functions with a locally extremal number of prime implicants},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {68--96},
     publisher = {mathdoc},
     volume = {28},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_1_a3/}
}
TY  - JOUR
AU  - I. P. Chukhrov
TI  - Connected Boolean functions with a locally extremal number of prime implicants
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 68
EP  - 96
VL  - 28
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_1_a3/
LA  - ru
ID  - DA_2021_28_1_a3
ER  - 
%0 Journal Article
%A I. P. Chukhrov
%T Connected Boolean functions with a locally extremal number of prime implicants
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 68-96
%V 28
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_1_a3/
%G ru
%F DA_2021_28_1_a3
I. P. Chukhrov. Connected Boolean functions with a locally extremal number of prime implicants. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 1, pp. 68-96. http://geodesic.mathdoc.fr/item/DA_2021_28_1_a3/

[1] Yu. L. Vasil'ev, V. V. Glagolev, “Metric properties of disjunctive normal forms”, Discrete Mathematics and Mathematical Problems of Cybernetics, v. 1, 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 | DOI | MR | Zbl | Zbl

[3] M. M. Gadzhiev, “Maximum length of abbreviated DNF for Boolean functions of five and six variables”, Discrete Analysis, 18, Izd. Inst. Mat., Novosibirsk, 1971, 3–24 (Russian)

[4] A. P. Vikulin, “Estimation of the number of conjunctions in the abbreviated DNF”, Cybernetics Problems, 29, Nauka, M., 1971, 151–166 (Russian) | MR | Zbl

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

[6] A. E. Andreev, “On the problem of minimizing disjunctive normal forms”, Dokl. Akad. Nauk SSSR, 274:2 (1984), 265–269 (Russian) | MR | Zbl

[7] Kettle N., King A., Strzemecki T., “Widening ROBDDs with prime implicants”, Tools and Algorithms for the Construction and Analysis of Systems, Proc. 12th Int. Conf. (Vienna, Austria, Mar. 25–Apr. 2, 2006), Lect. Notes Comput. Sci., 3920, Springer, Heidelberg, 2006, 105–119 | DOI | Zbl

[8] Sloan R. H., Szörenyi B., Turan G., “On $k$-term DNF with the largest number of prime implicants”, SIAM J. Discrete Math., 21:4 (2008), 987–998 | DOI | MR

[9] Talebanfard N., “On the structure and the number of prime implicants of 2-CNFs”, Discrete Appl. Math., 200 (2016), 1–4 | DOI | MR | Zbl

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