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

Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Дата последнего поиска статьи во внешних источниках: 3 мая 2017 г.

Работа с статьей


[1] Кочергин В. В., Михайлович А. В. О минимальном числе отрицаний при реализации систем функций многозначной логики // Дискретная математика. — 2016. — Т. 28, № 4. — С. 80–90. Рассматривается задача о сложности реализации функций $k$-знач-ной логики схемами в бесконечных полных базисах, содержащих все монотонные функции, имеющие при этом нулевой вес (стоимость использования). Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А.,А.∼Марковым. В 1957 году он установил, что минимальное число отрицаний, достаточное для реализации произвольной булевой функции $f$ (инверсионная сложность функции $f$), равно $lceillog_{2}(d(f)+1)rceil$, где $d(f)$ — максимальное (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с б'ольшего значения на меньшее. В данной работе этот результат обобщен на случай вычисления функций $k$-значной логики. Установлено, что минимальное число отрицаний, достаточное для вычисления произвольной функции $k$-значной логики $f$ равно $lceillog_{2}(d(f)+1)rceil$, если под отрицанием понимается отрицание Поста (т.∼е. функция $x+1 pmod{k}$), и равно $lceillog_{k}(d(f)+1)rceil$, если под отрицанием понимается отрицание Лукасевича (т.∼е. функция $k-1 - x$). Также получено аналогичное обобщение другого классического результата А.,А.,Маркова∼— об инверсионной сложности систем булевых функций∼— на случай систем функций $k$-значной логики. [ DOI ]

Публикация в формате сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл сохранить в файл скрыть