Об экстремальных элементах и мощности множества непрерывно дифференцируемых выпуклых продолжений булевой функции
https://doi.org/10.18255/1818-1015-2025-2-100-109
Аннотация
В данной статье изучается существование максимального и минимального элементов множества непрерывно дифференцируемых выпуклых продолжений на $[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.
Об авторах
Достонжон Нумонжонович Баротов
Финансовый университет при Правительстве Российской Федерации
Россия
Россия
Рузибой Нумонжонович Баротов
Худжандский государственный университет имени академика Б. Гафурова
Россия
Россия
Список литературы
1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
8. 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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. Y. Y. Breitbart, “Essential variables of functions of the algebra of logic,” Doklady Akademii Nauk, vol. 172, no. 1, pp. 9–10, 1967.
18. 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.
19. 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.
Рецензия
Для цитирования:
Баротов Д.Н., Баротов Р.Н. Об экстремальных элементах и мощности множества непрерывно дифференцируемых выпуклых продолжений булевой функции. Моделирование и анализ информационных систем. 2025;32(2):100-109. https://doi.org/10.18255/1818-1015-2025-2-100-109
For citation:
Barotov D.N., Barotov R.N. On extremal elements and the cardinality of the set of continuously differentiable convex extensions of a Boolean function. Modeling and Analysis of Information Systems. 2025;32(2):100-109. (In Russ.) https://doi.org/10.18255/1818-1015-2025-2-100-109
Просмотров:
21
Послать статью по эл. почте 