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