Статья в сборнике "Математические вопросы кибернетики" №22, Москва, 2024
Авторы:Кочергин В.В., Михайлович А.В.
О немонотонной сложности булевых функций и функций k-значной логики
Аннотация:
В работе с единых позиций описаны основные продвижения, полученные за последние 10 лет в задачах, являющихся различными обобщениями задачи об инверсионной сложности булевых функций, решенной в 50-х годах прошлого века А.А. Марковым, установившим для произвольной булевой функции точное значение минимально возможного числа инверторов для схемной реализации в случае «бесплатного» использования монотонных функций. В работе, в частности, изложено получение следующих результатов: нахождение точного значения немонотонной сложности булевых функции; установление точного значения инверсионной сложности функций многозначной логики и для случая отрицания Поста, и для случая отрицания Лукасевича; доказательство верхней и нижней оценок немонотонной сложности произвольной функции многозначной логики, отличающихся на небольшую константу, не зависящую от базиса. В работе также затронут вопрос о схемной сложности булевых функций над бесконечными базисами: во-первых, дан достаточно полный обзор по этой теме, а во-вторых, изложено нахождение точного значение схемной сложности произвольной булевой функции над базисом, состоящем из отрицания и всех монотонных булевых функций.
Ключевые слова:
булевы (логические) схемы, схемы из функциональных элементов, схемная сложность, инверсионная сложность, немонотонная сложность, базисы с нулевыми весами, бесконечные базисы, функции многозначной логики
