Lattice of $E$-closed Classes of Multifunctions of Rank 2

Abstract

Multifunctions are discrete functions defined on a finite set and returning as their values all subsets of the considered set. The paper considers the classification of multifunctions defined on a two-element set with respect to the E-closure operator. E-closed sets of multifunctions are sets that are closed under superposition, the closure operator with branching by the equality predicate, the identification of variables, and the addition of dummy variables. The concept of separating sets was introduced using a greedy algorithm for the set covering problem, and 22 classes of separating sets were obtained. It is shown that the classification under consideration leads to a finite set of closed classes. The work describes all 359 E-closed classes of multifunctions, among which there are 138 pairs of dual classes and 83 self-dual classes. For each class consisting only of multifunctions, its generating system is indicated.

Keywords

• closure
• equality predicate
• multifunction
• closed set
• composition