Asymptotics for the Complexity of Boolean Functions with Small Number of Ones

The class $$F_{n,k}$$ of Boolean functions consisting of all functions of $$n$$ variables each of which outputs $$1$$ at exactly $$k$$ $$n$$ -tuples of values of the variables is considered. For small $$k$$ , for example, for $$k<\ln n$$ , an asymptotics for the complexity of implementation of every function in $$F_{n,k}$$ by a circuit of functional elements in an irredundant basis containing $$x\to y$$ and $$\overline{x\to y}$$ is found.