References

mais

Моделирование и анализ информационных систем

Modeling and Analysis of Information Systems

1818-10152313-5417

Yaroslavl State University

10.18255/1818-1015-2025-2-100-109

mais-1935

Research Article

Discrete Mathematics in Relation to Computer Science

Об экстремальных элементах и мощности множества непрерывно дифференцируемых выпуклых продолжений булевой функции

On extremal elements and the cardinality of the set of continuously differentiable convex extensions of a Boolean function

https://orcid.org/0000-0001-5047-7710

Баротов

Достонжон Нумонжонович

Barotov

Dostonjon N.

DNBarotov@fa.ru

https://orcid.org/0000-0003-3729-6143

Баротов

Рузибой Нумонжонович

Barotov

Ruziboy N.

DNBarotov@fa.ru

Финансовый университет при Правительстве Российской ФедерацииРоссияFinancial University under the Government of the Russian FederationRussian Federation

Худжандский государственный университет имени академика Б. ГафуроваРоссияKhujand State University named after academician Bobojon GafurovRussian Federation

2025

28062025

322100109

2025

Баротов Д.Н., Баротов Р.Н.

Barotov D.N., Barotov R.N.

Данная работа распространяется под лицензией Creative Commons Attribution 4.0.

This work is licensed under a Creative Commons Attribution 4.0 License.

https://www.mais-journal.ru/jour/article/view/1935

В данной статье изучается существование максимального и минимального элементов множества непрерывно дифференцируемых выпуклых продолжений на $[0,1]^n$ произвольной булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$ и мощность множества непрерывно дифференцируемых выпуклых продолжений на $[0,1]^n$ булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$. В результате исследования установлено, что мощность множества непрерывно дифференцируемых выпуклых продолжений на $[0,1]^n$ произвольной булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$ равна континууму. Аргументировано, что для любой булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$ среди её непрерывно дифференцируемых выпуклых продолжений на $[0,1]^n$ нет минимального элемента. Доказано, что для любой булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$ множество её непрерывно дифференцируемых выпуклых продолжений на $[0,1]^n$ имеет максимальный элемент лишь тогда, когда количество существенных переменных данной булевой функции $f_{B}(x_1,x_2,\ldots,x_n)$ меньше 2.

In this paper we study the existence of the maximal and minimal elements of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ and the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of the Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$. As a result of the study, it was established that the cardinality of the set of continuously differentiable convex extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is equal to the continuum. It is argued that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, there is no minimal element among its continuously differentiable convex extensions to $[0,1]^n$. It is proved that for any Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$, the set of its continuously differentiable convex extensions to $[0,1]^n$ has a maximal element only if the number of essential variables of the given Boolean function $f_{B}(x_1,x_2,\ldots,x_n)$ is less than 2.

непрерывно дифференцируемое выпуклое продолжение булевой функцииэкстремальные элементы множествамощность множества

continuously differentiable convex extension of a Boolean functionextremal elements of a setcardinality of a set

References1

A. H. Abdel-Gawad, A. F. Atiya, and N. M. Darwish, “Solution of systems of Boolean equations via the integer domain,” Information Sciences, vol. 180, no. 2, pp. 288–300, 2010, doi: 10.1016/j.ins.2009.09.010.

G. V. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. University of Maryland, College Park, 2007.

V. K. Leontiev and E. N. Gordeev, “On the number of solutions to a system of Boolean equations,” Automation and Remote Control, vol. 82, pp. 1581–1596, 2021, doi: 10.1134/S000511792109006X.

E. Ishchukova, E. Maro, and P. Pristalov, “Algebraic analysis of a simplified encryption algorithm GOST R 34.12-2015,” Computation, vol. 8, no. 2, p. 51, 2020, doi: 10.3390/computation8020051.

A. I. Pakhomchik, V. V. Voloshinov, V. M. Vinokur, and G. B. Lesovik, “Converting of Boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis,” Algorithms, vol. 15, no. 2, p. 33, 2022, doi: 10.3390/a15020033.

S. Ramos-Calderer et al., “Solving systems of Boolean multivariate equations with quantum annealing,” Physical Review Research, vol. 4, no. 1, p. 013096, 2022, doi: 10.1103/PhysRevResearch.4.013096.

E. Burek, M. Wro'nski, K. Ma'nk, and M. Misztal, “Algebraic attacks on block ciphers using quantum annealing,” IEEE Transactions on Emerging Topics in Computing, vol. 10, no. 2, pp. 678–689, 2022, doi: 10.1109/TETC.2022.3143152.

J. Gu, “Global optimization for satisfiability (SAT) problem,” IEEE Transactions on Knowledge and Data Engineering, vol. 6, no. 3, pp. 361–381, 1994, doi: 10.1109/69.334864.

D. N. Barotov and R. N. Barotov, “Polylinear continuations of some discrete functions and an algorithm for finding them,” Numerical methods and programming, vol. 24, no. 1, pp. 10–23, 2023, doi: 10.26089/NumMet.v24r102.

R. T. Faizullin, V. I. Dulkeyt, and Y. Y. Ogorodnikov, “Hybrid method for the approximate solution of the 3-satisfiability problem associated with the factorization problem,” Trudy Instituta Matematiki i Mekhaniki UrO RAN, vol. 19, no. 2, pp. 285–294, 2013.

D. N. Barotov and R. N. Barotov, “Construction of smooth convex extensions of Boolean functions,” Russian Universities Reports. Mathematics, vol. 29, no. 145, pp. 20–28, 2024, doi: 10.20310/2686-9667-2024-29-145-20-28.

D. N. Barotov, “Convex continuation of a Boolean function and its applications,” Journal of Applied and Industrial Mathematics, vol. 18, no. 1, pp. 1–9, 2024, doi: 10.1134/S1990478924010010.

D. N. Barotov, “On the Existence and Properties of Convex Extensions of Boolean Functions,” Mathematical Notes, vol. 115, no. 3, pp. 489–505, 2024, doi: 10.1134/S0001434624030210.

D. N. Barotov, “Concave continuations of Boolean functions and some of their properties and applications,” Bulletin of Irkutsk State University. Series Mathematics, vol. 49, pp. 105–123, 2024, doi: 10.26516/1997-7670.2024.49.105.

D. N. Barotov and V. A. Sudakov, “On inequalities between convex, concave, and multilinear continuations of Boolean functions,” Keldysh Institute preprints, no. 30, pp. 1–13, 2024, doi: 10.20948/prepr-2024-30.

A. Salomaa, “On essential variables of functions, especially in the algebra of logic,” Annales Fennici Mathematici, no. 339, pp. 1–11, 1964, doi: 10.5186/aasfm.1964.339.

Y. Y. Breitbart, “Essential variables of functions of the algebra of logic,” Doklady Akademii Nauk, vol. 172, no. 1, pp. 9–10, 1967.

D. N. Barotov, “Convex continuations of some discrete functions,” Journal of Applied and Industrial Mathematics, vol. 18, no. 3, pp. 412–423, 2024, doi: 10.1134/S1990478924030049.

D. N. Barotov, “Concave Continuations of Boolean-like Functions and Some of Their Properties,” Bulletin of Irkutsk State University. Series Mathematics, vol. 51, pp. 82–100, 2025, doi: 10.26516/1997-7670.2025.51.82.

The authors declare that there are no conflicts of interest present.