Минимальные частичные ультраклоны на двухэлементном множестве
Авторы: | С. А. Бадмаев, И. К. Шаранхаев |
Аннотация: | Множество функций, определенных на конечном множестве A и принимающих в качестве значений подмножества множества A, является естественным обобщением множества конечнозначных функций на A (функций k-значной логики). Такие «обобщенные» функции, которые в последнее время принято называть мультифункциями, часто рассматривают как не всюду определенные функции, т. е. функции, определенные не на всех наборах. Для этого в мультифункциях неопределенности можно понимать как некоторые подмножества основного множества A. В зависимости от вида мультифункций и соответствующей им суперпозиции возникают частичные функции, гиперфункции, ультрафункции, частичные гиперфункции, частичные ультрафункции на A. В теории дискретных функций классической является задача описания решетки клонов – множеств функций, замкнутых относительно операции суперпозиции и содержащих все функции-проекции. Полное описание такой решетки получено только для булевых функций. Это было сделано Эмилем Постом в 1921 году. Таким образом, для других дискретных функций данная проблема остается открытой уже более 90 лет. В связи с трудностью решения этой задачи изучается не вся решетка целиком, а только ее отдельные фрагменты, например, минимальные и максимальные элементы, различные интервалы. В частности, отметим, что описания всех минимальных клонов известны для булевых функций, функций 3-значной логики, частичных функций на двухэлементном и трехэлементном множествах, гиперфункций и частичных гиперфункций на двухэлементном множестве. В настоящей работе рассматриваются ультрафункции и частичные ультрафункции на двухэлементном множестве. Дано описание всех минимальных клонов для этих классов мультифункций. |
Ключевые слова: | минимальный клон; частичный ультраклон; мультифункция; частичная ультрафункция; суперпозиция |
УДК: | 519.716 |
Литература: |
1. Алексеев В. Б. О некоторых замкнутых классах в частичной двузначной логике / В. Б. Алексеев, А. А. Вороненко // Дискрет. математика. — 1994. – Т. 6, вып. 4. – С. 58–79. 2. Пантелеев В. И. Критерий полноты для доопределяемых булевых функций / В. И. Пантелеев // Вестн. Самар. гос. ун-та. Естественнонауч. сер. – 2009. – №2 (68). – С. 60–79. 3. Пантелеев В. И. О двух максимальных мультиклонах и частичных ультраклонах / В. И. Пантелеев // Изв. Иркут. гос. ун-та. Сер. Математика. – 2012. – Т. 5, № 4. – C. 46–53. 4. Тарасов В. В. Критерий полноты для не всюду определенных функций алгебры логики / В. В. Тарасов // Проблемы кибернетики. – М. : Наука, 1975. – Вып. 30. – С. 319–325. 5. Фрейвалд Р. В. Критерий полноты для частичных функций алгебры логики и многозначной логики / Р. В. Фрейвалд // Докл. АН СССР. – 1966. – Т. 167. – С. 1249–1250. 6. Borner F. Minimal partial clones / F. Borner, L. Haddad, R. P¨oschel // Bulletin of the Austral. Math. Soc. – 1991. – Vol. 44, N 3. – P. 405–415. 7. Borner F. A note on minimal partial clones / F. Borner, L. Haddad, R. P¨oschel // Proceedings of 21th IEEE International Symposium on Multiple-Valued Logic (ISMVL). – 1991. – P. 262–267. 8. Csakany B. All minimal clones on the three-element set / B. Csakany // Acta cybernetica. – 1983. – N 6. – P. 227–238. 9. Pantovic J. Minimal partial hyperclones on a two-element set / J. Pantovic, G. Vojvodic // Proceedings of 34th IEEE International Symposium on Multiple-Valued Logic (ISMVL). – 2004. – P. 115–119. 10. Post E. L. Introduction to a general theory of elementary propositions / E. L. Post // American Journal of Math. – 1921. – Vol. 43. 11. Post E. L. Two-valued iterative systems of mathematical logic / E. L. Post // Annals of Math. Studies. – Princeton : Univer. Press, 1941. – Vol. 5. – 122 p. 12. Rosenberg I. G. Minimal clones I: the five types / I. G. Rosenberg // In Lectures in Universal Algebra 43, Colloq.Math. Soc. J. Bolyai. – 1983. – P. 405–427. |