![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Понятие мультимножества
Мы рассмотрели конечные множества, в которых отсутствуют повторяющиеся элементы. В кортежах возможны повторяющиеся элементы, но при этом значение каждого элемента определяется его местоположением. В задачах искусственного интеллекта начинают использоваться объекты с повторяющимися элементами. Л.Б. Петровский такие элементы назвал мультимножествами и разработал основы их теории. Мультимножество - это множество с повторяющимися элементами, где один и тот же элемент может присутствовать многократно, особенностью мультимножества является понятие кратности вхождения элемента. Элементы мультимножеств будем обозначать строчными буквами с подстрочным индексом М: 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, …}, xi Группу одинаковых элементов kixi, называют компонентой мультимножества, элементы xi, входящие в компоненту kixi, – экземплярами элементов мультимножества. Функция ki принимающая числовые значения, определяет число вхождений элемента xi Говорят, что элемент xi принадлежит мультимножеству AM (обозначается xi Если все мультимножества семейства Θ (AM) = { A1M, A2M, …} образуются из элементов одного и того же множества G = {x1, x2, …}, то множество G называется порождающим множеством или доменом для семейства Θ (AM). В качестве порождающего множества G может выступать любое непустое (конечное или бесконечное) множество. Основными характеристиками мультимножества являются мощность и размерность. Мощность мультимножества AM определяется как общее число экземпляров всех его элементов | AM |=card AM, а размерность мультимножества А – как общее число различных элементов / AM / = dim AM. Размерность мультимножества не превосходит его мощности и мощности домена / AM / Высотой или пиковым значением мультимножества АM называется максимальное значение его функции кратности ki, а элемент xA*, для которого функция кратности kA максимальна, - пиком или пиковым элементом мультимножества АM. Мультимножество удобно изображать графически в виде ступенчатой гистограммы, по оси абсцисс которой расположены элементы основного множества A или домена G, а по оси ординат отложены значения ki (xi) функции кратности, показывающие количество экземпляров элемента xi в мультимножестве AM. Таким образом, каждый столбец гистограммы соответствует определенной компоненте мультимножества АM. Ширина гистограммы равна размерности / АM / мультимножества, а высота гистограммы есть высота мультимножества АM. Мощность мультимножества | АM | будет численно равна площади фигуры, ограниченной гистограммой. Для мультимножеств справедливы теоретико-множественные понятия, введенные для множеств. Рассмотрим возможные способы сопоставления мультимножеств, обусловленные особенностями их различных характеристик. Мультимножества АM и BM называются равными (AM = BM), если ki (xi) = kj (xj) для всех элементов xi, xj Мультимножества A и B называют: · равномощными, если |A|=|B|. · равноразмерными, если /А/=/В/. · равными, если они равномощны и равноразмерны. Говорят, что мультимножество BM содержится или включено в мультимножество АM (AM Включение мультимножества обладает свойствами рефлексивности (AM
|