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

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

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

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

AM = {a, b, a, d, e, c, a, b, h, h}, BM = {d, d, e, b, b, d, e, e, h}, CM = {a, a, d, a, c, a, a, e, c, c, g, g, g}.

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

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

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

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

Мультимножеством АМ, определенном на множестве А={x1, x2, …}, вес элементы хi, которого различны, называется совокупность групп одинаковых элементов

AM={k1x1, k2x2, …}, xiA.

Группу одинаковых элементов kixi, называют компонентой мультимножества, элементы xi, входящие в компоненту kixi, – экземплярами элементов мультимножества. Функция kiпринимающая числовые значения, определяет число вхождений элемента xiAв мультимножество AM.

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

Если все мультимножества семейства Θ(AM) = {A1M, A2M, …} образуются из элементов одного и того же множества G = {x1, x2, …}, то множество G называется порождающим множеством или доменом для семейства Θ(AM). В качестве порождающего множества G может выступать любое непустое (конечное или бесконечное) множество.

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

|AM |=cardAM,

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

/AM / = dimAM.

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

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

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

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

Рассмотрим возможные способы сопоставления мультимножеств, обусловленные особенностями их различных характеристик. Мультимножества АM и BM называются равными (AM = BM), если ki(xi) = kj(xj) для всех элементов xi, xjG, ki(xi)АM,kj(xj)BM. В противном случае эти мультимножества неравны. Для равных мультимножеств имеем |A| = |B|, /A/ = /B/.

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

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

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

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

Говорят, что мультимножество BMсодержится или включено в мультимножество АM(AMBM), если kjxjkixi,для каждого элемента xi, xjG, kixiAM, kjxjBM. Мультимножество BM называемся тогда подмультимножеством мультимножества AM, а мультимножество AM– надмультимножествоммультимножества BM.

Включение мультимножества обладает свойствами рефлексивности (AMАM) и транзитивности (AMBM, BMCMAMCM), а значит, является отношением предпорядка.