On a minimization problem for a set of Boolean functions
Igor' Petrovich Chukhrov · Journal of Applied and Industrial Mathematics · 2015
We study the set of Boolean functions that consist of a single connected component, have minimal complexes of faces which are not shortest, and do not satisfy the sufficient minimality conditions based on the notion of an independent set of vertices. For the minimization of functions with the indicated properties, the available efficient methods such as the independent minimization for the connected components and the fulfillment of sufficientminimality conditions are inapplicable. For this set of functions, we obtain some lower bounds for the capacity and the maximal number of complexes of faces minimal under additive measures of the linear and polynomial complexity.