ОБЩИЕ ВОПРОСЫ ФОРМАЛИЗАЦИИ ПРОЕКТИРОВАНИЯ: ОНТОЛОГИЧЕСКИЕ АСПЕКТЫ
sergey shishkinБ.А. Кулик
Аннотация. В современном дедуктивном анализе к основным задачам относятся следующие: поиск доказательства заданного утверждения с помощью аксиом и правил вывода; проверка корректности заданного следствия из определенных посылок. О задачах вывода следствий с заранее заданными свойствам (задачи с интересными следствиями) в настоящее время известно немного, и нет четких ответов на вопросы: какие свойства присущи интересному следствию и как вычислить интересное следствие? Ответы можно получить, если для моделирования рассуждений воспользоваться математическим аппаратом алгебры кортежей на основе свойств декартова произведения множеств. Объектами алгебры кортежей являются произвольные многоместные отношения. Эти отношения можно рассматривать как интерпретации формул математической логики. Они представляют собой матрице-подобные структуры, у которых ячейки содержат не элементы, а подмножества соответствующих атрибутов. Операции (дополнение, обобщенное пересечение и обобщенное объединение) в алгебре кортежей соответствуют логическим связкам математической логики (отрицание, конъюнкция, дизъюнкция), а отношение обобщенное включение – отношению выводимости. Вычисление кванторных операций выполняется с помощью операций с атрибутами (добавление фиктивного атрибута, что соответствует правилу обобщения в исчислении предикатов, и элиминация атрибута). Для двух из четырех типов структур алгебры кортежей элиминация атрибутов соответствует вычислению проекции отношения. Для вывода интересных следствий в алгебре кортежей используется структура, названная минимальным следствием, которая равна обобщенному пересечению посылок, выраженных структурами алгебры кортежей. Интересные следствия вычисляются как проекции минимального следствия. В результате вычислений и проверок получаются следствия с сокращнным или заданным составом переменных, а также с сокращнным объмом записи.
Ключевые слова: интерпретация, алгебра кортежей, декартово произведение множеств, кванторные операции, правило обобщения, минимальное следствие, проекция, элиминация атрибутов.
Введение. Постановка задачи поиска интересных следствий предложена в статье [1]. В современных публикациях, например в [2, 3], при решении подавляющего большинства задач логического вывода предполагается, что посылки и предполагаемое следствие заданы, требуется лишь подтвердить корректность этого следствия. Задача поиска следствий, не представленных в условии задачи, решается лишь для определенного класса баз знаний [4, 5]. В работе [6] показаны возможности автоматизации порождения содержательных утверждений (гипотез, абдуктивных заключений и т.д.) из знаний, выраженных с помощью позитивно образованных стандартизованных формул (пост-формул). Однако в работе [6] рассматривается порождение утверждений, которые не являются логическими следствиями. Близкой к задаче вычисления интересных следствий является задача минимизации булевых функций [7, 8]. Но в ней рассматриваются эквивалентные преобразования логических формул определенного типа, а не вывод следствий. Чтобы найти подходы к решению задачи вычисления интересных следствий, предлагается воспользоваться методами алгебры кортежей [9].
Краткие сведения об алгебре кортежей
Основные термины и структуры алгебры кортежей. Алгебра кортежей (АК) – математическая система, предназначенная для моделирования и анализа многоместных отношений, в которой используются свойства декартовых произведений (ДП) множеств. Эти свойства позволяют представить отношения в сжатом виде и унифицировать многие методы и модели дискретной математики. Структуры алгебры кортежей могут быть преобразованы в обычные отношения с помощью определенных алгоритмов.
Применительно к логике с помощью алгебры кортежей исследуется один из вариантов [10] интерпретации языка первого порядка. В качестве области интерпретации всех переменных используется множество D, а для n-местных предикатов и формул со свободными переменными областью интерпретации является n-местное отношение, т.е. подмножество nместных кортежей элементов из Dn . Эта модель интерпретации принята за основу в АК, но с учетом прикладной направленности АК в данную модель интерпретации внесены следующие изменения.
Изменение 1. Для разных переменных модели разрешено использовать разные области интерпретации. Поэтому, во избежание возможных несогласованностей, предложено по аналогии с базами данных [11] приписывать к именам отношений схему отношения, т.е. последовательность имен областей интерпретации переменных. С учетом этого, имена областей интерпретации переменных названы атрибутами, а области интерпретации атрибутов – доменами.
Изменение 2. Для многих задач логического анализа удобно рассматривать n-местное отношение не как множество n-местных кортежей элементов, а как объединение ДП. В этом случае в качестве значений атрибута используются не элементы его домена, а имена или обозначения (например, A2 или {b, c}) всех подмножеств домена. Множества с этими именами или обозначениями названы компонентами атрибута.
Объединение ДП, рассматриваемое как отдельная структура, ранее не исследовалось. Для этой структуры не были известны алгоритмы операций (дополнение, пересечение, объединение), алгоритмы проверок включения одной структуры в другую и т.д. Были определены только отдельные операции для одиночных ДП (пересечение и разность), а также алгоритм проверки включения одного ДП в другое [12, 13]. Оказалось, что ранее известные и новые алгоритмы и их обоснования можно существенно упростить, если отказаться от общепринятых обозначений ДП. Вместо этого предложено представлять ДП как кортежи компонент, при этом каждая компонента с помощью схемы отношения привязывается к определенному атрибуту.
Законы АК соответствует законам алгебры множеств [14]. Многоместные отношения в АК можно представить с помощью четырех типов структур (АК-объектов). Вместо логических связок в АК используются соответствующие операции (по сути это модифицированные операции алгебры множеств) с многоместными отношениями, а вместо кванторов – операции с атрибутами. Алгоритмы выполнения операций с АК-объектами, проверок включения, преобразований в другие типы и т.д. сформулированы и доказаны в АК в виде теорем.
Информация о схеме отношения АК-объектов содержится в их именах: к идентификатору отношения приписывается заключенная в квадратные скобки схема этого отношения. Например, имя R[XYZ] означает, что АК-объект R содержится в пространстве XYZ . АК-объекты, заданные в одном и том же пространстве атрибутов, называются однотипными. Выделяются два типа компонент, названных фиктивными компонентами.
Полная компонента равна домену соответствующего атрибута.
Пустая компонента равна пустому множеству.
Обозначения структур АК: C-кортежи соответствуют конъюнкции (conjunction), D кортежи – дизъюнкции (disjunction) логических формул. Структуры АК матричные, причем в ячейках матриц записываются не элементы, а компоненты. При преобразовании АК объектов в формулы математической логики предполагается, что компоненты АК-объектов – это интерпретации одноместных предикатов, а АК-объекты – интерпретации формул или многоместных предикатов.
C-кортеж – это n-местное отношение, равное ДП содержащихся в нем компонент, записанных в виде кортежа, ограниченного квадратными скобками.
Например ...
Доказано, что пересечение C-кортежей, если оно не равно пустому множеству, равно C-кортежу (теоремы 2 и 3 в [9]). Однако объединение C-кортежей может быть представлено единственным C-кортежем лишь в исключительных случаях [9]. Поэтому возникает необходимость в определении структуры нового типа.
C-система – это отношение, равное объединению однотипных C-кортежей, которые записываются в виде строк матрицы, ограниченной квадратными скобками.
Например ...
C-системе c n атрибутами в математической логике соответствует дизъюнктивная нормальная форма (ДНФ) или n-местный предикат.
Если АК-объект преобразуется в обычное отношение, то элементы этого отношения называются элементарными кортежами. Они представляют выполняющие подстановки соответствующей логической формулы. С помощью C-кортежей и C-систем можно выразить любое многоместное отношение, но для вычисления их дополнений требуются новые структуры – D-кортежи и D-системы. Для определения этих АК-объектов используется промежуточная структура – диагональная C-система
Диагональная C-система – это C-система размерности n на n, у которой все недиагональные компоненты – полные.
Например ...
Доказано (теорема 9 в [9]), что диагональная C-система есть результат вычисления дополнения некоторого C-кортежа.
D-кортеж – это отношение, равное диагональной C-системе, записанное как ограниченный перевернутыми квадратными скобками кортеж её диагональных компонент.
Например ...
Ясно (теорема 9), что дополнение Q[XYZ] равно C-кортежу [ A B C ]. Здесь A = X\A, B = Y\B и C = Z\C.
D-система – это отношение, равное пересечению однотипных D-кортежей, записанное как ограниченная перевернутыми квадратными скобками матрица компонент, в которой строками являются участвующие в операции D-кортежи.
С помощью D-систем можно вычислять дополнение C-систем. Поскольку C-система есть объединение C-кортежей, то по закону де Моргана её дополнение равно пересечению дополнений этих C-кортежей. Поскольку дополнения C-кортежей равны соответствующим Dкортежам, то для вычисления дополнения C-системы достаточно заменить в ней все компоненты их дополнениями, а вместо обычных квадратных скобок записать перевёрнутые.
Например ... В математической логике D-системе соответствует конъюнктивная нормальная форма (КНФ).
Универсум АК-объекта (U) определяется как ДП доменов атрибутов, заданных в его схеме отношения. Например ...
Если при вычислении установлено, что некоторая C-система равна универсуму, то она соответствует общезначимой формуле, если же некоторая D-система окажется равной пустому множеству, то она соответствует тождественно ложной формуле или противоречию.
Кванторные операции в АК выполняются с помощью простых операций с атрибутами. К ним, в частности, относятся операции +Atr и –Atr. Операция добавление фиктивного атрибута (+Atr) выполняется как добавление имени нового атрибута в схему отношения АКобъекта и соответствующего нового столбца с фиктивными компонентами в матричное представление. Например .... При добавлении фиктивного атрибута получается C-система ... При выполнении операции +Atr в C-структуры и D структуры добавляются фиктивные компоненты ...,
Операция +Atr соответствует правилу обобщения (Gen) в исчислении предикатов, которое в [10, p.67]. Операция +Atr используется также для преобразования АК-объектов с разными схемами отношений к однотипным АК объектам за счёт добавления недостающих фиктивных атрибутов.
Обобщённые операции пересечения и объединения – это операции АК, отличающиеся от обычных одноимённых операций алгебры множеств тем, что перед их выполнением АК-объекты приводятся к одной схеме отношения с помощью операции +Atr. Обобщённые операции пересечения и объединения семантически равносильны логическим связкам конъюнкции и дизъюнкции. Аналогично вводятся обобщённые отношения. Доказано, что АК с обобщёнными операциями и отношениями изоморфна алгебре множеств.
Операция элиминации атрибута (–Atr) выполняется как удаление из схемы отношения имени этого атрибута, а из матричного представления – столбца его значений. Логический смысл этой операции, в отличие от +Atr, зависит от типа АК-объекта (теоремы 31 и 32 в [9]). Например ...
В D-системах в соответствии с семантикой операции –Atr, которая в данном случае соответствует навешиванию квантора .... Проверка (с помощью теорем 20 и 21 в [9]) показывает, что данное соотношение выполняется.
Проекцией АК-объекта называется результат однократного или многократного применения операции –Atr к АК-объекту, выраженному как C-кортеж или C-система, при условии, что атрибут Atr содержится в его схеме отношения. Например, если задана C-система R[XYZ], то её проекции обозначаются PrXY(R), PrY(R), PrXZ(R) и т.д., а проекция PrXZ(R) вычисляется с помощью элиминации атрибута Y: PrXZ(R) = –Y(R[XYZ]).
С проекциями АК-объектов связано понятие фиктивного атрибута, содержащегося в отношении. Пусть задан АК-объект R[W], где W – множество атрибутов, в состав которых входит атрибут X, и PrW\X(R) – проекция АК объекта R[W], в которой присутствуют все атрибуты, кроме X. Тогда X есть фиктивный атрибут в R[W], если соблюдается равенство R[W] = +X(PrW\X(R)).
В АК-объекте R[W] каждому элементарному кортежу из проекции PrW\X(R) соответствует множество всех значений атрибута X.
Пусть посылки рассуждения записаны в виде АК-объектов A1, A2, …, An. Тогда логическая формула, представленная АК-объектом B, будет следствием этих посылок, если соблюдается соотношение ...
АК-объект, полученный в результате вычисления выражения в левой части (2), называется минимальным следствием. Минимальное потому, что любое его строгое подмножество не является следствием.
Следует заметить, что в АК фиктивный атрибут Xi добавляется в АК-объект при условии, что Xi отсутствует в его схеме отношения. Это означает, что правило Gen «(...xi)B следует из B» надо дополнить словами «при условии, что переменная xi не входит свободно в B». В книге [10] для правила Gen это условие отсутствует.
Источником ошибок в логическом анализе на основе исчисления предикатов может быть отсутствие понятия, аналогичного термину «схема отношения». В частности, в алгоритме унификации допускается замена переменных в подстановках [15, p.80]. Для отношений и АК-объектов, которые являются интерпретациями предикатов и формул, это означает замену атрибута в схеме отношения и, соответственно, переход в другое пространство даже в том случае, если домены этих атрибутов одинаковы. Например ... Другой пример ... Таким образом, интерпретации формул при переименовании переменных существенно изменяются.
При решении логических задач, в т.ч. для задачи вычисления интересных следствий, применяется метод ортогонализации [16, 17].
С помощью ортогонализации вычисляются C-системы с попарно непересекающимися C-кортежами, которые используются при расчѐте вероятностей событий, выраженных логическими формулами [18, 19] или АК-объектами [20]. Установлено, что ортогонализация позволяет значительно уменьшить трудоѐмкость некоторых алгоритмов экспоненциальной вычислительной сложности за счёт того, что при выполнении операций получается намного больше пустых C-кортежей, которые не участвуют в последующих вычислениях [21].
Алгоритм преобразовании D-системы в C-систему формулируется просто (теорема 25). Однако его реализация требует в общем случае экспоненциального числа операций. Например, если D-система задана в пространстве из N атрибутов и число D-кортежей в ней равно M, то для выполнения этой операции потребуется NM операций пересечения C-кортежей. На самом деле этих операций намного меньше, т.к., во-первых, многие D-кортежи содержат меньшее, чем N, число непустых компонент и преобразуются в C-систему меньшей размерности, и, во-вторых, при пересечениях C-кортежей нередко получаются пустые кортежи, которые не участвуют в дальнейших операциях.
Если в алгоритме преобразования D-системы в C-систему использовать теорему 27, то число операций этого алгоритма может значительно сократиться и в некоторых случаях дойти до полиномиальной оценки вычислительной сложности [21]. Для того, чтобы выполнить ортогонализацию в этом алгоритме, достаточно каждый D-кортеж исходной D-системы преобразовать в ортогональную C-систему, после чего вычислить пересечение преобразованных C-систем.
Помимо этого сокращение трудоёмкости алгоритма преобразования D-системы в Cсистему достигается за счёт использования специальных правил упорядочивания D-кортежей, а также различных вариантов преобразования D-кортежей в ортогональные Cсистемы [21].
Используемые теоремы АК
В формулировках теорем рассматриваются однотипные АК-объекты, поэтому их схемы отношений в именах не указываются.
Теорема 1 (проверка включения C-кортежей).
Теорема 2 (пересечение C-кортежей).
Теорема 3 (пустое пересечение C-кортежей).
Теорема 8 (пересечение C-систем). Пусть даны однотипные C-системы P и Q. Результатом их пересечения будет C-система, содержащая все непустые пересечения каждого C-кортежа из P с каждым C-кортежем из Q.
Теорема 9 Дополнение C-кортежа P = [P1 P2 … PN] есть диагональная C-система размерности n на n, где каждая диагональная компонента – дополнение соответствующей компоненты C-кортежа P
Теорема 20 (проверка включения C-кортежа в D-кортеж).
Теорема 21 (проверка включения C-кортежа в D-систему).
Теорема 25 (преобразование D-системы в C-систему). D-система P, содержащая m D-кортежей, эквивалентна C-системе, которая является пересечением m C-систем, полученных с помощью преобразования каждого D-кортежа из P в диагональную C-систему.
Теорема 27 (ортогонализация D-кортежа) ...
Теорема 31 (навешивание квантора).
Теорема 32 (навешивание квантора ...).
Примеры решения логических задач методами АК
Свойства интересных следствий
Методы вычисления интересных следствий
Вычисление следствий с сокращённой схемой отношения
Вычисление следствий с заданным составом атрибутов
Сокращение объёмов записи в следствиях
Заключение
Для заданной системы посылок предложены алгоритмы вычисления следствий со следующими свойствами:
- с сокращённым составом переменных;
- с заданным составом переменных;
- с сокращённым объёмом записи.
Во всех случаях используется понятие минимального следствия, представляющего собой обобщённое пересечение АК-объектов, которые моделируют посылки. Интересные следствия в ряде случаев являются неполными проекциями минимального следствия.
Значительная часть современных классических и неклассических логических систем предусматривает для вывода новых следствий механизм исчислений, т.е. получение результатов на основе правил вывода. В АК наряду с этим механизмом предлагается получение новых следствий с помощью вычислений, т.е. на основе алгоритмов, позволяющих получить требуемый результат с помощью определённых операций над заданными в условии задачи структурами. В некоторых случаях, в частности, в задаче вычисления следствий с заранее заданными свойствами, этот метод имеет определѐнные преимущества.
Список источников
[1] Шалак В.И. Анализ vs дедукция // Логические исследования. 2018. Т. 24, № 1. С.26-45.
[2] Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах. М.: ООО Издательская фирма "Физико-математическая литература". 2008. 712 с
[3] Охотников О.А. О поиске натурального классического логического вывода с использованием частичной скулемизации // Интеллектуальные системы. Теория и приложения. 2019. Т. 23. Вып. 4. С.39-90.
[4] Симонов А.И., Страбыкин Д.А. Вывод следствий с построением схемы вывода из новых фактов при не полностью определѐнной базе знаний // Современные наукоѐмкие технологии. 2018. № 10. С.120-125.
[5] Bardovskaya A., Chistyakov G., Dolzhenkova M., Strabykin D. The method of deductive inference of consequences with the scheme construction // Advances in Intelligent Systems and Computing. 2019. Vol. 985. P.1-10.
[6] Васильев С.Н. Интерактивное порождение новых знаний на основе автоматических средств логического вывода // Онтология проектирования. 2023. Т.13, №1(47). С.10-28. DOI: 10.18287/2223-9537-2023-13-1-10- 28.
[7] Quine W.V. The problem of simplifying of truth functions // Amer. Math. Monthly. 1952, Vol. 59. P.521-531.
[8] Михеева Е.А., Еникеева А.Ф. Минимизация булевых функций геометрическим методом // Учѐные записки УлГУ. Сер. Математика и информационные технологии. Электрон. журн. 2018. № 1, С.72-82. https://www.mathnet.ru/rus/ulsu/y2018/i1/p72.
[9] Кулик Б.А. Логика и математика: просто о сложных методах логического анализа (под общ. ред. А.Я. Фридмана). СПб.: Политехника. 2020. 144 с.
[10] Mendelson E. Introduction to Mathematical Logic (6th ed.). Boca Raton, London, New York: Taylor & Francis Group, 2015. 499 p.
[11] Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. М.: Наука. 1991. 448 с. [
12] Бурбаки Н. Теория множеств. М.: Мир. 1965. 455 с.
[13] Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука. 1971. 416 с.
[14] Курант Р., Роббинс Г. Что такое математика? 3-e изд., испр. и доп. М.: МЦНМО. 2001. 568 с.
[15] Chang С.-L., LeeR.С.-T. Symbolic Logic and Mechanical Theorem Proving. New York: Academic Press. 1973. 331 p.
[16] Порецкий П.С. Решение общей задачи теории вероятностей при помощи математической логики // Собрание протоколов заседаний секции физико-математических наук общества естествоиспытателей при Казанском университете. Казань: 1887. Т.5. С.83-116.
[17] Мерекин Ю.В. Решение задач вероятностного расчѐта однотактных схем методом ортогонализации // Вычислительные системы. Сборник трудов Института математики СО АН СССР. 1963. Вып.4. С.10-21.
[18] Рябинин И.А. Надёжность и безопасность структурно-сложных систем. СПб.: Политехника. 2000. 248 с.
[19] Цициашвили Г.Ш. Логико-вероятностное моделирование по модульному принципу // Дальневосточный математический журнал. 2019. Т. 19. № 1. С.114-118.
[20] Кулик Б.А., Зуенко А.А., Фридман А.Я. Алгебраический подход к интеллектуальной обработке данных и знаний. СПб.: Изд-во Политехн. ун-та. 2010. 235 с.
[21] Кулик Б.А. Новые классы КНФ с полиномиально распознаваемым свойством выполнимости // Автоматика и телемеханика. 1995. № 2. С.111-124.
[22] Pelletier F.J. Seventy-Five Problems for Testing Automatic Theorem Provers // Journal of Automated Reasoning. 1986. Vol. 2. P.191-216.