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

Дискретный анализ и исследование операций. 2018. Т. 25. № 1. С. 42–74.

Кочергин В. В., Михайлович А. В.

Исследуется сложность реализации функций k-значной логики (k > 2) схемами из функциональных элементов в бесконечном базисе, состоящем из отрицания Поста, т.е. функции x+1 (mod k), и всех монотонных функций. Под сложностью понимается общее число элементов в схеме. Для произвольной функии f установлены отличающиеся друг от друга не более чем на единицу нижняя и верхняя оценки сложности вида 3log3 (d(f)+1) +O(1), где d(f) --- максимальное  (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции f с большего значения на меньшее. Найдено точное значение соответствующей функции Шеннона, характеризующей сложность реализации самой сложнореализуемой функции от заданного числа переменных

Ключевые слова: функции многозначной логики, multi-valued logic functions, схемная сложность, infinite basis, бесконечный базис, inversion complexity, Markov's theorem, инверсионная сложность, теорема Маркова, nonmonotone complexity, немонотонная сложность, logic circuits, circuit complexity, логические схемы