Статья в сборнике "Математические вопросы кибернетики" №19, Москва, 2019
Авторы:Красулина Е.Г.
О нижней оценке сложности реализации системы всех элементарных симметрических функций контактными схемами
Аннотация:
Рассматривается задача реализации всех элементарных симметрических функций алгебры логики контактными схемами. В настоящей работе показано, что если контактная схема не имеет паразитных цепей и реализует систему всех элементарных симметрических функций от n переменных, то число контактов в такой схеме по крайней мере n(n+3)/2.
Ключевые слова:
элементарные симметрические функции, контактные схемы, теория сложности
