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
REFERENCES
1. Barotov D.N. Concave continuations of Boolean functions and some of their properties and applications. Izv. Irkut. Gos. Univer. Ser. Mat., 2025, vol. 49, pp. 105–123 (in Russian). 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, pp. 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, pp. 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, pp. 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, pp. 1–17. https://doi.org/https://doi.org/10.1007/BF02952482
6. Faizullin R.T., Dulkeyt V.I., Ogorodnikov Yu.Yu. A hybrid search method for the approximate solution of the 3-satisfiability problem associated with the factorization problem. Trudy Inst. Mat. Mekh. UrO RAN, 2013, vol. 19, no. 2, pp. 285–294 (in Russian).
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, 22 p. 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, 21 p. 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, pp. 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, 8 p. 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. Phys. Rev. Research, 2022, vol. 4, no. 1, art. no. 013096, 9 p. https://doi.org/10.1103/PhysRevResearch.4.013096
13. Barotov D.N. Concave continuations of Boolean-like functions and some of their properties. Izv. Irkut. Gos. Univer. Ser. Mat., 2025, vol. 51, pp. 82–100 (in Russian). https://doi.org/10.26516/1997-7670.2025.51.82
14. Zhuk D.N. From two-valued logic to k-valued logic. Intel. Syst. Theory and Appl., 2018, vol. 22, no. 1, pp. 131–149 (in Russian).
15. Selezneva S.N. Polynomial representations of discrete functions. Diss. Doct. Phys.-Math. Sci.: 01.01.09, Moscow, 2016, 257 p. (in Russian).
16. Jensen J.L.W.V. Sur les fonctions convexes et les inegalites entre les valeurs moyennes. Acta Math., 1906, vol. 30, no. 1, pp. 175–193. https://doi.org/10.1007/BF02418571
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.
