On some series of bases for the set of Boolean functions

I. K. Sharankhaev

The Bulletin of Irkutsk State University. Series Mathematics, Tome 15 (2016), pp. 92-107

Résumé

In this paper the problem of comparison of Boolean bases is considered. In our case the bases are compared on the complexity of Boolean functions representation by terms (formulas). The partial order is introduced on the set of all Boolean functions bases with respect to which a system of equivalence classes is obtained.It is known that the criterion for the equivalence for two bases is a reciprocal repetition-free expressiveness of functions of the one basis by the functions of the other, and the augmentation of a basis with a function weakly repetition-containing in it allows us not only to expand it, but makes this expansion minimal, making it possible to investigate the bases using the complexity of Boolean function representations with terms.Thus, the problem of describing the equivalence classes of bases can be reduced to finding weakly repetition-containing functions in specific bases. The basis $\{\vee, \cdot, -, 0,1 \}$ is the largest element in this partial order and its equivalence class forms the null level of the structure. The description of bases of the first level and, partially, of the second level has been obtained by several authors. This article describes the weakly repetition-containing Boolean functions in the same basis, in terms of uniformity, which completes the characterization of bases of the second level.

Détail

Keywords: Boolean function, repetition-free function, weakly repetition-containing function, base.
Mots-clés : term