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.