№1 19 УДК 519.95 О СЛОЖНОСТИ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ С МАЛЫМ ЧИСЛОМ ЕДИНИЦ САМОКОРРЕКТИРУЮЩИМИСЯ КОНТАКТНЫМИ СХЕМАМИ Н.П. <...> Редькин1 В работе установлена асимптотика для сложности реализации самокорректирующимися контактными схемами булевых функций, обращающихся в единицу на относительно небольшом числе наборов значений переменных. <...> Ключевые слова: булевы функции, контактные схемы, самокорректирующиеся схемы, сложность реализации функций. <...> An asymptotics for the complexity of implementation of Boolean functions taking the unit value on a comparatively small set of collections of variables by self-correcting contact networks is obtained. <...> Key words: Boolean functions, contact networks, self-correcting schemes, complexity of implementation of functions. <...> (x1, . , xn), и на эту схему воздействует источник неисправностей [2, 3]. <...> Будем предполагать, что в результате этого воздействия контакты схемы могут переходить в неисправные состояния, которые можно интерпретировать как обрывы и (короткие) замыкания контактов [3, 4]; в случае обрыва контакт (рассматриваемый как двухполюсная контактная схема) реализует константу 0, а в случае замыкания —константу 1. <...> Схема S корректирует a обрывов и b замыканий, т.е. является (a, b)-самокорректирующейся, если в случае обрывов не более чем a контактов и замыканий не более чем b контактов эта схема реализует ту же функцию, что и в исправном состоянии. <...> Обозначим через L(S) сложность контактной схемы S, т.е. число контактов в ней. <...> Пусть La,b(f)= minL(S), где минимум берется по всем (a, b)-самокорректирующимся контактным схемам, реализующим булеву функцию f; функция Шеннона La,b(f) задает сложность реализации булевой функции f (a, b)-самокорректирующимися контактными схемами. <...> Ниже нас будет интересовать сложность реализации (a, b)-самокорректирующимися контактными схемами булевых функций с малым числом единиц, т.е. функций из класса Fn,k, состоящего из всех тех булевых функций от n переменных, каждая из которых обращается в единицу ровно на k наборах <...>