Volume 29, No 1, 2022, P. 74-93

UDC 519.71
I. P. Chukhrov
Properties of Boolean functions with the extremal number of prime implicants

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(\surd 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 $\epsilon_n$ and for any such vertex the fraction of the number of maximum faces of the maximum possible number is not less than $\epsilon_n$. Conditions are obtained for $\epsilon_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.

DOI: 10.33048/daio.2022.29.725

Igor P. Chukhrov ¹
1. Institute of Computer Aided Design RAS,
19/18, Vtoraya Brestskaya Street, 123056 Moscow, Russia
e-mail: chip@icad.org.ru

Received September 8, 2021
Revised September 8, 2021
Accepted November 17, 2021

References

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

[2] A. A. Sapozhenko and I. P. Chukhrov, Boolean function minimization in the class of disjunctive normal forms, Itogi Nauki Tekh., Ser. Teor. Veroyatnost., Mat. Statist., Teor. Kibern. 25, 68–116 (1987) [Russian] [J. Sov. Math. 46 (4), 2021–2052 (1989)].

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

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

[5] I. P. Chukhrov, Connected boolean functions with a locally extremal number of prime implicants, Diskretn. Anal. Issled. Oper. 28 (1), 68–94 (2021) [Russian] J. Appl. Ind. Math. 15 (1), 17–38 (2021).

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

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

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

[9] N. Alon and J. H. Spencer, The Probabilistic Method, (Wiley, Hoboken, NJ, 2000; BINOM. Lab. Znanii, Moscow, 2007 [Russian]).

[10] A. V. Kostochka, An upper bound of the cardinality of antichain boundary in the $n$-cube, Diskretn. Mat. 1 (4), 53–61 (1989) [Russian] [Discrete Math. Appl., 1 (3), 279–288 (1991)].