Математика
Об одном множестве функций
В. В. Чугунова Пензенский государственный университет, Пенза
Аннотация:
Рассматривается реализация булевых функций схемами из ненадежных функциональных элементов в базисах, содержащих функцию
$h(x_1,...,x_{2k+1})$ множества
$H_{2k+1}$. Предполагается, что базисные элементы независимо друг от друга с вероятностью
$\epsilon$ (
$\epsilon \in (0; 1/2)$) подвержены инверсным неисправностям на входах элементов. В работе показано: 1) в произвольном конечном полном базисе
$B$, содержащем функцию
$h(x_1,...,x_{2k+1})$ множества
$H_{2k+1}$, все булевы функции можно реализовать схемами с ненадежностью не более
$a\epsilon^{k+1}+\epsilon^{k+2}$ при
$\epsilon \leq \frac{1}{48am^2(2k+1)}$, где
$a=C_{2k+1}^{k+1}$,
$m$ - наибольшее число входов элементов в полном конечном базисе
$B$; 2) в базисе
$\tilde{B}$, содержащем все функции, зависящие не более чем от двух переменных, и функцию
$h(x_1,...,x_{2k+1}) \in H_{2k+1}$, функции
$0, 1, x_1, ..., x_n$ можно реализовать абсолютно надежно, а все остальные функции можно реализовать асимптотически оптимальными по надежности схемами, функционирующими с ненадежностью, асимптотически (при
$\epsilon \to 0$) равной
$a\epsilon^{k+1}$, где
$a=C_{2k+1}^{k+1}$.
Ключевые слова:
булевы функции, синтез, асимптотически оптимальные по надежности схемы.
УДК:
519.718