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

Рассматривается задача о сложности реализации функций $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$-значной логики.