Теорема Шеннона — Лупанова

Теорема Шеннона — Лупанова определяет число элементов, необходимых для реализации автомата в заданном автоматном базисе^{[неизвестный термин]}.

Формулировка

1. Для любого базиса $\Sigma$: $L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}$, где $C_{\Sigma }$ — константа, зависящая от базиса.

2. Для любого $\epsilon >0$ доля функций $f$, для которых $L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}$ стремится к нулю с ростом $n$.

Пояснения

Здесь $L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)$, где максимум берется по всем функциям от $n$ переменных. Знак $\sim$ обозначает асимптотическое равенство: $a(n)\sim b(n)$, если $\lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1$. Смысл второго утверждения теоремы в том, что с ростом $n$ почти все функции реализуются со сложностью, близкой к верхней границе $L(n)$.

Доказательство

Доказательство есть в статье.

Литература

• Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с. — ISBN 5-283-01563-7.