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. Ее также называют функцией кратности или функцией числа экземпляров мультимножества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), а значит, является отношением предпорядка.