Операции над мультимножествами

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

Объединением мультимножеств A_M и B_M называется мультимножество, состоящее из всех элементов, которые присутствуют хотя бы в одном из мультимножеств, и кратность каждого элемента равна максимальной кратности соответствующих элементов в объединяемых мультимножествах:

C_M= A_M B_M= {max(k_ix_i, k_jx_j)}, k_ix_i A_M, k_jx_j B_M.

Другими словами, производится попарное сравнивание каждого экземпляра мультимножеств и в каждой паре выбирается экземпляр с наибольшим значением функции кратности.

Пересечением мультимножеств A_M и B_M называется мультимножество, состоящее из всех элементов, которые одновременно присутствуют в каждом из мультимножеств, и кратность каждого элемента равна минимальной кратности соответствующих элементов в пересекаемых мультимножествах:

C_M= A_M B_M= {min(k_ix_i, k_jx_j)}, k_ix_i A_M, k_jx_j B_M.

Другими словами, производится попарное сравнивание каждого экземпляра мультимножеств и в каждой паре выбирается экземпляр с наименьшим значением функции кратности.

Арифметической суммой мультимножеств A_M и B_M называется мультимножество, состоящее из всех элементов, которые присутствуют хотя бы в одном из мультимножеств, и кратность каждого элемента равна сумме кратностей соответствующих элементов в складываемых мультимножествах:

C_M= A_M+B_M= {kx | kx = k_ix_i + k_jx_j}, k_ix_i A_M, k_jx_j B_M.

Операции объединение, пересечение и арифметическое сложение можно выполнять для произвольного числа мультимножеств.

Арифметической разностью мультимножеств A_M и B_M называется мультимножество, состоящее из тех элементов мультимножества A_M, кратность которых превышает кратность соответствующих элементов в мультимножестве B_M. Кратность каждого элемента результирующего множества равна разности кратностей соответствующих элементов в вычитаемых мультимножествах:

C_M= A_M-B_M= {kx | kx = k_ix_i-k_jx_j, если k_i> k_j; 0, в противном случае}, k_ix_i A_M, k_jx_j B_M.

A_M B_M A_M- B_M =

Симметрической разностью мультимножеств A_M и B_M называется мультимножество, состоящее из тех элементов мультимножества A_Mи B_M, кратности которых различны. Кратность каждого элемента результирующего множества равна модулю разности кратностей соответствующих элементов в вычитаемых мультимножествах:

C_M= A_M\B_M= {kx | kx = |k_ix_i-k_jx_j|}, k_ix_i A_M, k_jx_j B_M.

Арифметическая и симметрическая разности мультимножеств применима только к двум мультимножествам.

Дополнением мультимножества A_M до универсума U называется мультимножество, состоящее из тех элементов, кратность которых равна разности кратностей соответствующих элементов в универсуме U и дополняемом мультимножестве A_M. Под универсумом в данном случае понимается некоторое мультимножество U, такое, что все остальные мультимножества являются подмультимножествами данного множества U.

A_M’=U-A_M={k_A’x | k_Ux-k_Ax, x U}

Из определений пустого мультимножества и дополнения мультимножества следует, что пустое мультимножество и универсум U взаимно дополняют друг друга: ’ = U, U’= .

Арифметической произведением мультимножеств A_M и B_M называется мультимножество, состоящее из элементов, которые одновременно присутствуют в каждом из мультимножеств, и их кратность равна произведению кратностей соответствующих элементов в перемножаемых мультимножествах:

C_M= A_M B_M= {kx | kx = |k_ix_i k_jx_j|}, k_ix_i A_M, k_jx_j B_M.

Прямым произведением мультимножеств A_M и B_M называется мультимножество, состоящее из всех упорядоченных пар элементов < x_i, x_j>,

таких, что первый элемент каждой пары является элементом первого сомножителя x_i A_M, второй элемент пары - элементом второго сомножителя x_j B_Mи кратность каждой пары < x_i, x_j> равна произведению кратностей элементов x_i и x_jв перемножаемых мультимножествах:

C_M= A_M B_M= {k_{A× B}< x_i, x_j> | k_{A× B} = k_ix_i k_jx_j}, x_i A_M, x_j B_M.

По аналогии с множествами, для мультимножеств также можно сформулировать некоторые правила выполнения операций:

(A B)’ = A’ B’;

(A B)’ = A’ B’;

(A+B)’ = A’ – B = B’ – A;

(A – B)’ = A’ + B;

A’ – B’ = B – A;

A + B = (A B) + (A B);

A\B = (A B) – (A B) = A’\B’;

(A – B) (B – A) = ;

A B = (A + B) – (A B) = (A B) + A\B = A + (B – A) = B + (A – B);

A B = (A + B) – (A B) = (A B) – A\B = A – (A – B) = B – (B – A);

A – B = (A B) – B = A – (A B) = (A B)\B = A\(A B);

A\B = (A B) – (A B) = (A – B) + (B – A) = (A – B) (B – A) = (A + B) – 2·(A B);

A + B = (A B) + (A B) = A\B + 2·(A B).