List of issues > Series «Mathematics». 2016. Vol. 15
On Some Series of Bases for the Set of Boolean Functions
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 repetitioncontaining functions in specific bases.
MSC
06E30
1. Kirichenko K.D. Weakly Repetition-Containing Boolean Functions in Some Pre-Elementary Bases (in Russian). Irk. Univ. Ser.: Disk. Matem. i Informatika, 2000, vol. 13. 61 p.
2. Kirichenko K.D. Weakly Repetition-Containing Boolean Functions in Non-Binary Bases (in Russian). Irk. Univ. Ser.: Disk. Matem. i Informatika,2000, vol. 14. 21 p.
3. Kuznetsov A.V. On Repetition-Free Contact Circuits and Repetition-Free Superpositions of Logic Functions (in Russian). Trudi Mat. Instit. AN USSR, 1958, vol. 51, pp. 186-225.
4. Peryazev N.A. Complexity of Representations of Boolean Functions by Formulas in Non-Monolinear Bases (in Russian). Irk. Univ. Ser.: Disk. Matem. i Informatika, 1995, vol. 2. 15 p.
5. Peryazev N.A. Weakly Repetition-Containing Boolean Functions in Binary Base (in Russian). Irk. Univ. Ser.: Disk. Matem. i Informatika, 1998, vol. 4. 12 p.
6. Peryazev N.A. Elements of Theory of Boolean Functions (in Russian). Moscow, Fizmatlit, 1999. 112 p.
7. Stetsenko V. A. On Preworst Bases in P2 (in Russian). Mat. Voprosi Kibernet., 1992, vol. 4, pp. 139-177.
8. Subbotovskaya B. A. Comparison of Bases in Realization by Formulas of Logic Functions (in Russian). Dokl. Akad. Nauk USSR, 1963, vol. 4, pp. 478-481.
9. Cherukhin D. Yu. Algorithmic Criterion for Comparison of Boolean Bases (in Russian). Mat. Voprosi Kibernet., 1999, vol. 8, pp. 77-122.
10. Sharankhaev I. K. On Weakly Repetition-Containing Boolean Functions in Some Pre-Elementary Base (in Russian). Disret. Analiz i Issled. Oper. Ser. 1, 2003, vol. 10, no 2, pp. 79-101.
11. Sharankhaev I. K. On Boolean bases of the second level (in Russian). Izvest. Vuzov. Matem., 2004, no 3, pp. 81-82.
12. Sharankhaev I. K. Weakly Repetition-Containing Boolean Functions in Pre-Elementary Non-Monotone Base of Order 3 (in Russian). Vestnik Buryat. Univ. Ser. 13, 2005, vol. 2, pp. 61-71.
13. Sharankhaev I. K. On Classification of Bases of Boolean Functions (in Russian). Vestnik Buryat. Univ. Ser. 13, 2006, vol. 3, pp. 61-67.