Parametric closed classes of hyperfunctions on two-element set

L. V. Ryabets

The Bulletin of Irkutsk State University. Series Mathematics, Tome 17 (2016), pp. 46-61

Résumé

One of the direction in discrete function's investigations is research of functional systems: the sets of functions and the sets of operators defined on this functions. The modern line of inquiry of functional systems deals with generalization of many-valued functions such as partial functions, multifunctions or hyperfunctions. Hyperfunctions are discrete functions from a finite set $A$ to all nonempty subsets of $A$ which closed with respect to the superposition operator. In addition of the superposition operator its interesting to exam more stronger operators which given nontrivial function's classifications. For example, the criterion of completeness for the closure operator with the equality predicate branching on the set of hyperfunctions on two-element set was found. Another well-known strong operator is the parametric closure operator. Twenty five closed classes of Boolean functions is known for this operator. In this work we precise the definition of the parametric closure operator for the set of hyperfunctions and consider this operator on set of hyperfunctions on two-element set. With respect to this operator thirteen closed classes of hyperfunctions are founded. Two of them $S^-$ and $L^-$ are parametric precomplete. The lattice of parametric closed classes of hyperfunctions on two-element set are obtained and parametric bases of this classes are defined.

Détail

Keywords: closure, parametric closure, hyperfunction, completeness criterion
Mots-clés : superposition.

Bibliographie

[1] Danilchenko A. F., “About Parametric Expressibility of Ternary Logic Functions”, Algebra and Logic, 16:4 (1977), 397–416 (in Russian) | MR | Zbl

[2] Kuznetsov A. V., “Tools for Detecting Non-Derivability or Nonexpressibility”, Logical Inference, Nauka, M., 1979, 5–33 (in Russian)

[3] Lo Czu Kai, “Maximal Closed Classes on the Set of Partial Many-valued Logic Functions”, Kiberneticheskiy Sbornik, 25, Mir, M., 1988, 131–141 (in Russian) | Zbl

[4] Lo Czu Kai, “Completeness Theory on Partial Many-valued Logic Functions”, Kiberneticheskiy Sbornik, 25, Mir, M., 1988, 142–157 (in Russian) | MR

[5] Marchenkov S. S., Closed Classes of Boolean Functions, Fizmatlit, M., 2000, 126 pp. (in Russian)

[6] Marchenkov S. S., “On the Expressibility of Functions of Many-Valued Logic in Some Logical-Functional Classes”, Discrete Mathematics, 11:4 (1999), 110–126 (in Russian) | DOI | Zbl

[7] Marchenkov S. S., “Positive Closed Classes in the Three-Valued Logic”, Diskretn. Anal. Issled. Oper., 21:1 (2014), 67–83 (in Russian) | Zbl

[8] Marchenkov S. S., Popova A. A., “Positively Closed Classes of Partial Boolean Functions”, Vestnik MGU, Ser. 15: Computational Mathematics and Cybernetics, 2008, no. 3, 30–34 (in Russian)

[9] Panteleyev V. I., Ryabets L. V., “The Closure Operator with the Equality Predicate Branching on the Set of Hyperfunctions on Two-Element Set”, IIGU Ser. Matematika, 10 (2014), 93–105 (in Russian) | Zbl

[10] Tarasov V. V., “Completeness Criterion for Partial Logic Functions”, Problemy Kibernetiki, 30, Nauka, M., 1975, 319–325 (in Russian) | Zbl

[11] H. Machida, “Hyperclones on a two-element set”, Multiple-Valued Logic. An International Journal, 8:4 (2002), 495–501 | DOI | MR | Zbl

[12] H. Machida, J. Pantovic, “On maximal hyperclones on $\{0, 1\}$ — a new approach”, Proceedings of 38th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2008, 2008, 32–37

[13] B. A. Romov, “Hyperclones on a finite set”, Multiple-Valued Logic. An International Journal, 3:2 (1998), 285–300 | Zbl