О предплохих булевых базисах

В работе изучается сложность реализации булевых функций формулами в различных базисах. С точки зрения сложности почти всех булевых функций базисы в некотором смысле равноправны. В то же время отдельные последовательности функций в одних базисах допускают существенно более простую реализацию, нежели в других. В этой связи интерес представляет такой метод сравнения базисов, который бы учитывал сложность реализации отдельных последовательностей функций. Такой метод был предложен О. Б. Лупановым и затем развит в работах Б. А. Субботовской и В. А. Стеценко.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, а также Федеральной целевой программы «Государственная поддержка интеграции высшего образования и фундаментальной науки на 1997–2000 гг.», проект 2.1–473.