Точное значение схемной сложности булевых функций в одном бесконечном базисе

В. В. Кочергин^a, А. В. Михайлович<sup>b

a</sup> Московский государственный университет им. М. В. Ломоносова
^b Национальный исследовательский университет "Высшая школа экономики", г. Москва

Аннотация: Для каждой булевой функции установлено точное значение сложности реализации логическими схемами в бесконечном базисе, состоящем из отрицания и всех монотонных булевых функций. Под сложностью функции понимается минимально возможное число элементов базиса, достаточное для построения схемы для данной функции.
Библиография: 20 названий.

Ключевые слова: логические (булевы) схемы, схемы из функциональных элементов, схемная сложность, инверсионная сложность, бесконечный базис.

УДК: 519.71

Поступило: 08.08.2024

DOI: 10.4213/mzm14465

 Англоязычная версия: Mathematical Notes, 2025, 117:4, 579–594

Реферативные базы данных:

• 
•