рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2016. Vol. 15

On Some Series of Bases for the Set of Boolean Functions

Author(s)
I. K. Sharankhaev
Abstract

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.

The basis {∨, ·,−, 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, term, repetition-free function, weakly repetition-containing function, base
UDC
519.71

MSC
06E30
References

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.


Full text (russian)