Читать онлайн «Кибернетический сборник. Новая серия. Выпуск 21»

Кибернетический сборник НОВАЯ СЕРИЯ ВЫПУСК 21 Сборник переводов ПОД РЕДАКЦИЙ О. Б. ЛУПАЙОВА МОСКВА «МИР» 1984 ББК 32. 81 К 38 УДК 519. 95 Научный совет по кибернетике Академии наук СССР К 38 Кибернетический сборник. Новая серия. Вып. 21. Сб. статей; Пер. с англ. —М. : Мир, 1984, 264 с, ил. Продолжение серии, начатой издательством «Мир» в 1965 г. В выпуске со- содержатся обзорные статьи и оригинальные работы известных зарубежных ученых по наиболее актуальным проблемам теоретической кибернетики. Большой интерес представляют статьи Д. Плейстида по автоматическому доказательству теорем и И. Вегенера по монотонной сложности булевых функции. М. Храпченко ВВЕДЕНИЕ Схемы из функциональных элементов [9], известные также под названием комбинационные схемы [73], являются довольно точной моделью электронных логических схем без обратной связи, которые составной частью входят в многие устройства вычислительной техники, автоматики, телефонии и т. д. Одно- Одновременно с этим схе'мы из функциональных элементов пред- представляют собой весьма содержательный объект с математиче- математической точки зрения. Поэтому их исследованию посвящено огром- огромное число работ, которое продолжает быстро расти. Настоящий обзор является попыткой систематизировать факты, накопленные в одном из наиболее актуальных направ- направлений исследования схем из функциональных элементов. При работе над обзором автор существенно опирался на моногра- монографии Дж. Сэвиджа [82] и Р. Г. Нигматуллина [23], в которых можно найти подробное изложение многих результатов, упоми- упоминающихся в обзоре, и на обзорные статьи О. Б. Лупанова [11] и Р. Г. Нигматуллина [22], очень близкие по теме к данному обзору и наложившие на него свой идейный отпечаток. Понятие схемы из функциональных элементов фактически совпадает с понятием схемы вычисления, которую обычно по- понимают как последовательность равенств: где все переменные ziy ... , zi различны, каждая переменная tji] (i ==■ 1, ... ,/; / = 1, ... , ri)— это либо одна из входных (независимых) переменных хи ... , хп, либо одна из внутренних (зависимых) переменных zu . . . ,2i_i, вычисленных на предыду- предыдущих шагах, а фЬ ... ,ф/— некоторые функции. При этом каж- каждая из переменных zu ... , zt (а также каждая из переменных #ь ... , хп) может быть выражена в виде функции от перемен- © «Мир» 1984 В. М. Храпченко ных Х\9 ... , хп. Считается, что схема вычисления реализует лю- любую такую функцию. Если исходить из того, что в этих равенствах каждая опера- операция ф/ (/= 1, ... , /) выполняется функциональным элементом, то мы приходим к схеме из функциональных элементов. В этой схеме п входов, которым приписаны переменные хи ... , хП9 и / функциональных элементов, причем i-й элемент имеет п пе- перенумерованных входов и один выход, переменная zit приписан- приписанная его выходу, есть функция ф/ от переменных, приписанных его входам, а соединения осуществляются так, как это диктует- диктуется равенствами.