|
Вестник Московского университета. Серия 1: Математика. Механика, 2011, номер 1, страницы 22–26
(Mi vmumm650)
|
|
|
|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Математика
О глубине функций $k$-значной логики в бесконечных базисах
А. В. Кочергин Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Рассматривается реализация функций $k$-значной логики схемами из функциональных элементов над произвольным бесконечным полным базисом $B$. Изучается поведение функции Шеннона $D_B(n)$ глубины схем над базисом $B$ (здесь при любом натуральном $n$ значение $D_B(n)$ равно наименьшей глубине схем, достаточной для реализации над базисом $B$ любой функции $k$-значной логики от $n$ переменных). Устанавливается, что при любом фиксированном $k\ge2$ для любого бесконечного полного базиса $B$ функций $k$-значной логики либо существует константа $\alpha \ge 1$, такая, что $D_B(n)=\alpha$ при всех достаточно больших $n$, либо существуют константы $\beta$ ($\beta>0$), $\gamma$, $\delta$, такие, что $\beta\log_2n\le D_B(n)\le\gamma\log_2n+\delta$ при всеx $n$.
Ключевые слова:
$k$-значные логики, глубина схем, бесконечный базис.
Поступила в редакцию: 09.06.2010
Образец цитирования:
А. В. Кочергин, “О глубине функций $k$-значной логики в бесконечных базисах”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2011, № 1, 22–26; Moscow University Mathematics Bulletin, 66:1 (2011), 20–24
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vmumm650 https://www.mathnet.ru/rus/vmumm/y2011/i1/p22
|
Статистика просмотров: |
Страница аннотации: | 41 | PDF полного текста: | 22 |
|