On the classes of Boolean functions generated by maximal partial ultraclones

S. A. Badmaev

The Bulletin of Irkutsk State University. Series Mathematics, Tome 27 (2019), pp. 3-14

Résumé

The sets of multifunctions are considered. A multifunction on a finite set $A$ is a function defined on the set $A$ and taking its subsets as values. Obviously, superposition in the usual sense does not work when working with multifunctions. Therefore, we need a new definition of superposition. Two ways of defining superposition are usually considered: the first is based on the union of subsets of the set $A$, and in this case the closed sets containing all the projections are called multiclones, and the second is the intersection of the subsets of $A$, and the closed sets containing all projections are called partial ultraclones. The set of multifunctions on $A$ on the one hand contains all the functions of $|A|$-valued logic and on the other, is a subset of functions of $2^{|A|}$-valued logic with superposition that preserves these subsets. For functions of $k$-valued logic, the problem of their classification is interesting. One of the known variants of the classification of functions of $k$-valued logic is one in which functions in a closed subset $B$ of a closed set $M$ can be divided according to their belonging to the classes that are complete in $M$. In this paper, the subset of $B$ is the set of all Boolean functions, and the set of $M$ is the set of all multifunctions on the two-element set, and the partial maximal ultraclones are pre-complete classes.

Détail

Keywords: multifunction, clone, ultraclone
Mots-clés : superposition, maximal clone.

Bibliographie

[1] Badmaev S. A., Sharankhaev I. K., “On Maximal Clones of Partial Ultrafunctions on a Two-element Set”, The Bulletin of Irkutsk State University. Series Mathematics, 16 (2016), 3–18 (in Russian) | Zbl

[2] Badmaev S. A., “A Completeness Criterion of Set of Multifunctions in Full Partial Ultraclone of Rank 2”, Siberian Electronic Mathematical Reports, 15 (2017), 450–474 (in Russian) | DOI | MR

[3] Zamaratskaya S. V., Panteleev V. I., “On Maximal Clones of Ultrafunctions of Rank 2”, The Bulletin of Irkutsk State University. Series Mathematics, 15 (2016), 26–37 (in Russian) | Zbl

[4] Zamaratskaya S. V., Panteleev V. I., “Classification and Types of Bases of All Ultrafunctions on Two-Element Set”, The Bulletin of Irkutsk State University. Series Mathematics, 16 (2016), 58–70 (in Russian) | Zbl

[5] Zinchenko A. S., Panteleev V. I., “On Classes of Hyperfunctions of Rank 2 Generated by Maximal Multiclones”, The Bulletin of Irkutsk State University. Series Mathematics, 21 (2017), 61–76 (in Russian) | DOI | Zbl

[6] Kazimirov A. S., Panteleyev 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. Series Mathematics, 7 (2014), 61–78 (in Russian) | Zbl

[7] Kazimirov A. S., Panteleyev V. I., “On the Classes of Boolean Functions Generated by Maximal Multiclones”, The Bulletin of Buryat State University. Mathematics and Informatics, 9 (2015), 16–22 (in Russian)

[8] Panteleyev V. I., “On Two Maximal Multiclones and Partial Ultraclones”, The Bulletin of Irkutsk State University. Series Mathematics, 5:4 (2012), 46–53 (in Russian) | Zbl

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

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

[11] 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 | DOI

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