Набор операций для множеств

Набор операций называют функционально полным, если он позволяет реализовать любой алгоритм вычислений. Выбор функционально полного набора операций не является однозначным. Следующий вариант такого выбора хотя и является избыточным, но удобным для вычислений:

- операция проверки принадлежности объекта данному множеству;

- операция включения нового элемента множества;

- операция исключения элемента из множества;

- операция объединения;

- операция пересечения;

- операция дополнения.

Проверка принадлежности

Результатом выполнения операции xÎA является логическое значение "Истина", если x принадлежит множеству A и значение "Ложь", если нет.

Включение

Операция обозначается как A+x или AÈx, результатом является множество, в которое добавлен элемент x.

Исключение

Операция обозначается как A - x или A \ x. Результатом формируется путем исключения x из множества A. Если xÏA, результатом является множество A.

Объединение

Операция обозначается как AÈB. Результатом является множество, в которое включены все элементы из A и из B: AÈB = {x | xÎA или xÎB}.

Пересечение

Операция обозначается как AÇB. Результатом является множество, в которое включены только те элементы, которые принадлежат множеству A и, в то же время, множеству B:

AÇB = {x | xÎA и xÎB}.

Дополнение

Операция обозначается как ØA. Результатом является множество, в которое включены те элементы универсума, которые не принадлежат A: ØA = {x | xÎU и xÏA }. Эта операция определена только лишь в том случае, когда задан универсум.

Алгоритмы выполнения основных операций над множествами и их эффективность