О сложности стандартных форм мультифункций

Если рассматривать дискретные функции на множестве $A$, то мультифункции можно определить как функции на множестве $2^A$, при этом значения мультифункций для значений аргументов из $A$ задаются, а для значений, не являющихся одноэлементными множествами, определяются как объединение всех значений мультифункции на одноэлементных множествах. Таким же образом определяется суперпозиция для мультифункций.
Мультифункции являются обобщением различных моделей неопределенности, частичных и гиперфункций. Такие модели можно применять, например, при работе с неполной и противоречивой информацией в интеллектуальных системах.
Для мультифункций можно определить стандартные формы через мультифункцию пересечения. Представление мультифункции в классе стандартных форм не является единственным. Для них можно естественным образом ввести понятие сложности по количеству компонент пересечения.
В данной статье рассматривается связь между мультифункциями, принимающими всего два значения, и булевыми функциями. Показано, что сложность стандартных форм любой из таких мультифункций совпадает с длиной дизъюнктивной нормальной формы соответствующей булевой функции. В статье получена верхняя оценка сложности стандартных форм мультифункций, а также приведена последовательность мультифункций, сложность которой совпадает с этой верхней оценкой. Таким образом, получено значение сложности класса $n$-местных мультифункций (функции Шеннона). Также предложен алгоритм минимизации мультифункций ранга $2$ от $4$ и менее аргументов, основанный на последовательном переборе формул всё большей сложности. С помощью данного алгоритма найдены сложности всех $4$-местных мультифункций ранга $2$.