RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Иркутского государственного университета. Серия «Математика» // Архив

Известия Иркутского государственного университета. Серия Математика, 2014, том 9, страницы 3–9 (Mi iigum195)

Эта публикация цитируется в 1 статье

Минимальные частичные ультраклоны на двухэлементном множестве

С. А. Бадмаев, И. К. Шаранхаев

Бурятский государственный университет

Аннотация: Множество функций, определенных на конечном множестве $A$ и принимающих в качестве значений подмножества множества $A$, является естественным обобщением множества конечнозначных функций на $A$ (функций $k$-значной логики). Такие «обобщенные» функции, которые в последнее время принято называть мультифункциями, часто рассматривают как не всюду определенные функции, т. е. функции, определенные не на всех наборах. Для этого в мультифункциях неопределенности можно понимать как некоторые подмножества основного множества $A$. В зависимости от вида мультифункций и соответствующей им суперпозиции возникают частичные функции, гиперфункции, ультрафункции, частичные гиперфункции, частичные ультрафункции на $A$.
В теории дискретных функций классической является задача описания решетки клонов — множеств функций, замкнутых относительно операции суперпозиции и содержащих все функции-проекции. Полное описание такой решетки получено только для булевых функций. Это было сделано Эмилем Постом в 1921 году. Таким образом, для других дискретных функций данная проблема остается открытой уже более 90 лет. В связи с трудностью решения этой задачи изучается не вся решетка целиком, а только ее отдельные фрагменты, например, минимальные и максимальные элементы, различные интервалы. В частности, отметим, что описания всех минимальных клонов известны для булевых функций, функций 3-значной логики, частичных функций на двухэлементном и трехэлементном множествах, гиперфункций и частичных гиперфункций на двухэлементном множестве.
В настоящей работе рассматриваются ультрафункции и частичные ультрафункции на двухэлементном множестве. Дано описание всех минимальных клонов для этих классов мультифункций.

Ключевые слова: минимальный клон; частичный ультраклон; мультифункция; частичная ультрафункция; суперпозиция.

УДК: 519.716



© МИАН, 2024