Transformations of variables invariant under minimization of binary functions of multivalued arguments

摘要

A number of transformations are introduced that are invariant under minimization problems and make it possible to reduce the maximum possible number of distinct columns in the matrix of zeros of an arbitrary binary function of multivalued arguments. As a result, simpler disjunctive normal forms are constructed. Complexity bounds for the constructed disjunctive normal forms of arbitrary binary functions of k-valued arguments are given.