Concave Continuations of Boolean Functions and Some of Their Properties and Applications

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