DOI 10.17586/0021-3454-2022-65-7-478-491
УДК 62-507.15
СЛОЖНОСТЬ ПРОИЗВОЛЬНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ МАЛОГО ЧИСЛА ПЕРЕМЕННЫХ
Научно-производственная фирма „Меридиан“; главный конструктор информационно-управляющих систем;
Читать статью полностью
Аннотация. Рассмотрен способ оценивания сложности произвольных функций алгебры логики, основанный на их представлении композицией монотонных функций. Получены точные верхние оценки сложности монотонных и произвольных функций, зависящих от малого числа переменных.
Ключевые слова: монотонные и произвольные функции алгебры логики, сложность
Список литературы:
Список литературы:
- Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963. 829 с.
- Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 88—96.
- Коршунов А. Д. Монотонные булевы функции // Успехи мат. наук. 2003. № 5. С. 89—162.
- Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. 1976. Вып. 31. С. 167—185.
- Pippenger N. The complexity of monotone Boolean functions // Math. Systems Theory. 1978. Vol. 11. P. 289—316.
- Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31—110.
- Музыченко О. Н. Специализированные методы синтеза логических схем. Ч. 1. Методы синтеза логических схем симметричных и пороговых функций. СПб: Балт. гос. техн. ун-т, 2004. 161 с.
- Музыченко О. Н. Методы синтеза логических схем. СПб: Изд-во „Печатный цех“, 2018. 860 с.
- Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. 368 с.
- Музыченко О. Н. О сложности реализации пороговых функций // Изв. вузов. Математика. 2017. № 7. С. 41—49.
- Карпова Н. А. Минимальные схемы из замыкающих контактов для монотонных функций пяти переменных // Проблемы кибернетики. 1973. Вып. 26. С. 53—94.
- Музыченко О. Н. Синтез логических схем методом приближающих монотонных функций // Автоматика и телемеханика. 1994. № 12. С. 117—128.
- Коршунов А. Д. Решение проблемы Дедекинда о числе монотонных булевых функций // Докл. АН СССР. 1977. Т. 233, № 4. С. 543—546.
- Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. 1981. Вып. 38. С. 5—108.
- Музыченко О. Н., Лукоянов В. П. Быстродействующий алгоритм синтеза схем симметричных функций алгебры логики для систем автоматизированного проектирования // Вопр. радиоэлектроники. Сер. Общие вопросы радиоэлектроники. 1984. Вып. 12. С. 120—128.
