• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

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