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

Матем. заметки, 1980, том 28, выпуск 2, страницы 279–300 (Mi mzm6449)

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

Оценка длины и числа тупиковых д.н.ф. для почти всех не всюду определенных булевых функций

А. А. Сапоженко


Аннотация: Для почти всех частичных булевых функций $f(x_1,\dots,x_n)$, принимающих значение 1 на $u$ вершинах и значение 0 на $v$ вершинах единичного $n$-мерного куба, получены оценки для числа тупиковых д.н.ф. $\tau(f)$, наибольшей длины тупиковой д.н.ф. $l(f)$ и длины сокращенной д.н.ф. $s(f)$. Показано, что при ограничениях $n\leqslant v\leqslant2^{n-27\log_2n}$, $log_2v\leqslant u\leqslant v\log_2n/64$ для почти всех функций $f$ имеет место $\log_2\tau(f)=(1+\delta_n^{(1)})\log_2C^r_n$, $l(f)=(1-\delta_n^{(2)})u$, $s(f)=(C_n^r)^{1+\delta_n^{(3)}}\min\{u,2^r\}$, где $r=[\log_2v-\log_2\ln\log_2v-1_1$, $\lim_{n\to\infty}\delta_n^{(i)}=0$, $i=1,2,3$. Библ. 5 назв.

Поступило: 10.01.1978


 Англоязычная версия: Mathematical Notes, 1980, 28:2, 603–615

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


© МИАН, 2024