On Classes of Hyperfunctions of Rank 2 Generated by Maximal Multiclones

Abstract

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.

Keywords

• hyperclone
• basis
• hyperfunction
• complete set
• superposition
• closed set
• multifunction