Geodesic
On some series of bases for the set of Boolean functions
The Bulletin of Irkutsk State University. Series Mathematics, Tome 15 (2016), pp. 92-107 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Keywords: Boolean function, repetition-free function, weakly repetition-containing function, base.
Mots-clés : term 
@article{IIGUM_2016_15_a7,
     author = {I. K. Sharankhaev},
     title = {On some series of bases for the set of {Boolean} functions},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {92--107},
     year = {2016},
     volume = {15},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2016_15_a7/}
}
TY  - JOUR
AU  - I. K. Sharankhaev
TI  - On some series of bases for the set of Boolean functions
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2016
SP  - 92
EP  - 107
VL  - 15
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2016_15_a7/
LA  - ru
ID  - IIGUM_2016_15_a7
ER  - 
%0 Journal Article
%A I. K. Sharankhaev
%T On some series of bases for the set of Boolean functions
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2016
%P 92-107
%V 15
%U http://geodesic.mathdoc.fr/item/IIGUM_2016_15_a7/
%G ru
%F IIGUM_2016_15_a7
I. K. Sharankhaev. On some series of bases for the set of Boolean functions. The Bulletin of Irkutsk State University. Series Mathematics, Tome 15 (2016), pp. 92-107. http://geodesic.mathdoc.fr/item/IIGUM_2016_15_a7/

[1] Kirichenko K. D., “Weakly Repetition-Containing Boolean Functions in Some Pre-Elementary Bases”, Irk. Univ. Ser.: Disk. Matem. i Informatika, 13, 61 pp. (in Russian)

[2] Kirichenko K. D., “Weakly Repetition-Containing Boolean Functions in Non-Binary Bases”, Irk. Univ. Ser.: Disk. Matem. i Informatika, 14, 2000, 21 pp. (in Russian)

[3] Kuznetsov A. V., “On Repetition-Free Contact Circuits and Repetition-Free Superpositions of Logic Functions”, Trudi Mat. Instit. AN USSR, 51, 1958, 186–225 (in Russian) | MR | Zbl

[4] Peryazev N. A., “Complexity of Representations of Boolean Functions by Formulas in Non-Monolinear Bases”, Irk. Univ. Ser.: Disk. Matem. i Informatika, 2, 1995, 15 pp. (in Russian)

[5] Peryazev N. A., “Weakly Repetition-Containing Boolean Functions in Binary Base”, Irk. Univ. Ser.: Disk. Matem. i Informatika, 4, 1998, 12 pp. (in Russian)

[6] Peryazev N. A., Elements of Theory of Boolean Functions, Fizmatlit, M., 1999, 112 pp. (in Russian)

[7] Stetsenko V. A., “On Preworst Bases in $P_2$”, Mat. Voprosi Kibernet., 1992, no. 4, 139–177 (in Russian) | Zbl

[8] Subbotovskaya B. A., “Comparison of Bases in Realization by Formulas of Logic Functions”, Dokl. Akad. Nauk USSR, 4 (1963), 478–481 | MR | Zbl

[9] Cherukhin D. Yu., “Algorithmic Criterion for Comparison of Boolean Bases”, Mat. Voprosi Kibernet., 1999, no. 8, 77–122 (in Russian) | MR

[10] Sharankhaev I. K., “On Weakly Repetition-Containing Boolean Functions in Some Pre-Elementary Base”, Disret. Analiz i Issled. Oper. Ser. 1, 10:2 (2003), 79–101 (in Russian) | MR

[11] Sharankhaev I. K., “On Boolean bases of the second level”, Izvest. Vuzov. Matem., 2004, no. 3, 81–82 (in Russian) | MR

[12] Sharankhaev I. K., “Weakly Repetition-Containing Boolean Functions in Pre-Elementary Non-Monotone Base of Order 3”, Vestnik Buryat. Univ. Ser. 13, 2005, no. 2, 61–71 (in Russian)

[13] Sharankhaev I. K., “On Classification of Bases of Boolean Functions”, Vestnik Buryat. Univ. Ser. 13, 2006, no. 3, 61–67 (in Russian)