This article is cited in 2 papers

Some features of the synthesis of Boolean formulae over complete bases with direct and iterative variables

V. A. Konovodov

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow, Russia

Abstract: The paper studies some issues of complexity of Boolean formulae over different bases that consist of Boolean functions with direct and iterative variables. It is shown that the standard behavior of the Shannon function for the complexity of the formulae $(2^n/\log n)$ does not always take place; the examples of the non-trivial families of bases where this function has the order of growth of $2^n$ are given. Such examples exist in each family in the classification of bases according to their iterative closures, except for two bases, where the Shannon function has the standard order of growth. A new representation of the iterative closure operator $\delta$ (introduced by S. A. Lozhkin) is obtained. The issue about the complexity of an affine function over some classes of bases is considered separately. The examples of radical changes of this complexity in different bases from one family are given.

Keywords: Boolean formulae, complexity of functions, Shannon function, direct and iterative variables.

UDC: 519.714

Received: 04.08.2014