О сложности реализации линейных булевых функций в базисе «импликация — отрицание»

Работа посвящена исследованию схем из функциональных элементов в базисе $\{x \to y, \overline{x}\}$. Найдено точное значение сложности реализации неоднородной линейной функции, а также получено описание минимальных схем, реализующих однородную линейную функцию.
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект 14-01-00598 [1]).