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

Дискретная математика. 2016. Т. 28. № 4. С. 80–90.

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

Рассматривается задача о сложности реализации функций k-значной логики схемами в бесконечных полных базисах, содержащих все монотонные функции; вес монотонных функций (стоимость использования) считается равным 0. Для сложности реализации булевых функций в случае, когда единственным немонотонным элементом базиса является отрицание, исчерпывающее описание было получено А. А. Марковым. В 1957 году он установил, что минимальное число отрицаний, достаточное для реализации произвольной булевой функции f (инверсионная сложность функции f), равно ]log2(d(f)+1)[, где d(f) — максимальное (максимум берется по всем возрастающим цепям наборов значений переменных) число изменений значений функции с бо́льшего значения на меньшее. В данной работе этот результат обобщен на случай вычисления функций k-значной логики. Установлено, что минимальное число отрицаний, достаточное для вычисления произвольной функции k-значной логики f, равно ]log2(d(f)+1)[, если под отрицанием понимается отрицание Поста (т. е. функция x+1 mod k), и равно ]logk(d(f)+1)[, если под отрицанием понимается отрицание Лукасевича (т. е. функция k-1-x). Также получено аналогичное обобщение другого классического результата А. А. Маркова — об инверсионной сложности систем булевых функций — на случай систем функций k-значной логики.
 

Ключевые слова: функции многозначной логики, multi-valued logic functions, схемная сложность, inversion complexity, Markov's theorem, инверсионная сложность, теорема Маркова, nonmonotone complexity, немонотонная сложность, logic circuits, circuit complexity, логические схемы

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Классификация замкнутых классов функций многозначной логики, порожденных симметрическими функциями, по типам базируемости (2014)