Abstract:
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.
Key words:disjunctive normal forms, binary functions of multivalued arguments, $k$-valued logic, functions with few zeros, complexity of disjunctive normal forms, invariant transformations of variables.
Fulltext:
PDF file (95 kB)