RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2007, том 82, выпуск 6, страницы 822–828 (Mi mzm4193)

Эта публикация цитируется в 2 статьях

Асимптотика числа бесповторных булевых функций в элементарном базисе

О. В. Зубков

Иркутский государственный педагогический университет

Аннотация: В работе получена асимптотическая аппроксимация числа $K_n$ бесповторных булевых функций от $n$ переменных в элементарном базисе $\{\&,\vee,-\}$ при $n\to\infty$ с относительной погрешностью $O(1/\sqrt n\,)$. Как следствие, получено подтверждение гипотезы о существовании констант $\delta$ и $\alpha$ таких, что
$$ K_n\sim\delta\cdot\alpha^{n-1}\cdot(2n-3)!!, $$
и найдены эти константы.
Библиография: 7 названий.

УДК: 519.11+519.71

Поступило: 13.05.2006
Исправленный вариант: 29.01.2007

DOI: 10.4213/mzm4193


 Англоязычная версия: Mathematical Notes, 2007, 82:6, 741–747

Реферативные базы данных:


© МИАН, 2024