Глава 7. Основные понятия теории мультимножеств

Понятие мультимножества, компоненты мультимножеств, определение и способы задания мультимножеств,основные характеристики мультимножеств, операции над мультимножествами

ЦЕЛИ

Освоив эту главу студенты должны:

• иметь понятия о мультимножествах;

• знать основные характеристики мультимножеств;

• знать способы задания мультимножеств;

• уметь выполнять операции над мультимножествами.

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

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

Мультимножество - это множество с повторяющимися элементами, где один и тот же элемент может присутствовать многократно. Особенностью мультимножества является понятие кратности вхождения элемента. Элементы мультимножеств будем обозначать строчными буквами с подстрочным индексом М: a_М, b_М, ..., мультимножества - прописными буквами с подстрочным индексом М – А_М, В_М, ...

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

A_М = {a, b, a, d, e, c, a, b, h, h}, B_М = {d, d, e, b, b, d, e, e, h}, C_М = {a, a, d, a, c, a, a, e, c, c, g, g, g}.

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

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

B_М = {2b, 3d, 3e, h },

C_М = {5a, 3c, d, e, 3g},

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

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

A_М = {k₁x₁, k₂x₂, ...}, x_i  А.

Группу одинаковых элементов k_ix_i называют компонентой мультимножества, элементы x_i, входящие в компоненту k_ix_i, - экземплярами элементов мультимножества. Функция k_i, принимающая числовые значения, определяет число вхождений элемента x_i  А в мультимножество А_М или «вес» элемента x_i в мультимножестве А_М. Ее также называют функцией кратности или функцией числа экземпляров мультимножества А_М. Другими словами, мультимножество - это множество, состоящее из различных групп одинаковых экземпляров элементов.

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

Если все мультимножества семейства (А_М) = {А1_М, А2_М, ...} образуются из элементов одного и того же множества G = {x₁, x₂, ...}, то множество G называется порождающим множеством или доменом для семейства (А_М). В качестве порождающего множества G может выступать любое непустое (конечное или бесконечное) множество.

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

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

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

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

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

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

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

Мультимножества А и В называют равномощными, если |А| = |В|. Например, мультимножества A_М = {3a, 2b}, B_М = {2a, 3b} являются равномощными, так как мощность мультимножества A_М = 5 и мощность мультимножества B_М = 5, а мультимножества C_М = {3d, e}, D_М = {e, 2d} – неравными, т.к. 4  3.

Мультимножества А и В называют равноразмерными, если /A/ = /B/. Например, мультимножества A_М = {3a, 2b, c}, B_М = {2a, 2b, 2c} являются равноразмернымимощными, так как число различных экземпляров мультимножества /A_М / = /B_М / = 3, а мультимножества C_М = {3d, e}, D_М = {e, 2d} – неравными, т.к. 4  3.

Мультимножества А_M и В_M называют равными, если они равномощны и равноразмерны.

Говорят, что мультимножество В_M содержится или включено в мультимножество А_M (В_M  А_M), если k_jx_j  k_ix_i, для каждого элемента x_i, x_j  G, k_ix_i  А_М, k_jx_j  B_М. Мультимножество В_M называется тогда подмультимножеством мультимножества А_M, а мультимножество А_M - надмультимножеством мультимножества В_M. В этом случае |В|  |A|, /B/  /A/. Как и в случае обычных множеств, одновременное выполнение условий В_M  А_M и А_M  В_M влечет равенство мультимножеств А_M = В_M.

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