Properties of the Set of Weight Coefficients and Their Application in Deriving an Explicit Solution Formula for a Special Linear Programming Problem

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.

Authors

Institutions

Publication Details

Journal
Symmetry
Published
2026-11-20
DOI
https://doi.org/10.3390/sym18111944
Primary Topic
Complexity and Algorithms in Graphs
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Properties of the Set of Weight Coefficients and Their Application in Deriving an Explicit Solution Formula for a Special Linear Programming Problem

Dostonjon Numonjonovich Barotov
2 links
Symmetry
Complexity and Algorithms in Graphs
article

Properties of the Set of Weight Coefficients and Their Application in Deriving an Explicit Solution Formula for a Special Linear Programming Problem

Dostonjon Numonjonovich Barotov
article en

Abstract

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.

SymmetryVol. 18(11)
Financial University (RU)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon