Аннотация:
Мультиоперации ранга k определяются как функции на множестве всех подмножеств некоторого k-элементного множества A, при этом значения мультиоперации на наборах из A задаются, а на остальных наборах определяются как объединение всех значений мультиопераций на соотвествующих наборах из A. Таким же образом определяется суперпозиция для мультиопераций.
Мультиоперации являются обобщением различных моделей неопределенности, частичных и гиперопераций.
Для мультиопераций можно определить стандартные формы через мультиоперацию пересечения. Для них можно естественным образом ввести понятие сложности по количеству компонент пересечения.
Ранее была найдена сложность стандартных форм мультиопераций ранга 2 сведением к длине наикратчайшей ДНФ. В данной работе обобщается предыдущий результат на мультиоперации ранга k.
|
