|
Properties of Boolean functions with the extremal number of prime implicants
I. P. Chukhrov Institute of Computer Aided Design RAS, 19/18, Vtoraya Brestskaya Street, 123056 Moscow, Russia
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(\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, maximal face, number of prime implicants, asymptotics, order of growth.
Received: 08.09.2021 Revised: 08.09.2021 Accepted: 17.11.2021
Citation:
I. P. Chukhrov, “Properties of Boolean functions with the extremal number of prime implicants”, Diskretn. Anal. Issled. Oper., 29:1 (2022), 74–93
Linking options:
https://www.mathnet.ru/eng/da1294 https://www.mathnet.ru/eng/da/v29/i1/p74
|
Statistics & downloads: |
Abstract page: | 167 | Full-text PDF : | 26 | References: | 60 | First page: | 7 |
|