Понятие мультимножества

Мы рассмотрели конечные множества, в которых отсутствуют повторяющиеся элементы. В кортежах возможны повторяющиеся элементы, но при этом значение каждого элемента определяется его местоположением. В задачах искусственного интеллекта начинают использоваться объекты с повторяющимися элементами. Л.Б. Петровский такие элементы назвал мультимножествами и разработал основы их теории.

Мультимножество - это множество с повторяющимися элементами, где один и тот же элемент может присутствовать многократно, особенностью мультимножества является понятие кратности вхождения элемента. Элементы мультимножеств будем обозначать строчными буквами с подстрочным индексом М: a_M, b_M, …; а мультимножества – прописными буквами с подстрочным индексом М: A_M, B_M, …

Примером мультимножеств могут служить, например, следующие совокупности элементов a, b, c, d, e, f, g, h:

A_M = {a, b, a, d, e, c, a, b, h, h}, B_M = {d, d, e, b, b, d, e, e, h}, C_M = {a, a, d, a, c, a, a, e, c, c, g, g, g}.

Порядок следования элементов в мультимножестве считается несущественным. Тогда приведенные мультимножества A, B, C можно переписать следующим образом:

A_M = {3a, 2b, c, d, e, 2h}

Отметим, что отсутствующие элементы не указываются в записи мультимножества.

Формальное определение мультимножества, данное А.Б Петровским:

Мультимножеством А_М, определенном на множестве А={x₁, x₂, …}, вес элементы х_i, которого различны, называется совокупность групп одинаковых элементов

A_M={k₁x₁, k₂x₂, …}, x_i A.

Группу одинаковых элементов k_ix_i, называют компонентой мультимножества, элементы x_i, входящие в компоненту k_ix_i, – экземплярами элементов мультимножества. Функция k_i принимающая числовые значения, определяет число вхождений элемента x_i A в мультимножество A_M. Ее также называют функцией кратности или функцией числа экземпляров мультимножестваA_M.

Говорят, что элемент x_i принадлежит мультимножеству A_M (обозначается x_i A_M) и в мультимножестве A_M имеется ровно kэкземпляров элемента x_i, тогда и только тогда, когда кратность элемента x_i равна k_ix_i > 0. Когда кратность элемента x_i равна нулю k_ix_i = 0, тогда говорят, что элемент x_i не содержится в мультимножестве A_M (обозначается x_i A_M). Тем самым принадлежность элемента x_i мультимножеству A_M определяется значением функции кратности.

Если все мультимножества семейства Θ (A_M) = { A1_M, A2_M, …} образуются из элементов одного и того же множества G = {x₁, x₂, …}, то множество G называется порождающим множеством или доменом для семейства Θ (A_M). В качестве порождающего множества G может выступать любое непустое (конечное или бесконечное) множество.

Основными характеристиками мультимножества являются мощность и размерность. Мощность мультимножества A_M определяется как общее число экземпляров всех его элементов

| A_M |=card A_M,

а размерность мультимножества А – как общее число различных элементов

/ A_M / = dim A_M.

Размерность мультимножества не превосходит его мощности и мощности домена / A_M / |A_M|, / A_M / |G |. Мощность мультимножества | A_M | в общем случае не связана с мощностью домена |G|. Конечные мультимножества, имеющие мощность т и состоящие из т элементов (cчитая повторения), называют m-кардинальными мультимножествами или т-мультимножествами, а имеющие размерность п и состоящие из п компонент - n-мерными мультимножествами.

Высотой или пиковым значением мультимножества А_M называется максимальное значение его функции кратности k_i, а элемент x_A*, для которого функция кратности k_A максимальна, - пиком или пиковым элементом мультимножества А_M.

Мультимножество удобно изображать графически в виде ступенчатой гистограммы, по оси абсцисс которой расположены элементы основного множества A или домена G, а по оси ординат отложены значения k_i (x_i) функции кратности, показывающие количество экземпляров элемента x_i в мультимножестве A_M. Таким образом, каждый столбец гистограммы соответствует определенной компоненте мультимножества А_M. Ширина гистограммы равна размерности / А_M / мультимножества, а высота гистограммы есть высота мультимножества А_M. Мощность мультимножества | А_M | будет численно равна площади фигуры, ограниченной гистограммой.

Для мультимножеств справедливы теоретико-множественные понятия, введенные для множеств.

Рассмотрим возможные способы сопоставления мультимножеств, обусловленные особенностями их различных характеристик. Мультимножества А_M и B_M называются равными (A_M = B_M), если k_i (x_i) = k_j (x_j) для всех элементов x_i, x_j G, k_i (x_i) А_M, k_j (x_j) B_M. В противном случае эти мультимножества неравны. Для равных мультимножеств имеем |A| = |B|, /A/ = /B/.

Мультимножества A и B называют:

· равномощными, если |A|=|B|.

· равноразмерными, если /А/=/В/.

· равными, если они равномощны и равноразмерны.

Говорят, что мультимножество B_M содержится или включено в мультимножество А_M (A_M B_M), если k_jx_j k_ix_i, для каждого элемента x_i, x_j G, k_ix_i A_M, k_jx_j B_M. Мультимножество B_M называемся тогда подмультимножеством мультимножества A_M, а мультимножество A_M – надмультимножеством мультимножества B_M.

Включение мультимножества обладает свойствами рефлексивности (A_M А_M) и транзитивности (A_M B_M, B_M C_M A_M C_M), а значит, является отношением предпорядка.