6

Размещено на http://www.allbest.ru/

Киевский национальный университет имени Тараса Шевченко

Решетка мультимножеств

Буй Д.Б., д.ф. - м.н., с.н с.

Богатырёва Ю.А., аспирантка

Впервые понятие “мультимножество” (multiset) было предложено Н.Г. Де Брейном в частной корреспонденции с Д. Кнутом. В 70-х годах этот термин получил широкое распространение и сейчас является стандартным термином для обозначения совокупностей с повторениями [1, 11].

Совокупности с повторениями (коллекции) традиционно изучались в комбинаторике под названием “сочетания с повторениями” [15, с.172].Д. Кнут был одним из первых, кто обратил внимание на то, что существует необходимость рассмотрения мультимножества как отдельного математического объекта. В своей книге [3, с.536] он дает содержательное определение мультимножества и определяет операции объединения, пересечения и сложение мультимножеств.

В [5, с.225] также приводится определение мультимножества, но в терминах табличных баз данных: мультимножество рассматривается как совокупность кортежей, в которых возможны повторения. Кроме того, над мультимножествами вводятся операции объединения, пересечения, разности, проекции, декартового произведения, соединение и ряд дополнительных операций (агрегирование, группирование, сортировка).

Д. Кнут использует мультимножества в контекстно-свободных мультиязыках. В статье [2] он говорит, что мультиязык - это мультимножество строк.

Довольно широко мультимножества используются в SQL-подобных языках. Так, начиная со стандарта SQL: 2003, введен конструктор типа MULTISET (мультимножество), что открывает новые возможности для применения языка, в частности, в объектном стиле [10].

В языке ограничений OCL также определен такой структурный тип, как мультимножество (Bug), который является одним из разновидностей коллекций, и поддерживается большой набор операций над значениями коллекционных типов (select, collect, exists, forAll, size, union, intersect, symmetricDifference и др.) [7].

Мультимножества используются в математике, а именно в - исчислении [3], при определении основных понятий сетей Петри [4, 13], в задачах распознавания символов [14], а также в новой области знаний - так называемых вычислениях на ДНК [8]. Поэтому возникает необходимость развития теории мультимножеств.

Заметка посвящена построению решетки мультимножеств и соответствующей абстрактной решетки, сигнатура которой состоит из операций объединения и пересечения мультимножеств.

Введем формальное определение мультимножества. Для этого обозначим чeрез множество натуральных чисел с нулем и - множество натуральных чисел без нуля.

Пусть - некоторое множество (в классическом канторовском понимании). Тогда по определению мультимножество с основой - это функция вида: [3, 12].

Зафиксируем для дальнейших рассмотрений - универсум элементов основ мультимножеств. Тогда булеан есть универсум основ мультимножеств.

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

Характеристической функцией мультимножества называется функция вида , значение которой задается следующей кусочной схемой:

для всех [11, 12].

Очевидно, что различные мультимножества имеют разные характеристические функции, т.е. по характеристической функции соответствующее мультимножество восстанавливается однозначно.

Введем бинарное отношение включения на мультимножествах.

Мультимножество включается в мультимножество (обозначается ), если для их характеристических функций выполняется утверждение: . Непосредственно проверяется, что введенное отношение является частичным порядком.

Если , то мультимножество называется подмультимножеством мультимножества , а мультимножество - надмультимножеством мультимножества [11].

Над мультимножествами определяются аналоги стандартных операций над множествами: объединение, пересечение, разность, симметрическая разность, дополнение и прямое произведение. Кроме этого, существует ряд операции, которые определяются лишь над мультимножествами (т.е. эти операции используют специфику мультимножеств) и не имеют прямых аналогов среди операций над множествами. Примерами служaт операции сложения, произведения и умножение числа на мультимножество. Дадим определение операций объединения и пересечения.

Операция мультимножествам и сопоставляет мультимножество , значение характеристической функции которого на произвольном аргументе d задается выражением:

Операция мультимножествам и сопоставляет мультимножество , значение характеристической функции которого на произвольном аргументе d задается выражением: .

Эти операции имеют стандартные свойства.

Лемма 1 (о идемпотентности, коммутативности и ассоциативности операций объединения и пересечения). Операции и идемпотентны (т.е. , для ), коммутативны и ассоциативны.

Доказательство вытекает из того, что теоретико-числовые операции , имеют те же самые свойства.

Лемма 2 (о законах поглощения для операций объединения и пересечения). Для произвольных мультимножеств и выполняются следующие законы поглощения: , .

Доказательство вытекает из того, что теоретико-числовые операции , удовлетворяют своим законам поглощения (, ).

Понятие абстрактной решетки и решетки будем использовать в понимании [9].

Предложение 1. Алгебра A; ,, где A - семейство мультимножеств, элементы основ которых принадлежат , является абстрактной решеткой.

Доказательство вытекает из лемм 1, 2.

Рассмотрим бинарное отношение . Из результов общей теории решеток [9, § 5, п.5.1, с.130; 15, § 8, с.154, теорема 3] вытекает, что это бинарное отношение является частичным порядком, и допускает следующее эквивалентное представление: .

Предложение 2. Семейство мультимножеств A с частичным порядком является решеткой, причем и .

Доказательство вытекает из результатов общей теории решеток [9, § 5; 15, §8, с.154, теорема 3].

Непосредственно проверяется, что порядок решетки совпадает с порядком включения мультимножеств .

Существует еще один способ доказательства того, что семейство мультимножеств с частичным порядком является решеткой.

Как отмечалось выше, операции и идемпотентны, коммутативны и ассоциативны. Таким образом, можно рассматривать две коммутативные идемпотентные полугруппы.

решетка мультимножество бинарный абстрактный

Используя хорошо известный результат теории решеток о связи коммутативных идемпотентных полугрупп и полурешеток (полуструктур) [15, §8, с.151, теорема 1], полугруппу по объединению можно превратить в верхнюю полурешетку, а полугруппу по пересечению - в нижнюю. Соответствующие частичные порядки верхней полурешетки и нижней полурешетки задаются выражениями:

, ,

причем , .

Непосредственно проверятся, что эти порядки совпадают с порядком включения мультимножеств .

Таким образом, семейство мультимножеств A с частичным порядком является одновременно и верхней, и нижней полурешеткой, т.е. решеткой.

Второй способ построения решетки мультимножеств явно не использовал законы поглощения. Нетрудно показать в общем случае, что порядки верхней и нижней полурешеток совпадают тогда и только тогда, когда выполняются законы поглощения.

Литература