On pre-bad Boolean bases

In the paper the complexity of realization of Boolean functions by formulas over various bases is investigated. In terms of the complexity of almost all Boolean functions, bases are, in a sense, equal in rights. At the same time, individual sequences of functions admit essentially simpler realization over some bases than over other ones.
In this connection, of interest is such a method of comparison of bases which takes into account the complexity of realization of some individual sequences of functions. Such a method was proposed by O. B. Lupanov and then developed by B. A. Subbotovskaya and V. A. Stetsenko.
The research was supported by the Russian Foundation for Basic Research, grant 99–01–01175, and also by Federal Program ‘State support for integration of higher education and fundamental science for 1997–2000’, grant 2.1–473.