Сложность произвольных функций алгебры логики малого числа переменных
https://doi.org/10.17586/0021-3454-2022-65-7-478-491
Аннотация
Рассмотрен способ оценивания сложности произвольных функций алгебры логики, основанный на их представлении композицией монотонных функций. Получены точные верхние оценки сложности монотонных и произвольных функций, зависящих от малого числа переменных.
Об авторе
О. Н. Музыченко
Научно-производственная фирма «Меридиан»
Россия
Россия
Олег Николаевич Музыченко – д-р техн. наук, профессор; главный конструктор информационно-управляющих систем
Санкт-Петербург
Список литературы
1. Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963. 829 с.
2. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 88—96.
3. Коршунов А. Д. Монотонные булевы функции // Успехи мат. наук. 2003. № 5. С. 89—162.
4. Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. 1976. Вып. 31. С. 167—185.
5. Pippenger N. The complexity of monotone Boolean functions // Math. Systems Theory. 1978. Vol. 11. P. 289—316.
6. Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31—110.
7. Музыченко О. Н. Специализированные методы синтеза логических схем. Ч. 1. Методы синтеза логических схем симметричных и пороговых функций. СПб: Балт. гос. техн. ун-т, 2004. 161 с.
8. Музыченко О. Н. Методы синтеза логических схем. СПб: Изд-во „Печатный цех“, 2018. 860 с.
9. Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. 368 с.
10. Музыченко О. Н. О сложности реализации пороговых функций // Изв. вузов. Математика. 2017. № 7. С. 41—49.
11. Карпова Н. А. Минимальные схемы из замыкающих контактов для монотонных функций пяти переменных // Проблемы кибернетики. 1973. Вып. 26. С. 53—94.
12. Музыченко О. Н. Синтез логических схем методом приближающих монотонных функций // Автоматика и телемеханика. 1994. № 12. С. 117—128.
13. Коршунов А. Д. Решение проблемы Дедекинда о числе монотонных булевых функций // Докл. АН СССР. 1977. Т. 233, № 4. С. 543—546.
14. Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. 1981. Вып. 38. С. 5—108.
15. Музыченко О. Н., Лукоянов В. П. Быстродействующий алгоритм синтеза схем симметричных функций алгебры логики для систем автоматизированного проектирования // Вопр. радиоэлектроники. Сер. Общие вопросы радиоэлектроники. 1984. Вып. 12. С. 120—128.
Рецензия
Для цитирования:
Музыченко О.Н. Сложность произвольных функций алгебры логики малого числа переменных. Известия высших учебных заведений. Приборостроение. 2022;65(7):478-491. https://doi.org/10.17586/0021-3454-2022-65-7-478-491
For citation:
Muzychenko О.N. Complexity of Arbitrary Functions of the Logic Algebra of a Small Number of Variables. Journal of Instrument Engineering. 2022;65(7):478-491. (In Russ.) https://doi.org/10.17586/0021-3454-2022-65-7-478-491
Просмотров:
12
Послать статью по эл. почте 