priborИзвестия высших учебных заведений. ПриборостроениеJournal of Instrument Engineering0021-34542500-0381Национальный исследовательский университет ИТМО10.17586/0021-3454-2022-65-7-478-491pribor-253Research ArticleИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКАINFORMATION TECHNOLOGIES AND SYSTEMS, COMPUTER TECHNIQUEСложность произвольных функций алгебры логики малого числа переменныхComplexity of Arbitrary Functions of the Logic Algebra of a Small Number of VariablesМузыченкоО. Н.MuzychenkoО. N.

Олег Николаевич Музыченко – д-р техн. наук, профессор; главный конструктор информационно-управляющих систем

Санкт-Петербург

Oleg N. Muzychenko – Dr. Sci., Professor; Chief Designer of Information Control Systems

St. Petersburg

syntez2@yandex.ruНаучно-производственная фирма «Меридиан»Research and Production Firm Meridian202201122024657478491Copyright © Национальный исследовательский университет ИТМО, 20242024Национальный исследовательский университет ИТМОНациональный исследовательский университет ИТМОhttps://pribor.ifmo.ru/jour/about/submissions#copyrightNoticehttps://pribor.ifmo.ru/jour/article/view/253

Рассмотрен способ оценивания сложности произвольных функций алгебры логики, основанный на их представлении композицией монотонных функций. Получены точные верхние оценки сложности монотонных и произвольных функций, зависящих от малого числа переменных.

A method for evaluating the complexity of arbitrary function of Boolean algebra is examined, based on presenting such a function as a composition of monotone functions. Accurate upper estimates have been received for the complexity of monotone and arbitrary functions depending on a small number of variables.

монотонные и произвольные функции алгебры логикисложностьmonotone and arbitrary logic functionscomplexityReferencesШеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963. 829 с.Shannon C.E. Bell System Technical Journal, 1948, no. 3(July).Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики. 1963. Вып. 10. С. 88—96.Lupanov O.B. Problemy kibernetiki, 1963, no. 10, pp. 88–96. (in Russ.)Коршунов А. Д. Монотонные булевы функции // Успехи мат. наук. 2003. № 5. С. 89—162.Korshunov A.D. Russian Mathematical Surveys, 2003, no. 5, pp. 929–1001.Угольников А. Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. 1976. Вып. 31. С. 167—185.Ugol'nikov A.B. Problemy kibernetiki, 1976, no. 31, pp. 167–185. (in Russ.)Pippenger N. The complexity of monotone Boolean functions // Math. Systems Theory. 1978. Vol. 11. P. 289—316.Pippenger N. Math. Systems Theory, 1977/78, vol. 11, рр. 289–316.Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования // Проблемы кибернетики. 1965. Вып. 14. С. 31—110.Lupanov O.B. Problemy kibernetiki, 1965, no. 14, pp. 31–110. (in Russ.)Музыченко О. Н. Специализированные методы синтеза логических схем. Ч. 1. Методы синтеза логических схем симметричных и пороговых функций. СПб: Балт. гос. техн. ун-т, 2004. 161 с.Muzychenko O.N. Spetsializirovannyye metody sinteza logicheskikh skhem. Chast' 1. Metody sinteza logicheskikh skhem simmetrichnykh i porogovykh funktsiy (Specialized Methods for Synthesizing Logic Circuits. Part 1. Methods for Synthesizing Logic Circuits of Symmetric and Threshold Functions), St. Petersburg, 2004, 161 р. (in Russ.)Музыченко О. Н. Методы синтеза логических схем. СПб: Изд-во „Печатный цех“, 2018. 860 с.Muzychenko O.N. Metody sinteza logicheskikh skhem (Methods for Synthesizing Logic Circuits), St. Petersburg, 2018, 860 р. (in Russ.)Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. 368 с.Pospelov D.A. Logicheskiye metody analiza i sinteza skhem (Logical Methods of Analysis and Synthesis of Circuits), Moscow, 1974, 368 р. (in Russ.)Музыченко О. Н. О сложности реализации пороговых функций // Изв. вузов. Математика. 2017. № 7. С. 41—49.Muzychenko O.N. Russian Mathematics, 2017, no. 7, pp. 35–42.Карпова Н. А. Минимальные схемы из замыкающих контактов для монотонных функций пяти переменных // Проблемы кибернетики. 1973. Вып. 26. С. 53—94.Karpova N.A. Problemy kibernetiki, 1973, no. 26, pp. 53–94. (in Russ.)Музыченко О. Н. Синтез логических схем методом приближающих монотонных функций // Автоматика и телемеханика. 1994. № 12. С. 117—128.Muzychenko O.N. Automation and Remote Control, 1994, no. 12, pp. 117–128. (in Russ.)Коршунов А. Д. Решение проблемы Дедекинда о числе монотонных булевых функций // Докл. АН СССР. 1977. Т. 233, № 4. С. 543—546.Korshunov A.D. Soviet Mathematics. Doklady, 1977, no. 4(233), pp. 543–546. (in Russ.)Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. 1981. Вып. 38. С. 5—108.Korshunov A.D. Problemy kibernetiki, 1981, no. 38, pp. 5–108. (in Russ.)Музыченко О. Н., Лукоянов В. П. Быстродействующий алгоритм синтеза схем симметричных функций алгебры логики для систем автоматизированного проектирования // Вопр. радиоэлектроники. Сер. Общие вопросы радиоэлектроники. 1984. Вып. 12. С. 120—128.Muzychenko O.N., Lukoyanov V.P. Questions of radio electronics. General questions of radio electronics, 1984, no. 12, pp. 120–128. (in Russ.)

The authors declare that there are no conflicts of interest present.