|
Математические заметки, 1980, том 28, выпуск 2, страницы 279–300
(Mi mzm6449)
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 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
Образец цитирования:
А. А. Сапоженко, “Оценка длины и числа тупиковых д.н.ф. для почти всех не всюду определенных булевых функций”, Матем. заметки, 28:2 (1980), 279–300; Math. Notes, 28:2 (1980), 603–615
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm6449 https://www.mathnet.ru/rus/mzm/v28/i2/p279
|
Статистика просмотров: |
Страница аннотации: | 299 | PDF полного текста: | 96 | Первая страница: | 3 |
|