М. А. Алехина
О ЧИСЛЕ ЭЛЕМЕНТОВ СХЕМЫ, РЕАЛИЗУЮЩЕЙ
ОБОБЩЕННУЮ ФУНКЦИЮ ГОЛОСОВАНИЯ
Аннотация. <...> Рассматривается один из важнейших разделов математической
кибернетики – теория синтеза, надежности и сложности управляющих систем. <...> Актуальность исследований в этой области обусловлена важностью многочисленных приложений, возникающих в различных разделах науки и техники. <...> Все разнообразные средства цифровой техники: ЭВМ, микропроцессорные системы измерений и автоматизации технологических процессов, цифровая
связь, телевидение и т.д., строятся на единой элементной базе, в состав которой входят чрезвычайно разные по сложности микросхемы – от логических
элементов, выполняющих простейшие операции, до сложнейших программируемых кристаллов, содержащих миллионы логических элементов. <...> К числу основных модельных объектов математической теории
синтеза, сложности и надежности управляющих систем относятся схемы из
ненадежных функциональных элементов, реализующие булевы функции. <...> В
ряде результатов, относящихся к реализации булевых функций надежными
схемами из ненадежных функциональных элементов, фигурирует параметр
N gˆ – наименьшее число функциональных элементов, необходимых для реализации функции голосования x` в рассматриваемом полном базисе. <...> Оказалось,
что еще и другие функции (обозначим их множество через G) обладают свойствами, аналогичными свойствам функции голосования. <...> Пусть Ng – наименьшее число абсолютно надежных функциональных элементов, необходимых для реализации функции g ∈ G
в рассматриваемом полном базисе, а NG = min N g , т.е. NG – наименьшее число
g∈G
абсолютно надежных функциональных элементов, достаточное для реализации хотя бы одной функции из множества G в рассматриваемом полном базисе. <...> Цель данной работы – получить верхнюю оценку величины NG, которая
была бы справедлива в произвольном полном базисе. <...> Предполагается, что все
функциональные элементы базиса абсолютно надежны. <...> Для получения <...>