On maximal clones of ultrafunctions of rank 2

S. V. Zamaratskaya   ; V. I. Panteleev

The Bulletin of Irkutsk State University. Series Mathematics, Tome 15 (2016), pp. 26-37

Résumé

This paper considers functions mapping a 2-element set $A$ to all non-empty subsets of $A$. These functions are called ultrafunctions of rank 2. Ultrafunctions of rank 2 can be interpreted as functions on all non-empty subsets of $A$. Value of ultrafunction on set $B \subseteq A$ is determined as intersection of values on all elements of $B$, if this intersection is not empty, and as union of these values otherwise. Thus an unltrafunction can be specified by all of its values on elements of $A$. Superposition of ultrafunctions is determined the same way. The number of maximal clones for all ultrafunctions of rank 2 is equal to 11 [V. Panteleev, 2009]. This paper studies properties of ultrafunctions with respect of their inclusion in maximal clones $\mathbb {K}_5$, $\mathbb {S}^-$, $\mathbb {T}_0^-$ and $\mathbb {T}_1^-$. These properties give some results concerning clone lattice (e.g., clones of intervals $I(\mathbb {T}_0\cap \mathbb {T}_1,\mathbb {T}_0)$ and $I(\mathbb {T}_0\cap \mathbb {T}_1,\mathbb {T}_1)$ are not included in clone $\mathbb {S}^-$; all self-dual and monotone ultrafuncions are included in $\mathbb {K}_1$ and $\mathbb {K}_2$). Some borders on classes of equivalence number are described (ultrafunctions not included in clones $\mathbb {T}_1^-$ and $\mathbb {K}_5$ generate no more than 32 classes of equivalence by relation of belonging to maximal clones). These results can be applied to classification of ultrafunctions by their inclusion in maximal clones.

Détail

Keywords: ultrafunction, clone, base
Mots-clés : maximal clone.

Bibliographie

[1] Kazimirov A. S., Panteleev V. I., Tokareva L. V., “Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set”, The bulletin of Irkutsk State University. Mathematics, 7 (2014), 61–78 (in Russian) | MR | Zbl

[2] Panteleev V. I., “The Completeness Criterion for Certain Boolean Functions”, Vestnik of Samara State University. Natural Science Series, 2009, no. 2(68), 60–79 (in Russian)

[3] Yablonskij S. V., “On the Superpositions of Logic Functions”, Mat. Sbornik, 30:2(72) (1952), 329–348 (in Russian) | MR | Zbl

[4] M. Miyakawa, I. Stojmenović, D. Lau, I. Rosenberg, “Classification and basis enumerations in many-valued logics”, Proc. 17th International Symposium on Multi-Valued logic (Boston, 1987), 151–160

[5] M. Miyakawa, I. Stojmenović, D. Lau, I. Rosenberg, “Classification and basis enumerations of the algebras for partial functions”, Proc. 19th International Symposium on Multi-Valued logic (Rostock, 1989), 8–13

[6] L. Krnić, “Types of bases in the algebra of logic”, Glasnik matematicko-fizicki i astronomski. Ser 2, 20 (1965), 23–32 | MR

[7] D. Lau, M. Miyakawa, “Classification and enumerations of bases in $P_k(2)$”, Asian-European Journal of Mathematics, 01:02 (2008), 255–282 | DOI | MR

[8] M. Miyakawa, I. Rosenberg, I. Stojmenović, “Classification of three-valued logical functions preserving 0”, Discrete Applied Mathematics, 28 (1990), 231–249 | DOI | MR | Zbl

[9] E. L. Post, Two-valued iterative systems of mathematical logic, Annals of Math. Studies, 5, Univer. Press, Princeton, 1941, 122 pp. | MR | Zbl

[10] I. Stojmenović, “Classification of $P_3$ and the enumeration of base of $P_3$”, Rev. of Res., Fat. of Sci., Math. Ser., Novi Sad., 14 (1984), 73–80 | MR | Zbl