Minimal Partial Ultraclones on a Two-Element Set

S. A. Badmaev   ; I. K. Sharankhaev

The Bulletin of Irkutsk State University. Series Mathematics, Tome 9 (2014), pp. 3-9

Résumé

Set of functions from a finite set $A$ to set of all subsets of $ A $ is a natural generalization of the set of many-valued functions on $ A $ ($k$-valued logic functions). These generalized functions, which are called multifunctions, often are regarded as incompletely defined functions. Partial functions, hyperfunctions, ultrafunctions, partial hyperfunctions, partial ultrafunctions on $A$ are arised depending on the type of multifunctions and superposition. In the theory of discrete functions the classical problem is description of lattice of clones — sets of functions that are closed with respect to superposition and contain all projections. Full description of a lattice is obtained only for Boolean functions by Emil Post in 1921. Thus this problem remains open more than 90 years for other discrete functions. Because of difficulty of this problem lattice fragments are studied, for example, the minimum and maximum elements, different intervals. In particular, we note that the descriptions of all minimal clones are known for Boolean functions, 3-valued logic functions, partial functions on two-element and three-element sets, hyperfunctions and partial hyperfunctions on a two-element set. In this paper we consider ultrafunctions and partial ultrafunctions on a two-element set. A description of all minimal clones for these classes of multifunctions is got.

Détail

Keywords: minimal clone; partial ultraclone; multifunction; partial ultrafunction; superposition.

Bibliographie

[1] Alekseev V. B., Voronenko A. A., “On Some Closed Sets in Partial Two-Valued Logic”, Discrete Mathematics and Applications, 4:5 (1994), 401–419 | DOI | MR | Zbl

[2] Panteleyev V. I., “Completeness Criterion for Incompletely Defined Boolean Functions”, Vestnik Samar. Gos. Univ. Est.-Naush. Ser., 2009, no. 2(68), 60–79 (in Russian)

[3] Panteleyev V. I., “On Two Maximal Multiclones and Partial Ultraclones”, Izvestiya Irk. Gos. Univ. Ser. Matematika, 5:4 (2012), 46–53 (in Russian) | MR

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

[5] Freivald R. V., “Completeness Criterion for Partial Functions of Algebra Logic and Many-valued Logics”, Dokl. Akad. Nauk of USSR, 167 (1967), 1249–1250 (in Russian) | Zbl

[6] F. Börner, L. Haddad, R. Pöschel, “Minimal partial clones”, Bulletin of the Austral. Math. Soc., 44:3 (1991), 405–415 | DOI | MR | Zbl

[7] F. Börner, L. Haddad, R. Pöschel, “A note on minimal partial clones”, Proceedings of 21th IEEE International Symposium on Multiple-Valued Logic, ISMVL (1991), 262–267

[8] B. Csákány, “All minimal clones on the three-element set”, Acta cybernetica, 1983, no. 6, 227–238 | MR

[9] J. Pantovic, G. Vojvodic, “Minimal partial hyperclones on a two-element set”, Proceedings of 34th IEEE International Symposium on Multiple-Valued Logic, ISMVL (2004), 115–119

[10] E. L. Post, “Introduction to a general theory of elementary propositions”, American Journal of Math., 43 (1921) | DOI | MR | Zbl

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

[12] I. G. Rosenberg, “Minimal clones I: the five types”, Lectures in Universal Algebra, Colloq. Math. Soc. J. Bolyai, 43, 1983, 405–427 | MR