The research of multifunctions is a one of the directions in discrete function’s investigations. Multifunction is a discrete function from a finite set A to all subsets of A. The set of hyperfunctions is a subset of set of multifunctions. Hyperfunction is a discrete function from a finite set A to all nonempty subsets of A.

The subset relation of hyperfunctions to maximal multiclones is a relation of equivalence and according it all hyperfunctions are divided into equivalence classes. Based on this equivalence it is possible to estimate the cardinality of all possible bases, calculate the number of different types of bases of the same cardinality, and construct some intervals of the clone lattice.

Knowing the number of maximal clones, we can obtain upper-bound estimate of the number of such classes as the cardinality of the set of all subsets of the set of maximal clones. It possible to lower this estimate by using properties of the hyperfunctions . A lower-bound estimate for the number of classes can be obtained by constructing the corresponding classes.

It is noteworthy that the complexity of the problem of describing all equivalence classes increases essentially with the cardinality of the set of maximal clones increasing.

This paper considers multifunctions on a two-element set. The number of maximal multiclones equals to 15 (Panteleyev V.I., 2009).

The primary purpose of this research is describing the classification of the set of hyperfunctions into equivalence classes. As Kazimirov A.S. and Panteleyev V.I. showed there are 18 equivalence classes on the set of Boolean functions, which is a subset of the set of hyperfunctions. In this paper were obtained special properties of hyperfunctions and were described all the equivalence classes generated by functions of 3 arguments having applied a computer experiment. The obtained results made it possible to show that the subset relation of hyperfunctions to maximal multiclones splits the set of all hyperfunctions into 67 equivalence classes.

MSC

08A99,03B50

DOI

https://doi.org/10.26516/1997-7670.2017.21.61

1. Kazimirov A.S., Panteleyev V.I. On the classes of Boolean functions generated by maximal multiclones Vestn. Buryat. Gos. Univ., Mat., Inf., 2015, vol. 9, pp. 16-22. (in Russian)

2. Kazimirov A.S., Panteleyev V.I., Tokareva L.V. Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set Izv. Irkutsk. Gos. Univ., Ser. Mat., 2014, vol. 7, pp. 61-78. (in Russian)

3. Panteleyev V.I. The criteria of completeness for redefining boolean function Vestn. Novosib. Gos. Univ., Ser. Mat. Mekh. Inform., 2009, vol. 9, no 3, pp. 95-114. (in Russian)

4. Tarasov V. V. A test for the completeness of not everywhere defined functions of the algebra of logic Problemy Kibernet., 1975, vol. 30, pp. 319-325. (in Russian)

5. Yablonskij S.V. On the Superpositions of Logic Functions Mat. Sbornik, 1952, vol. 30, no 2(72), pp. 329-348. (in Russian)

6. Krnic L. Types of bases in the algebra of logic. Glasnik matematicko-fizicki i astronomski, 1965, ser. 2, vol. 20, pp. 23–32.

7. Miykawa M., Stojmenovic I., Lau D., Rosenberg I. Classifikation and basis enumarations in many-valued logics Proc 17th International Symposium on Multi-Valued logic, Boston, 1987, pp. 151-160.

8. Miykawa M., Stojmenovic I., Lau D., Rosenberg I. Classifikation and basis enumarations of the algebras for partial functions Proc 19th International Symposium on Multi-Valued logic, Rostock, 1989, pp. 8–13.

9. Lau D., Miyakawa M. Classification and enumaration of bases in Pk(2) Asian-European Journal of Mathematics 2008, vol. 1, no. 2, pp. 255–282. https://doi.org/10.1142/S1793557108000242

10. Stojmenovic I. Classification of P3 and the enumeration of base of P3, Rev. of Res. 14, Fat. of Sci., Math. Ser., Novi Sad, 1984, pp. 73–80.

11. Miyakawa M., Rosenberg I., Stojmenovic I. Classification of three-valued logical functions preserving 0 Discrete Applied Mathematics, 1990, vol. 28, pp. 231–249. https://doi.org/10.1016/0166-218X(90)90005-W