• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Дискретная математика. 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-значной логики.