Алгебра кортежей — математическая система моделирования и анализа многоместных отношений.
Использование термина
В математической литературе термин «алгебра кортежей» используется в двух значениях. В одном из них под алгеброй кортежей понимается класс логических формул, применяемых для преобразования булевых функций в арифметические полиномы (Малюгин В. Д. Параллельные логические вычисления посредством арифметических полиномов. Москва. Физматлит. 1997).
Иное значение термина рассматривается в работах Б. А. Кулика — этот вариант излагается в данной статье.
Определение
Алгебра кортежей (АК) — это алгебраическая система, носителем которой является произвольная совокупность многоместных отношений, выраженных в специфических структурах (элементарный кортеж, C-кортеж, C-система, D-кортеж, D-система), называемых АК-объектами. Операции и отношения в АК полностью соответствуют операциям (пересечение, объединение, дополнение) и отношениям (принадлежность, включение, равенство) алгебры множеств. Кроме того, в состав операций АК добавлены четыре операции с атрибутами:
- переименование атрибутов;
- перестановка атрибутов;
- добавление нового фиктивного атрибута;
- элиминация атрибута из АК-объекта.
На чем основана АК
Законы АК основаны на сочетании законов алгебры множеств и свойств прямого произведения множеств.
Структуры АК
Обозначения
Имена АК-объектов содержат собственно имя, в некоторых случаях к имени добавляется заключенная в прямые скобки последовательность имен атрибутов, определяющих схему отношения, в которой задан этот АК-объект. Например, означает, что АК-объект задан в пространстве атрибутов и .
АК-объекты, заданные в одном пространстве атрибутов, называются однотипными.
Элементарный кортеж
- Элементарный кортеж в АК соответствует кортежу элементов в многоместных отношениях. Например, запись . означает, что — элементарный кортеж, при этом .
В АК элементарные кортежи являются элементами множеств (отношений), выраженных другими типами АК-объектов.
Компоненты
Остальные структуры формируются из множеств, являющихся подмножествами доменов атрибутов. Эти множества в АК называются компонентами. В их число входят две фиктивные компоненты:
- полная компонента — , равна домену соответствующего (по месту ее расположения в кортеже) атрибута (используется в C-кортежах и C-системах);
- пустое множество — , (используется в D-кортежах и D-системах).
C-кортеж
- C-кортеж — кортеж множеств, ограниченный прямыми скобками. Интерпретируется как множество элементарных кортежей, содержащихся в прямом произведении этих множеств. Например, означает, что и .
C-система
- C-система — объединение однотипных C-кортежей, выраженное в виде матрицы, ограниченной прямыми скобками.
Например, C-систему
можно представить как множество элементарных кортежей, вычисляемое по формуле
- .
D-кортеж
Прежде, чем определить D-кортеж, нужно определить диагональную C-систему.
- Диагональная C-система — C-система размерности , у которой все недиагональные компоненты равны
Пример:
- D-кортеж — отношение, равное диагональной C-системе, записанное в виде кортежа диагональных компонент и ограниченное перевернутыми квадратными скобками.
В частности, в формуле
правая часть равенства — D-кортеж.
D-система
- D-система — ограниченная перевернутыми квадратными скобками матрица компонент, которая интерпретируется как пересечение содержащихся в ней однотипных D-кортежей.
Так
Основные соотношения
Основные соотношения АК основаны на свойствах прямого произведения множеств.
Пусть заданы C-кортежи и
Тогда
- для любого C-кортежа если хотя бы одна компонента равна , то ;
- где дополнение компоненты в D-кортеже вычисляется относительно домена соответствующего атрибута;
- , если и только если для всех .
Операции с атрибутами
- Переименование атрибутов используется при замене переменных, в частности, в алгоритмах вычисления транзитивного замыкания бинарного отношения.
- Перестановка атрибутов — операция, при выполнении которой в матрице АК-объекта меняются местами столбцы. При этом в некоторых случаях (например, при обращении отношений) порядок атрибутов в схеме отношения остается неизменным.
- Добавление фиктивного атрибута осуществляется только в том случае, если добавляемый атрибут отсутствует в схеме отношения АК-объекта. При этом в C-кортежи и в C-системы в соответствующие столбцы добавляется фиктивные компоненты , а в D-кортежи и D-системы — фиктивные компоненты .
- Если в АК-объект вводится фиктивный атрибут, то эта процедура соответствует известному в исчислении предикатов правилу вывода, которое называется правилом обобщения. Например, если D-система
- соответствует формуле исчисления предикатов, то, добавив в этот АК-объект фиктивный атрибут , получим АК-объект
- который соответствует формуле , выводимой из формулы по правилу обобщения.
- Элиминация атрибута осуществляется так:
- из АК-объекта удаляется столбец, а из его схемы отношения — соответствующий атрибут.
- Доказано, что для C-кортежй и C-систем элиминация атрибута означает «навешивание» квантора в соответствующую формулу, а для D-кортежй и D-систем — квантора .
Связь алгебры кортежей с исчислением предикатов
- C-кортежу в исчислении предикатов соответствует конъюнкция одноместных предикатов с разными переменными. Например,
C-кортежу
соответствует логическая формула , где
- и — области определения переменных и ; .
- D-кортежу соответствует дизъюнкция одноместных предикатов с разными переменными. Например,
D-кортежу
соответствует логическая формула , где
- .
- C-системе соответствует дизъюнкция C-кортежей, D-системе — конъюнкция D-кортежей.
- Элементарный кортеж, входящий в состав непустого АК объекта, соответствует выполняющей подстановке логической формулы.
- АК-объект, оказавшийся при проверке пустым, соответствует тождественно ложной формуле.
- АК-объект , если он равен , соответствует общезначимой формуле или тавтологии.
- Непустой АК-объект соответствует выполнимой формуле.
- Методы квантификации в АК с помощью операций с атрибутами приведены выше.
- Домены атрибутов в АК могут быть любыми не обязательно равными друг другу множествами. Это означает, что структуры АК соответствуют формулам многосортного исчисления предикатов.
- Логический вывод в АК основан на теореме.
- Теорема. Пусть даны АК-объекты . Тогда есть следствие , если и только если .
Возможные применения
С помощью алгебры кортежей моделируются произвольные отношения, формулы математической логики, модели знаний (логические формулы, правила, фреймы и семантические сети) и логико-вероятностные модели. АК можно применять для обобщения данных и знаний в интеллектуальных системах. Одним из преимуществ структур АК по сравнению с традиционными моделями интеллектуальных систем является возможность эффективного распараллеливания операций.
Логическая задача
По мотивам задач из книги известного логика Раймонда Смаллиана «Принцесса или тигр?».
Перед узником три комнаты, в одной из них принцесса, в другой — тигр, а третья — пустая. Узнику нужно войти в комнату с принцессой. Заданы всего две подсказки:
- Во 2-й комнате нет тигра, а 3-я комната не пуста.
- 1-я комната не пуста, а во второй нет тигра.
Одна из подсказок истинная (какая именно, неизвестно), другая — ложная. В какой комнате принцесса? Задачу можно, разумеется, решить и без алгебры кортежей.
- Пояснение: пусть T — в комнате тигр, P — в комнате принцесса, E — комната пуста. Тогда в структурах АК подсказки можно записать так:
- .
- .
Литература
- Кулик Б. А. Система логического программирования на основе алгебры кортежей // Изв. РАН. Техн. кибернетика. 1993. № 3. С. 226—239.
- Кулик Б. А. Математическая модель дедуктивной базы данных на основе алгебры кортежей // Известия РАН. Техн. кибернетика. 1994. № 2. С. 161—169.
- Кулик Б. А. Новые классы КНФ с полиномиально распознаваемым свойством выполнимости // Автоматика и телемеханика. 1995. № 2. С. 111—124.
- Кулик Б. А. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 1. Основы алгебры кортежей //Автоматика и телемеханика. 1997. № 1. С. 126—136.
- Кулик Б. А., Наумов М. В. Представление логических систем в вероятностном пространстве на основе алгебры кортежей. 2. Измеримые логические системы //Автоматика и телемеханика. 1997. № 2. С. 169—179.
- Кулик Б. А. Анализ надежности систем с многими состояниями на основе алгебры кортежей // Автоматика и телемеханика, 2003. № 7. С. 13-18.
- Кулик Б. А. Вероятностная логика на основе алгебры кортежей // Известия РАН. Теория и системы управления. 2007. № 1. С. 118—127.
- Кулик Б. А. Обобщенный подход к моделированию и анализу интеллектуальных систем на основе алгебры кортежей.
- Кулик Б. А. Курс лекций по логике и математике.