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

Ученые записки Казанского университета. Серия: Физико-математические науки. 2020. Т. 162. № 3. С. 311–321.

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

Исследована задача о сложности реализации функций многозначной логики логическими схемами в базисе, состоящем из элементов двух типов. Элементами первого типа являются произвольные монотонные (относительно стандартного порядка) функции, таким элементам приписан нулевой вес. Конечное число немонотонных функций образует непустое множество элементов второго типа, каждой такой функции приписан единичный вес. Установлены верхняя и нижняя оценки немонотонной сложности (минимального достаточного для реализации числа немонотонных элементов в схеме) произвольной функции k-значной логики, разность между которыми не превосходит некоторой абсолютной константы. Разность наилучших известных до этого верхней и нижней оценок отличалась на константу, зависящую от базиса, при этом множество значений таких констант неограничено.

Ключевые слова: функции многозначной логики, multi-valued logic functions, схемная сложность, infinite basis, inversion complexity, logic circuit, немонотонная сложность