О реализации булевых функций контактными схемами равномерной ширины 3

К.А. Попков

Институт прикладной математики им. М.В. Келдыша Российской академии наук, г. Москва, 125047, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2020.3.350-358

Для цитирования: Попков К.А. О реализации булевых функций контактными схемами равномерной ширины 3 // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2020. – Т. 162, кн. 3. – С. 350–358. – doi: 10.26907/2541-7746.2020.3.350-358.

For citation: Popkov K.A. On the implementation of Boolean functions by contact circuits with uniform width 3. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2020, vol. 162, no. 3, pp. 350–358. doi: 10.26907/2541-7746.2020.3.350-358. (In Russian)

Аннотация

Основной задачей исследования является изучение возможностей реализации произвольной булевой функции контактной схемой как можно меньшей равномерной ширины. Х.А. Мадатян в 1965 г. сформулировал понятие ширины контактной схемы; однако оно не всегда соответствует интуитивному представлению о ширине. В связи с этим в настоящей статье введено понятие равномерной ширины контактной схемы и показано, что для ряда случаев оно соответствует интуитивному смыслу понятия ширины. Доказано, что любую булеву функцию можно реализовать контактной схемой, равномерная ширина которой не превосходит 3.

Ключевые слова: контактная схема, булева функция, равномерная ширина

Литература

1. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. – М.: Изд-во Моск. ун-та, 1984. – 138 с.
2. Shannon C.E. A symbolic analysis of relay and switching circuits // Trans. AIEE. – 1938. – V. 57. – P. 713–723. – doi: 10.1109/T-AIEE.1938.5057767.
3. Shannon C.E. The synthesis of two-terminal switching circuits // Bell Syst. Tech. J. – 1949. – V. 28, No 1. – P. 59–98. – doi: 10.1002/j.1538-7305.1949.tb03624.x.
4. Коршунов А.Д. Сложность вычислений булевых функций // Усп. матем. наук. – 2012. – Т. 67, Вып. 1. – С. 97–168. – doi: 10.4213/rm9459.
5. Мадатян Х.А. Синтез контактных схем ограниченной ширины // Проблемы кибернетики. – М.: Наука, 1965. – Вып. 14. – С. 301–307.
6. Карпова Н.А. О вычислениях с ограниченной памятью // Математические вопросы кибернетики. – М.: Наука, 1989. – Вып. 2. – С. 131–144.
7. Окольнишникова Е.А. О сложности ветвящихся программ // Математические вопросы кибернетики. – М.: ФИЗМАТЛИТ, 2001. – Вып. 10. – С. 69–82.
8. Ложкин С.А. Лекции по основам кибернетики. – М.: Изд. отд. фак. ВМиК МГУ, 2004. – 253 с.
9. Коноводов В.А. О синтезе схем ограниченной ширины // Материалы VIII молодёжной науч. шк. по дискретной математике и её приложениям. – М.: Изд-во мех.-матем. фак. МГУ, 2011. – Ч. 1. – С. 37–41.
10. Кравцов С.С. О реализации функций алгебры логики в одном классе схем из функциональных и коммутационных элементов // Проблемы кибернетики. – М.: Наука, 1967. – Вып. 19. – С. 285–292.
11. Редькин Н.П. Надёжность и диагностика схем. – М.: Изд-во Моск. ун-та, 1992. – 192 с.

Поступила в редакцию 06.07.2020

Попков Кирилл Андреевич, кандидат физико-математических наук, научный сотрудник

Институт прикладной математики им. М.В. Келдыша Российской академии наук Миусская пл., д. 4, г. Москва, 125047, Россия

E-mail: kirill-formulist@mail.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.