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

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

Мультимножество - это множество с повторяющимися элементами, где один и тот же элемент может присутствовать многократно, особенностью мультимножества является понятие кратности вхождения элемента. Элементы мультимножеств будем обозначать строчными буквами с подстрочным индексом М: 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_iA.

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

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

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

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

|A_M |=cardA_M,

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

/A_M / = dimA_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_jG, k_i(x_i)А_M,k_j(x_j)B_M. В противном случае эти мультимножества неравны. Для равных мультимножеств имеем |A| = |B|, /A/ = /B/.

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

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

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

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

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

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