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

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

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



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






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


Дискрет. матем., 2016, том 28, выпуск 4, страницы 80–90 (Mi dm1394)  

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

О минимальном числе отрицаний при реализации систем функций многозначной логики

В. В. Кочергинab, А. В. Михайловичc

a МГУ им. М. В. Ломоносова
b ИТПМ им. Н. Н. Боголюбова МГУ
c НИУ ВШЭ

Аннотация: Рассматривается задача о сложности реализации функций $k$-значной логики схемами в бесконечных полных базисах, содержащих все монотонные функции; вес монотонных функций (стоимость использования) считается равным $0$. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А. А. Марковым. В 1957 году он установил, что минимальное число отрицаний, достаточное для реализации произвольной булевой функции $f$ (инверсионная сложность функции $f$), равно $\lceil\log_{2}(d(f)+1)\rceil$, где $d(f)$ — максимальное (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с бо́льшего значения на меньшее. В данной работе этот результат обобщен на случай вычисления функций $k$-значной логики. Установлено, что минимальное число отрицаний, достаточное для вычисления произвольной функции $k$-значной логики $f$, равно $\lceil\log_{2}(d(f)+1)\rceil$, если под отрицанием понимается отрицание Поста (т. е. функция $x+1 \pmod{k}$), и равно $\lceil\log_{k}(d(f)+1)\rceil$, если под отрицанием понимается отрицание Лукасевича (т. е. функция $k-1 - x$). Также получено аналогичное обобщение другого классического результата А. А. Маркова — об инверсионной сложности систем булевых функций — на случай систем функций $k$-значной логики.

Ключевые слова: Ключевые слова. Функции многозначной логики, логические схемы, схемная сложность, немонотонная сложность, инверсионная сложность, теорема Маркова.

Финансовая поддержка Номер гранта
Национальный исследовательский университет "Высшая школа экономики" 14-01-0144
Российский фонд фундаментальных исследований 14-01-00598_а
Данное научное исследование (№ 14-01-0144) выполнено при поддержке Программы «Научный фонд НИУ ВШЭ» в 2014/2015 гг. Работа первого автора выполнена при частичной финансовой поддержке РФФИ, проект № 14–01–00598.


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

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

Англоязычная версия:
Discrete Mathematics and Applications, 2017, 27:5, 295–302

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

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

Образец цитирования: В. В. Кочергин, А. В. Михайлович, “О минимальном числе отрицаний при реализации систем функций многозначной логики”, Дискрет. матем., 28:4 (2016), 80–90; Discrete Math. Appl., 27:5 (2017), 295–302

Цитирование в формате AMSBIB
\RBibitem{KocMik16}
\by В.~В.~Кочергин, А.~В.~Михайлович
\paper О минимальном числе отрицаний при реализации систем функций многозначной логики
\jour Дискрет. матем.
\yr 2016
\vol 28
\issue 4
\pages 80--90
\mathnet{http://mi.mathnet.ru/dm1394}
\crossref{https://doi.org/10.4213/dm1394}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3699323}
\elib{https://elibrary.ru/item.asp?id=28119093}
\transl
\jour Discrete Math. Appl.
\yr 2017
\vol 27
\issue 5
\pages 295--302
\crossref{https://doi.org/10.1515/dma-2017-0030}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000414954500004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85031803813}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1394
  • https://doi.org/10.4213/dm1394
  • http://mi.mathnet.ru/rus/dm/v28/i4/p80

    ОТПРАВИТЬ: 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. V. V. Kochergin, A. V. Mikhailovich, “Asymptotics of growth for non-monotone complexity of multi-valued logic function systems”, Сиб. электрон. матем. изв., 14 (2017), 1100–1107  mathnet  crossref
    2. В. В. Кочергин, А. В. Михайлович, “О сложности функций многозначной логики в одном бесконечном базисе”, Дискретн. анализ и исслед. опер., 25:1 (2018), 42–74  mathnet  crossref  elib; V. V. Kochergin, A. V. Mikhailovich, “On the complexity of multivalued logic functions over some infinite basis”, J. Appl. Industr. Math., 12:1 (2018), 40–58  crossref
    3. В. В. Кочергин, А. В. Михайлович, “Точное значение немонотонной сложности булевых функций”, Матем. заметки, 105:1 (2019), 32–41  mathnet  crossref  elib; V. V. Kochergin, A. V. Mikhailovich, “Exact Value of the Nonmonotone Complexity of Boolean Functions”, Math. Notes, 105:1 (2019), 28–35  crossref  isi
  • Дискретная математика
    Просмотров:
    Эта страница:208
    Полный текст:7
    Литература:31
    Первая стр.:27
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020