Оценки немонотонной сложности функций многозначной логики

Ученые записки Казанского университета. Серия: Физико-математические науки. 2020. Т. 162. № 3. С. 311–321.

Kochergin V., Mikhailovich A.

The problem of the complexity of multi-valued logic functions realization by circuits

in a special basis is investigated. This kind of basis consists of elements of

two types. The first type of elements are monotone functions with zero weight.

The second type of elements are non-monotone elements with unit weight.

The non-empty set of elements of this type is finite.

In the paper the upper and the lower bounds for non-monotone complexity (the minimum number of non-monotone elements) for an arbitrary

multi-valued logic function are improved.

The difference between the upper bound and the lower bound does not exceed constant value.

The difference between the best upper and lower bounds known before is value which depends on basis and are

arbitrary large.

Keywords: функции многозначной логики, multi-valued logic functions, схемная сложность, infinite basis, inversion complexity, logic circuit, немонотонная сложность