В. В. Чугунова
О НАДЕЖНОСТИ СХЕМ В НЕКОТОРЫХ ПРИВОДИМЫХ
ПОЛНЫХ БАЗИСАХ
Показано, что если к базису {x1 & x2, x1 } добавить, по крайней мере,
еще одну булеву функцию, зависящую не более чем от двух переменных, то
асимптотическая оценка ненадежности значительно понижается. <...> Рассмотрим реализацию булевых функций схемами из ненадежных
двухвходовых функциональных элементов. <...> Схема реализует функцию f(x1, x2,
..., xn) = f ( x ) , если при поступлении на входы схемы набора a = (a1, a2, ..., an)
при отсутствии неисправностей на выходе схемы появляется значение f (a ) . <...> Предполагается, что входы всех элементов схемы независимо друг от друга с
вероятностью ε (0 < ε < 1/2) подвержены инверсным неисправностям. <...> Эти
неисправности характеризуются тем, что поступающее на вход элемента значение a, (a ∈ {0, 1}) с вероятностью ε может превратиться в значение a . <...> Пусть Pf ( a ) ( S , a ) – вероятность появления значения f (a ) на выходе
схемы S, реализующей булеву функцию f ( x ) , при входном наборе a . <...> Ненадежность P(S) схемы S определяется как максимальное из чисел Pf ( a ) ( S , a )
при всевозможных входных наборах a . <...> Обозначим Pε ( f ) = inf P ( S ) , где S – схема из ненадежных элементов,
реализующая булеву функцию f. <...> Схему A из ненадежных элементов, реализующую булеву функцию f, назовем асимптотически оптимальной (наилучшей) по надежности, если P(A) ∼ Pε ( f ) при ε → 0. <...> Пусть B' – это множество всех булевых функций, зависящих не более
чем от двух переменных. <...> Множество B ⊂ M(x1, x2) назовем неприводимым полным базисом
(в P2), если множество B полно и никакое его собственное подмножество
полным не является. <...> Математика
Любой другой базис, отличный от базисов B1 – B17 (например, B18 =
= {x1 & x2, x1 ∨ x2, x1 }), можно получить переименованием переменных без
отождествления, а также добавлением одной или нескольких функций из
множества M(x1, x2) к некоторому базису из указанного списка. <...> Пусть базис B – один из базисов B1 – B18, тогда для него справедливы
теоремы 1 и 2. <...> Из теоремы 2 следует <...>