RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Дискрет. матем., 2015, том 27, выпуск 1, страницы 111–122 (Mi dm1319)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм

С. Н. Селезнева

МГУ им. М.В. Ломоносова

Аннотация: Поляризованная полиномиальная форма (ППФ) (по модулю $k$) – это сумма по модулю $k$ произведений переменных $x_1, …, x_n$ или их отрицаний Поста, причем число отрицаний каждой переменной определяется вектором поляризации этой ППФ. Длиной ППФ называется число ее попарно различных слагаемых. Длиной функции $k$-значной логики $f(x_1, …, x_n)$ в классе ППФ называется минимальная длина среди всех ППФ, реализующих эту функцию. В работе построена такая последовательность симметрических функций трехзначной логики $f_n(x_1, …, x_n)$, что длина каждой из функций $f_n$ в классе ППФ не меньше, чем $\lfloor 3^{n+1}/4 \rfloor$, где $\lfloor a \rfloor$ обозначает наибольшее целое число, не превосходящее число $a$. Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во всех этих ППФ. Сложностью $L_k^{\textrm{ППФ}}(F)$ системы $F = \{f_1, …, f_m\}$ функций $k$-значной логики, зависящих от переменных $x_1, …, x_n$, в классе ППФ называется минимальная сложность среди всех таких систем ППФ $\{p_1, …, p_m\}$, что все ППФ $p_1, …, p_m$ имеют один и тот же вектор поляризации, и ППФ $p_j$ реализует функцию $f_j$, $j = 1, …, m$. Пусть $L_k^{\textrm{ППФ}}(m, n) = \max\limits_{F}L_k^{\textrm{ППФ}}(F)$, где индекс $F$ пробегает по всем системам, содержащим $m$ функций $k$-значной логики, зависящих от переменных $x_1, …, x_n$. Понятно, что при простых $k$ верна оценка $L_k^{\textrm{ППФ}}(m, n) \le k^n$. В работе доказано, что $L_2^ППФ(m, n) = 2^n$ и $L_3^{\textrm{ППФ}}(m, n) = 3^n$ для всех $m \ge 2$, $n = 1, 2, …$. Более того, доказано, что оценки остаются такими же, если рассматривать только системы симметрических функций.
Работа поддержана РФФИ, проекты 13–01–00684-а, 13–01–00958-а.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 13-01-00684-а
13-01-00958-а
Работа поддержана РФФИ, проекты 13-01-00684-а, 13-01-00958-а.


DOI: https://doi.org/10.4213/dm1319

Полный текст: PDF файл (438 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2016, 26:2, 115–124

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

Тип публикации: Статья
УДК: 519.716.325
Статья поступила: 09.10.2014

Образец цитирования: С. Н. Селезнева, “Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм”, Дискрет. матем., 27:1 (2015), 111–122; Discrete Math. Appl., 26:2 (2016), 115–124

Цитирование в формате AMSBIB
\RBibitem{Sel15}
\by С.~Н.~Селезнева
\paper Сложность систем функций алгебры логики и систем функций трехзначной логики в классах поляризованных полиномиальных форм
\jour Дискрет. матем.
\yr 2015
\vol 27
\issue 1
\pages 111--122
\mathnet{http://mi.mathnet.ru/dm1319}
\crossref{https://doi.org/10.4213/dm1319}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468145}
\elib{http://elibrary.ru/item.asp?id=23780140}
\transl
\jour Discrete Math. Appl.
\yr 2016
\vol 26
\issue 2
\pages 115--124
\crossref{https://doi.org/10.1515/dma-2016-0009}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000375870900004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84968884486}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1319
  • https://doi.org/10.4213/dm1319
  • http://mi.mathnet.ru/rus/dm/v27/i1/p111

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. И. Мамонтов, С. М. Рябинов, “Об одном методе экономии памяти при классификации текстов”, Программные системы: теория и приложения, 8:4 (2017), 133–147  mathnet  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:293
    Полный текст:75
    Литература:42
    Первая стр.:25
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020