Email this article On the set of continuously differentiable concave extensions of a Boolean function
- Authors: Barotov D.N.1, Barotov R.N.2
-
Affiliations:
- Financial University under the Government of the Russian Federation
- Khujand State University named after academician Bobojon Gafurov
- Issue: Vol 30, No 149 (2025)
- Pages: 5-14
- Section: Articles
- URL: https://bakhtiniada.ru/2686-9667/article/view/304166
- ID: 304166
Cite item
Full Text
Abstract
This paper is devoted to the study of the existence of extremal elements of the set of continuously differentiable concave extensions to the set $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,\ldots,x_n)$, as well as finding the cardinality of the set of continuously differentiable concave extensions to $[0,1]^n$ of the Boolean function $f_{B}(x_1,\ldots,x_n).$ As a result of the study, it is proved that, firstly, for any Boolean function $f_{B}(x_1,\ldots,x_n)$ among its continuously differentiable concave extensions to $[0,1]^n$ there is no maximal element, secondly, if the Boolean function $f_{B}(x_1,\ldots,x_n)$ has more than one essential variable, then among its continuously differentiable concave extensions to $[0,1]^n$ there is no minimal element, and if the Boolean function is constant or has only one essential variable, then among its continuously differentiable concave extensions to $[0,1]^n$ there is a unique minimal element, the explicit form of which is given in the paper. It was also established that the cardinality of the set of continuously differentiable concave extensions to $[0,1]^n$ of an arbitrary Boolean function $f_{B}(x_1,\ldots,x_n)$ is equal to the continuum.
About the authors
Dostonjon N. Barotov
Financial University under the Government of the Russian Federation
Author for correspondence.
Email: DNBarotov@fa.ru
ORCID iD: 0000-0001-5047-7710
Senior Lecturer, Mathematics and Data Analysis Department
Russian Federation, 49/2 Leningradsky Prospekt, Moscow 125167, Russian FederationRuziboy N. Barotov
Khujand State University named after academician Bobojon Gafurov
Email: ruzmet.tj@mail.ru
ORCID iD: 0000-0003-3729-6143
Lecturer, Mathematical Analysis named after Professor A. Mukhsinov Department
Tajikistan, Mavlonbekova, Khujand 735700, Republic of TajikistanReferences
- D.N. Barotov, R.N. Barotov, "Construction of smooth convex extensions of Boolean functions", Vestnik rossiyskikh universitetov. Matematika = Russian Universities Reports. Mathematics, 29:145 (2024), 20-28 (In Russian).
- E. Ishchukova, E. Maro, P. Pristalov, "Algebraic analysis of a simplified encryption algorithm GOST R 34.12-2015", Computation, 8:2 (2020), 51.
- V.K. Leontiev, E.N. Gordeev, "On the number of solutions to a system of Boolean equations", Autom. Remote Control, 82:9 (2021), 1581-1596.
- M.A. Maltseva, A.S. Rumyantsev, "Boolean satisfiability verification by quantum annealing", Proceedings of the Karelian Scientific Center of the Russian Academy of Sciences, 2023, №4, 41-49 (In Russian).
- S. Ramos-Calderer, C. Bravo-Prieto, R. Lin, E. Bellini, M. Manzano, N. Aaraj, J. Latorre, "Solving systems of Boolean multivariate equations with quantum annealing", Phys. Rev. Res., 4:1 (2022), 013096.
- A.I. Pakhomchik, V.V. Voloshinov, V.M. Vinokur, G.B. Lesovik, "Converting of Boolean expression to linear equations, inequalities and QUBO Penalties for cryptanalysis", Algorithms, 15:2 (2022), 33.
- J. Gu, Q. Gu, D. Du, "On optimizing the satisfiability (SAT) problem", Journal of Computer Science and Technology, 14:1 (1999), 1-17.
- D.N. Barotov, D.Z. Muzafarov, R.N. Barotov, "On one method for solving systems of Boolean algebraic equations", Mod. Math. Concept Innov. Math. Educ., 8:1 (2021), 17-23 (In Russian).
- R.T. Faizullin, V.I. Dul'keit, Yu.Yu. Ogorodnikov, "Hybrid method for the approximate solution of the 3 -satisfiability problem associated with the factorization problem", Trudy Inst. Mat. i Mekh. UrO RAN, 19, 2013, 285-294 (In Russian).
- D.N. Barotov, "Convex continuation of a Boolean function and its applications", J. Appl. Ind. Math., 18:1 (2024), 1-9.
- D.N. Barotov, "On the existence and properties of convex extensions of Boolean functions", Math. Notes, 115:4 (2024), 489-505.
- D.N. Barotov, "Convex continuations of some discrete functions", J. Appl. Ind. Math., 18:3 (2024), 412-423.
- D.N. Barotov, "Target function without local minimum for systems of logical equations with a unique solution", Mathematics, 10:12 (2022), 2097.
- D.N. Barotov, R.N. Barotov, "Polylinear continuations of some discrete functions and an algorithm for _nding them", Numerical Methods and Programming, 24:1 (2023), 10-23 (In Russian).
- D.N. Barotov, "Concave continuations of Boolean functions and some of their properties and applications", Bulletin of Irkutsk State University. Series Mathematics, 49 (2024), 105-123 (In Russian).
- D.N. Barotov, V.A. Sudakov, "On inequalities between convex, concave, and multilinear continuations of Boolean functions", Keldysh Institute preprints, 2024, №30, 1-13 (In Russian).
- A. Salomaa, "On essential variables of functions, especially in the algebra of logic", Ann. Acad. Sci. Fenn. Ser. AI Math., 1963, №339, 1-11.
- Yu.Ya. Breitbart, "Essential variables of functions of the algebra of logic", Dokl. Akad. Nauk SSSR, 172:1 (1967), 9-10 (In Russian).
Supplementary files
