УДК 519.716.32, 517.518.244, 512.563
MSC: 03B50, 54C20, 26B25, 06E30
DOI: 10.21538/0134-4889-2025-31-4-52-61
В настоящей статье исследуется существование и единственность вогнутого продолжения на отрезок $[0,k-1]$ произвольной унарной функции $k$-значной логики $f_{L}\colon\{0,1,\ldots,k-1\}\to\{0,1,\ldots,k-1\}$ при любом натуральном $k \geq 2$. В результате исследования для произвольного натурального $k \geq 2$ формулируется и доказывается критерий существования вогнутого продолжения унарной функции $k$-значной логики $f_{L}$. Доказывается, что найденный критерий существования вогнутого продолжения функции $k$-значной логики $f_{L}$ является также критерием существования минимального вогнутого продолжения функции $k$-значной логики $f_{L}$, но не является достаточным условием единственности вогнутого продолжения функции $k$-значной логики $f_{L}$. Также находится и доказывается критерий единственности вогнутого продолжения произвольной унарной функции $k$-значной логики $f_{L}$.
Ключевые слова: функция $k$-значной логики, вогнутое продолжение функции $k$-значной логики, критерий существования и единственности вогнутого продолжения
СПИСОК ЛИТЕРАТУРЫ
1. Баротов Д.Н. Вогнутые продолжения булевых функций и некоторые их свойства и приложения // Изв. Иркут. гос. ун-та. Серия: Математика. 2024. Т. 49. С. 105–123. https://doi.org/10.26516/1997-7670.2024.49.105
2. Abdel-Gawad A.H., Atiya A.F., Darwish N.M. Solution of systems of Boolean equations via the integer domain // Inf. Sci. 2010. Vol. 180, no. 2. P. 288–300. https://doi.org/10.1016/j.ins.2009.09.010
3. Gu J. On optimizing a search problem // Art. Intel. Methods and Appl. 1992. P. 63–105. https://doi.org/10.1142/9789814354707_0002
4. Gu J. Global optimization for satisfiability (SAT) problem // IEEE Trans. Knowl. Data Eng. 1994. Vol. 6, no. 3. P. 361–381. https://doi.org/10.1109/69.334864
5. Gu J., Gu Q., Du D. On optimizing the satisfiability (SAT) problem // J. Comp. Sci. Technol. 1999. Vol. 14, no. 1. P. 1–17. https://doi.org/10.1007/BF02952482
6. Файзуллин Р.Т., Дулькейт В.И., Огородников Ю.Ю. Гибридный метод поиска приближенного решения задачи 3-выполнимость, ассоциированной с задачей факторизации // Тр. Ин-та математики и механики УрО РАН. 2013. Т. 19, № 2. С. 285–294.
7. Pakhomchik A.I., Voloshinov V.V., Vinokur V.M., Lesovik G.B. Converting of boolean expression to linear equations, inequalities and QUBO penalties for cryptanalysis // Algorithms. 2022. Vol. 15, no. 2. Art. no. 33. https://doi.org/10.3390/a15020033
8. Ishchukova E., Maro E., Pristalov P. Algebraic analysis of a simplified encryption algorithm GOST R 34.12-2015 // Computation. 2020. Vol. 8, no. 2. Art. no. 51. https://doi.org/10.3390/computation8020051
9. Burek E., Wroński M., Mańk K., Misztal M. Algebraic attacks on block ciphers using quantum annealing // IEEE Trans. Emerg. Topics Comput. 2022. Vol. 10, no. 2. P. 678–689. https://doi.org/10.1109/TETC.2022.3143152
10. Bard G.V. Algorithms for solving linear and polynomial systems of equations over finite fields, with applications to cryptanalysis. College Park: University of Maryland Publ., 2007. 181 p.
11. Armario J.A. Boolean functions and permanents of Sylvester Hadamard matrices // Mathematics. 2021. Vol. 9, no. 2. Art. no. 177. https://doi.org/10.3390/math9020177
12. Ramos-Calderer S., Bravo-Prieto C., Lin R., Bellini E., Manzano M., Aaraj N., Latorre J. Solving systems of Boolean multivariate equations with quantum annealing // Physical Review Research. 2022. Vol. 4, no. 1. Art. no. 013096. https://doi.org/10.1103/PhysRevResearch.4.013096
13. Баротов Д.Н. Вогнутые продолжения булевоподобных функций и некоторые их свойства // Изв. Иркут. гос. ун-та. Сер.: Математика. 2025. Т. 51. С. 82–100. https://doi.org/10.26516/1997-7670.2025.51.82
14. Жук Д.Н. От двузначной к k-значной логике // Интеллектуальные системы. Теория и приложения. 2018. Т. 22, №. 1. С. 131–149.
15. Селезнева С.Н. Полиномиальные представления дискретных функций: дисс. …д-ра физ.-мат. наук: 01.01.09. Москва, 2016. 257 с.
16. Jensen J.L.W.V. Sur les fonctions convexes et les inégalités entre les valeurs moyennes // Acta Math. 1906. Vol. 30, no. 1. P. 175–193. https://doi.org/10.1007/BF02418571
Поступила 4.05.2025
После доработки 2.06.2025
Принята к публикации 13.08.2025
Баротов Достонжон Нумонжонович
старший преподаватель кафедры математики и анализа данных
Финансовый университет при Правительстве Российской Федерации
г. Москва
e-mail: DNBarotov@fa.ru
Ссылка на статью: Д.Н. Баротов. Критерии существования и единственности вогнутого продолжения функции $k$-значной логики // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 4. С. 52-61
English
D.N. Barotov. Criteria for the existence and uniqueness of a concave continuation of a function of $k$-valued logic
In this paper we study the existence and uniqueness of a concave continuation to the segment $[0,k-1]$ of an arbitrary unary function of $k$-valued logic $f_{L}:\{0,1,\ldots,k-1\}\to\{0,1,\ldots,k-1\}$ for any natural $k \geq 2$. As a result of the study, for an arbitrary natural $k \geq 2$ we formulate and prove a criterion for the existence of a concave continuation of a unary function of $k$-valued logic $f_{L}$. It is proved that the found criterion for the existence of a concave continuation of a function of $k$-valued logic $f_{L}$ is also a criterion for the existence of a minimal concave continuation of a function of $k$-valued logic $f_{L}$, but is not a sufficient condition for the uniqueness of a concave continuation of a function of $k$-valued logic $f_{L}$. We also find and prove a criterion for the uniqueness of a concave continuation of an arbitrary unary function of $k$-valued logic $f_{L}$.
Keywords: function of $k$-valued logic, concave continuation of a function of $k$-valued logic, criterion for the existence and uniqueness of a concave continuation
Received May 4, 2025
Revised June 2, 2025
Accepted August 13, 2025
Dostonjon Numonjonovich Barotov, Department of Mathematics and Data Analysis, Financial University under the Government of the Russian Federation, Moscow, 109456 Russia, e-mail: DNBarotov@fa.ru
Cite this article as: D.N. Barotov. Criteria for the existence and uniqueness of a concave continuation of a function of k-valued logic. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 4, pp. 52–61.
