Answers are grounded in this paper and cite their sources.
Extremal convex and concave extensions of Boolean functions—used in solving and analyzing systems of Boolean equations, a fundamental problem in computer science—can be constructed based on a set of weighting coefficients that allow a point x in an n-dimensional space to be represented as a convex combination of the vertices of an n-dimensional unit cube. In this paper, the properties of such a set of weighting coefficients and one partition of the n-dimensional unit cube are substantiated. Based on these, an explicit analytical (simplified) solution is derived for the problem of calculating the value of a concave extension of a Boolean function, which is a particular problem of linear programming, for each of the four particular cases corresponding to these properties. Specifically, it is proven that if the set of weighting coefficients consists of a single element, then the values of the minimal concave extension and the polylinear extension of an arbitrary n-ary Boolean function coincide. Explicit formulas are provided for the minimal concave extensions of two fundamental n-ary Boolean functions: the disjunction and the conjunction of rank n. Furthermore, an explicit formula is derived for the minimal concave extension of an n-ary Boolean function whose zeros are non-adjacent. This work complements the existing literature on the properties of sets of weighting coefficients and the extremal convex and concave extensions of Boolean functions.
No takes yet. Share an insight, caveat, or question.
Dostonjon Numonjonovich Barotov (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: