|
Algebraic and logical methods in computer science and artificial intelligence
Concave continuations of Boolean functions and some of their properties and applications
D. N. Barotov Financial University under the Government of the Russian Federation, Moscow, Russian Federation
Abstract:
In this paper, it is proved that for any Boolean function of $n$ variables, there are infinitely many functions, each of which is its concave continuation to the $n$-dimensional unit cube. For an arbitrary Boolean function of $n$ variables, a concave function is constructed, which is the minimum among all its concave continuations to the $n$-dimensional unit cube. It is proven that this concave function on the $n$-dimensional unit cube is continuous and unique. Thanks to the results obtained, in particular, it has been constructively proved that the problem of solving a system of Boolean equations can be reduced to the problem of numerical maximization of a target function, any local maximum of which in the desired domain is a global maximum, and, thus, the problem of local maxima for such problems is completely solved.
Keywords:
concave continuation of a Boolean function, Boolean function, concave function, global optimization, local extremum.
Received: 13.01.2024 Revised: 02.03.2024 Accepted: 12.03.2024
Citation:
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
Linking options:
https://www.mathnet.ru/eng/iigum578 https://www.mathnet.ru/eng/iigum/v49/p105
|
Statistics & downloads: |
Abstract page: | 13 | Full-text PDF : | 5 |
|