Как вычислять интересные следствия

Полный текст

Введение

Постановка задачи поиска интересных следствий предложена в статье [1]. В современных публикациях, например в [2, 3], при решении подавляющего большинства задач логического вывода предполагается, что посылки и предполагаемое следствие заданы, требуется лишь подтвердить корректность этого следствия. Задача поиска следствий, не представленных в условии задачи, решается лишь для определённого класса баз знаний [4, 5]. В работе [6] показаны возможности автоматизации порождения содержательных утверждений (гипотез, абдуктивных заключений и т.д.) из знаний, выраженных с помощью позитивно-образованных стандартизованных формул (пос-формул). Однако в работе [6] рассматривается порождение утверждений, которые не являются логическими следствиями.

Близкой к задаче вычисления интересных следствий является задача минимизации булевых функций [7, 8]. Но в ней рассматриваются эквивалентные преобразования логических формул определённого типа, а не вывод следствий.

Чтобы найти подходы к решению задачи вычисления интересных следствий, предлагается воспользоваться методами алгебры кортежей [9].

1. Краткие сведения об алгебре кортежей

1.1 Основные термины и структуры алгебры кортежей

Алгебра кортежей (АК) – математическая система, предназначенная для моделирования и анализа многоместных отношений, в которой используются свойства декартовых произведений (ДП) множеств. Эти свойства позволяют представить отношения в сжатом виде и унифицировать многие методы и модели дискретной математики. Структуры алгебры кортежей могут быть преобразованы в обычные отношения с помощью определённых алгоритмов.

Применительно к логике с помощью алгебры кортежей исследуется один из вариантов [10] интерпретации языка первого порядка. В качестве области интерпретации всех переменных используется множество D, а для n-местных предикатов и формул со свободными переменными областью интерпретации является n-местное отношение, т.е. подмножество n-местных кортежей элементов из Dⁿ. Эта модель интерпретации принята за основу в АК, но с учётом прикладной направленности АК в данную модель интерпретации внесены следующие изменения.

Изменение 1. Для разных переменных модели разрешено использовать разные области интерпретации. Поэтому, во избежание возможных несогласованностей, предложено по аналогии с базами данных [11] приписывать к именам отношений схему отношения, т.е. последовательность имён областей интерпретации переменных. С учётом этого, имена областей интерпретации переменных названы атрибутами, а области интерпретации атрибутов – доменами.

Изменение 2. Для многих задач логического анализа удобно рассматривать n-местное отношение не как множество n‑местных кортежей элементов, а как объединение ДП. В этом случае в качестве значений атрибута используются не элементы его домена, а имена или обозначения (например, A₂ или {b, c}) всех подмножеств домена. Множества с этими именами или обозначениями названы компонентами атрибута.

Объединение ДП, рассматриваемое как отдельная структура, ранее не исследовалось. Для этой структуры не были известны алгоритмы операций (дополнение, пересечение, объединение), алгоритмы проверок включения одной структуры в другую и т.д. Были определены только отдельные операции для одиночных ДП (пересечение и разность), а также алгоритм проверки включения одного ДП в другое [12, 13]. Оказалось, что ранее известные и новые алгоритмы и их обоснования можно существенно упростить, если отказаться от общепринятых обозначений ДП ($D^n$; $A\times B\times C$; ${\prod }_{i=1}^n{S}_i$ и т.д.). Вместо этого предложено представлять ДП как кортежи компонент, при этом каждая компонента с помощью схемы отношения привязывается к определённому атрибуту.

Законы АК соответствует законам алгебры множеств [14]. Многоместные отношения в АК можно представить с помощью четырёх типов структур (АК-объектов). Вместо логических связок $\neg$, $\wedge$ и $\vee$ в АК используются соответствующие операции (по сути это модифицированные операции алгебры множеств) с многоместными отношениями, а вместо кванторов – операции с атрибутами. Алгоритмы выполнения операций с АК-объектами, проверок включения, преобразований в другие типы и т.д. сформулированы и доказаны в АК в виде теорем¹.

Информация о схеме отношения АК-объектов содержится в их именах: к идентификатору отношения приписывается заключённая в квадратные скобки схема этого отношения. Например, имя R[XYZ] означает, что АК-объект R содержится в пространстве $X\times Y\times Z$. АК‑объекты, заданные в одном и том же пространстве атрибутов, называются однотипными.

Выделяются два типа компонент, названных фиктивными компонентами.

Полная компонента (обозначается *) равна домену соответствующего атрибута.

Пустая компонента (обозначается $\varnothing$) равна пустому множеству.

Обозначения структур АК: C-кортежи соответствуют конъюнкции (conjunction), D-кортежи – дизъюнкции (disjunction) логических формул. Структуры АК матричные, причём в ячейках матриц записываются не элементы, а компоненты. При преобразовании АК-объектов в формулы математической логики предполагается, что компоненты АК-объектов – это интерпретации одноместных предикатов, а АК-объекты – интерпретации формул или многоместных предикатов.

C-кортеж – это n-местное отношение, равное ДП содержащихся в нём компонент, записанных в виде кортежа, ограниченного квадратными скобками.

Например, АК-объект T[XYZ] = [A * B] – это C-кортеж, при этом A$\subseteq$X, B$\subseteq$Z, а компонента «*» равна домену соответствующего атрибута (в данном случае, поскольку она находится на второй позиции, то * = Y). Этот C-кортеж можно преобразовать в обычное отношение с помощью ДП следующим образом: T[XYZ] = A$\times$Y$\times$B. Он соответствует конъюнкту

T(x, z) = A(x) $\wedge$ True $\wedge$ B(z) = A(x) $\wedge$ B(z),

в котором интерпретации одноместных предикатов A(x) и B(z) – это компоненты A и B.

Доказано, что пересечение C-кортежей, если оно не равно пустому множеству, равно C‑кортежу (теоремы 2 и 3 в [9]). Однако объединение C-кортежей может быть представлено единственным C-кортежем лишь в исключительных случаях [9]. Поэтому возникает необходимость в определении структуры нового типа.

C-система – это отношение, равное объединению однотипных C-кортежей, которые записываются в виде строк матрицы, ограниченной квадратными скобками.

Например, R[XYZ] = $\left[\begin{array}{l}{A}_1*A_3\\ B_1{B}_2*\end{array}\right]$ есть C-система, при этом A₁ $\subseteq$ X, A₃ $\subseteq$ Z и т.д. Данная C-система преобразуется в обычное отношение с помощью ДП следующим образом:

R[XYZ] = (A₁ $\times$ Y $\times$ A₃) $\cup$ (B₁ $\times$ B₂ $\times$ Z).

C-системе c n атрибутами в математической логике соответствует дизъюнктивная нормальная форма (ДНФ) или n-местный предикат.

Если АК-объект преобразуется в обычное отношение, то элементы этого отношения называются элементарными кортежами. Они представляют выполняющие подстановки соответствующей логической формулы. С помощью C-кортежей и C-систем можно выразить любое многоместное отношение, но для вычисления их дополнений требуются новые структуры – D-кортежи и D-системы. Для определения этих АК-объектов используется промежуточная структура – диагональная C-система.

Диагональная C-система – это C-система размерности n$\times$n, у которой все недиагональные компоненты – полные (*).

Например, Q[XYZ] = $\left[\begin{array}{l}{A}_1*\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}*\\ *B*\\ **\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.17em}}С\end{array}\right]$ – диагональная C-система.

Доказано (теорема 9 в [9]), что диагональная C-система есть результат вычисления дополнения некоторого C-кортежа.

D-кортеж – это отношение, равное диагональной C-системе, записанное как ограниченный перевёрнутыми квадратными скобками кортеж её диагональных компонент.

Например, изображённую выше диагональную C-систему можно записать как D‑кортеж:

Q[XYZ] = ]A B C[.

Ясно (теорема 9), что дополнение Q[XYZ] равно C-кортежу [$\overline{A}$ $\overline{B}$  $\overline{C}$]. Здесь $\overline{A}$ = X\A, $\overline{B}$ = Y\B и $\overline{C}$ = Z\C.

D-система – это отношение, равное пересечению однотипных D-кортежей, записанное как ограниченная перевёрнутыми квадратными скобками матрица компонент, в которой строками являются участвующие в операции D-кортежи.

С помощью D-систем можно вычислять дополнение C-систем. Поскольку C‑система есть объединение C-кортежей, то по закону де Моргана² её дополнение равно пересечению дополнений этих C-кортежей. Поскольку дополнения C-кортежей равны соответствующим D-кортежам, то для вычисления дополнения C-системы достаточно заменить в ней все компоненты их дополнениями, а вместо обычных квадратных скобок записать перевёрнутые.

Например, дополнение C-системы P[XYZ] = $\left[\begin{array}{l}A*\text{\hspace{0.33em}\hspace{0.33em}}C\\ DE*\end{array}\right]$ вычисляется как D‑система $\overline{P}\left[XYZ\right]=\left]\begin{array}{ccc}\overline{A}& \varnothing & \overline{C}\\ \overline{D}& \overline{E}& \varnothing \end{array}\right[$. В математической логике D-системе соответствует конъюнктивная нормальная форма (КНФ).

Универсум АК-объекта (U) определяется как ДП доменов атрибутов, заданных в его схеме отношения. Например, для АК-объекта R[XYZ] универсум есть U = X $\times$ Y $\times$ Z.

Если при вычислении установлено, что некоторая C-система равна универсуму, то она соответствует общезначимой формуле, если же некоторая D-система окажется равной пустому множеству, то она соответствует тождественно ложной формуле или противоречию.

Кванторные операции в АК выполняются с помощью простых операций с атрибутами. К ним, в частности, относятся операции +Atr и –Atr. Операция добавление фиктивного атрибута (+Atr) выполняется как добавление имени нового атрибута в схему отношения АК-объекта и соответствующего нового столбца с фиктивными компонентами в матричное представление. Например, пусть задана C-система R_k[XZ] =$\left[\begin{array}{l}{A}_1{A}_2\\ B_1{B}_2\end{array}\right]$. При добавлении фиктивного атрибута Y в R_k[XZ] получается C-система +Y(R_k[XZ]) = R_m[XYZ] =$\left[\begin{array}{l}{A}_1*A_3\\ B_1*B_3\end{array}\right]$. При выполнении операции +Atr в C-структуры добавляются фиктивные компоненты «*», а в D-структуры – фиктивные компоненты «$\varnothing$».

Операция +Atr соответствует правилу обобщения (Gen) в исчислении предикатов, которое в [10, p.67] формулируется так: «($\forall$x_i)B следует из B». Операция +Atr используется также для преобразования АК-объектов с разными схемами отношений к однотипным АК-объектам за счёт добавления недостающих фиктивных атрибутов.

Обобщённые операции пересечения (${\cap }_G$) и объединения (${\cup }_G$) – это операции АК, отличающиеся от обычных одноимённых операций алгебры множеств тем, что перед их выполнением АК-объекты приводятся к одной схеме отношения с помощью операции +Atr. Обобщённые операции ${\cap }_G$ и ${\cup }_G$ семантически равносильны логическим связкам конъюнкции и дизъюнкции. Аналогично вводятся обобщённые отношения (${\subseteq }_G$ и ${=}_G$). Доказано, что АК с обобщёнными операциями и отношениями изоморфна алгебре множеств.

Операция элиминации атрибута (–Atr) выполняется как удаление из схемы отношения имени этого атрибута, а из матричного представления – столбца его значений. Логический смысл этой операции, в отличие от +Atr, зависит от типа АК-объекта (теоремы 31 и 32 в [9]). Например, пусть задана D-система $P\left[XYZ\right]=\left]\begin{array}{l}\left\{c\right\}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}\left\{g\right\}\left\{a,c\right\}\\ \left\{a,d\right\}\text{\hspace{0.33em}\hspace{0.33em}}\varnothing \left\{b\right\}\end{array}\right[$ Вычисляя $X{\left(P\right[XYZ\left]\right)}^{\circ } ={ }^{\circ }Q{\left[YZ\right]}^{\circ } {=}^{\circ } \left]\begin{array}{l}\left\{g\right\}\left\{a,c\right\}\\ \varnothing \left\{b\right\}\end{array}\right[,$ можно преобразовать полученный результат в C‑систему (теоремы 25 и 8 в [9]): $Q{\left[YZ\right]}^{\circ } =\left[\begin{array}{l}\left\{g\right\}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}*\\ *\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}\left\{a,c\right\}\end{array}\right]{\cap }^{\circ } {[* \cdot \cdot \{b\left\}\right]}^{°} ={ }^{°}\left[\right\{g\} \cdot \cdot \{b\left\}\right].$

В D-системах в соответствии с семантикой операции –Atr, которая в данном случае соответствует навешиванию квантора ", должно выполняться [*  {g}  {b}] $\subseteq$ P[XYZ]. Проверка (с помощью теорем 20 и 21 в [9]) показывает, что данное соотношение выполняется.

Проекцией АК-объекта называется результат однократного или многократного применения операции –Atr к АК-объекту, выраженному как C-кортеж или C-система, при условии, что атрибут Atr содержится в его схеме отношения. Например, если задана C-система R[XYZ], то её проекции обозначаются Pr_XY(R), Pr_Y(R), Pr_XZ(R) и т.д., а проекция Pr_XZ(R) вычисляется с помощью элиминации атрибута Y: Pr_XZ(R) = –Y(R[XYZ]).

С проекциями АК-объектов связано понятие фиктивного атрибута, содержащегося в отношении. Пусть задан АК-объект R[W], где W – множество атрибутов, в состав которых входит атрибут X, и Pr_W\X(R) – проекция АК объекта R[W], в которой присутствуют все атрибуты, кроме X. Тогда X есть фиктивный атрибут в R[W], если соблюдается равенство

R[W] = +X(Pr_W\X(R)).   (1)

Равенство (1) означает, что в АК-объекте R[W] каждому элементарному кортежу из проекции Pr_W\X(R) соответствует множество всех значений атрибута X.

Пусть посылки рассуждения записаны в виде АК-объектов A₁, A₂, …, A_n. Тогда логическая формула, представленная АК-объектом B, будет следствием этих посылок, если соблюдается соотношение:

$\left(A_1{\cap }_G{A}_2{\cap }_G\dots {\cap }_G{A}_n\right)\subseteq B$.   (2)

АК-объект, полученный в результате вычисления выражения в левой части (2), называется минимальным следствием. Минимальное потому, что любое его строгое подмножество не является следствием.

Следует заметить, что в АК фиктивный атрибут X_i добавляется в АК-объект при условии, что X_i отсутствует в его схеме отношения. Это означает, что правило Gen «($\forall$x_i)B следует из B» надо дополнить словами «при условии, что переменная x_i не входит свободно в B». В книге [10] для правила Gen это условие отсутствует.

Источником ошибок в логическом анализе на основе исчисления предикатов может быть отсутствие понятия, аналогичного термину «схема отношения». В частности, в алгоритме унификации допускается замена переменных в подстановках [15, p.80]. Для отношений и АК-объектов, которые являются интерпретациями предикатов и формул, это означает замену атрибута в схеме отношения и, соответственно, переход в другое пространство даже в том случае, если домены этих атрибутов одинаковы. Например, АК-объект P[XY] при пересечении с самим собой не изменяется, но если в нём заменить имена атрибутов, например, P[YZ], то обобщённое пересечение P[XY]${\cap }_G$P[YZ] означает операцию соединения отношений. Другой пример: интерпретацией формулы A(x) $\wedge$ B(x) является пересечение интерпретаций одноместных предикатов A(x) и B(x), в то время как интерпретацией формулы A(x) $\wedge$ B(y) оказывается ДП интерпретаций предикатов A(x) и B(y). Таким образом, интерпретации формул при переименовании переменных существенно изменяются.

При решении логических задач, в т.ч. для задачи вычисления интересных следствий, применяется метод ортогонализации [16, 17].

С помощью ортогонализации вычисляются C-системы с попарно непересекающимися C‑кортежами, которые используются при расчёте вероятностей событий, выраженных логическими формулами [18, 19] или АК-объектами [20]. Установлено, что ортогонализация позволяет значительно уменьшить трудоёмкость некоторых алгоритмов экспоненциальной вычислительной сложности за счёт того, что при выполнении операций получается намного больше пустых C-кортежей, которые не участвуют в последующих вычислениях [21].

Алгоритм преобразовании D-системы в C-систему формулируется просто (теорема 25). Однако его реализация требует в общем случае экспоненциального числа операций. Например, если D-система задана в пространстве из N атрибутов и число D-кортежей в ней равно M, то для выполнения этой операции потребуется N^M операций пересечения C-кортежей. На самом деле этих операций намного меньше, т.к., во-первых, многие D-кортежи содержат меньшее, чем N, число непустых компонент и преобразуются в C-систему меньшей размерности, и, во-вторых, при пересечениях C-кортежей нередко получаются пустые кортежи, которые не участвуют в дальнейших операциях.

Если в алгоритме преобразования D-системы в C-систему использовать теорему 27, то число операций этого алгоритма может значительно сократиться и в некоторых случаях дойти до полиномиальной оценки вычислительной сложности [21]. Для того, чтобы выполнить ортогонализацию в этом алгоритме, достаточно каждый D-кортеж исходной D-системы преобразовать в ортогональную C-систему, после чего вычислить пересечение преобразованных C-систем.

Помимо этого сокращение трудоёмкости алгоритма преобразования D-системы в C-систему достигается за счёт использования специальных правил упорядочивания D‑кортежей, а также различных вариантов преобразования D-кортежей в ортогональные C-системы [21].

1.2 Используемые теоремы АК

В формулировках теорем рассматриваются однотипные АК-объекты, поэтому их схемы отношений в именах не указываются.

Теорема 1 (проверка включения C-кортежей). Пусть даны два однотипных C-кортежа P = [P₁ P₂ … P_N] и Q = [Q₁ Q₂ … Q_N]. Тогда P $\subseteq$ Q, если и только если P_i $\subseteq$ Q_i верно для всех соответствующих пар компонент сравниваемых C-кортежей.

Теорема 2 (пересечение C-кортежей). Пусть даны два однотипных C-кортежа P = [P₁ P₂ … P_N] и Q = [Q₁ Q₂ … Q_N].. Тогда P $\cap$ Q = [P₁ $\cap$ Q₁  P₂ $\cap$ Q₂  …  P_N $\cap$ Q_N].

Теорема 3 (пустое пересечение C-кортежей). Пусть даны два однотипных C-кортежа P = [P₁ P₂ … P_N] и Q = [Q₁ Q₂ … Q_N], и в них имеется, по крайней мере, одна пара P_i и Q_i компонент, для которых P_i $\cap$ Q_i = $\varnothing$. Тогда P $\cap$ Q = $\varnothing$.

Теорема 8 (пересечение C-систем). Пусть даны однотипные C-системы P и Q. Результатом их пересечения будет C-система, содержащая все непустые пересечения каждого C‑кортежа из P с каждым C-кортежем из Q.

Теорема 9 Дополнение C-кортежа P = [P₁ P₂ … P_N] есть диагональная C-система R = $\left[\begin{array}{l}\overline{P_1}*\cdots \text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}}*\\ *\text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}\overline{P_2}\text{\hspace{0.33em}\hspace{0.33em}}\cdots *\\ \cdots \cdots \cdots \cdots \\ **\text{\hspace{0.33em}\hspace{0.33em}}\dots \overline{P_n}\end{array}\right]$ размерности n ´ n, где каждая диагональная компонента – дополнение соответствующей компоненты C-кортежа P.

Теорема 20 (проверка включения C-кортежа в D-кортеж). Для C-кортежа P = [P₁ P₂ … P_N] и D-кортежа и Q = ]Q₁ Q₂ … Q_n[ справедливо P $\subseteq$ Q, если и только если по крайней мере для одного i соблюдается P_i $\subseteq$ Q_i.

Теорема 21 (проверка включения C-кортежа в D-систему). Для C-кортежа P и D-системы Q справедливо P $\subseteq$ Q, если и только если для каждого D-кортежа Q_i из Q выполняется P $\subseteq$ Q_i.

Теорема 25 (преобразование D-системы в C-систему). D-система P, содержащая m D‑кортежей, эквивалентна C-системе, которая является пересечением m C-систем, полученных с помощью преобразования каждого D-кортежа из P в диагональную C-систему.

Теорема 27 (ортогонализация D-кортежа). D-кортеж вида ]Q₁ Q₂ ... Q_m-1 Q_m[ преобразуется в эквивалентную ему ортогональную C-систему: $\left[\begin{array}{l}\underset{¯}{Q_1}*\cdots \text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}**\\ Q_1\text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}{Q}_2\text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}}\cdots \text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}*\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}*\\ \cdots \cdots \cdots \cdots \cdots \\ \underset{¯}{Q_1}\underset{¯}{Q_1}\text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}}\cdots \underset{¯}{Q_{m-1}}*\\ Q_1{Q}_2\text{\hspace{0.17em}\hspace{0.33em}\hspace{0.33em}}\cdots Q_{m-1}\text{\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}}{Q}_m\end{array}\right]$.

Теорема 31 (навешивание квантора $\exists$). Если C-кортеж или C-система R[…X…] без пустых C-кортежей – интерпретация логической формулы A(…, x, …) со свободной переменной x, то АК-объект –X(R[…X…]) – интерпретация логической формулы $\exists$x(A(…, x, …)).

Теорема 32 (навешивание квантора $\forall$). Если D-кортеж или D-система R[…X…], не содержащие D-кортежей с компонентой «*», – интерпретация логической формулы A(…, x, …) со свободной переменной x, то АК-объект –X(R[…X…]) – интерпретация логической формулы $\forall$x(A(…, x, …)).

2. Примеры решения логических задач методами АК

Задача 1. Четыре подруги (Анна, Белла, Светлана и Дина) имеют следующие особенности: Анна и Белла – блондинки, Светлана предпочитает короткую стрижку, Анна и Дина носят туфли на высоких каблуках, Анна, Белла и Светлана работают в фирме D. В зависимости от внешности и статуса, подруги предпочитают покупать одежду в разных торговых фирмах (K, L и M). Эти зависимости выражаются следующими условиями:

1) если не блондинки отдают предпочтение фирме K, то девушка с короткой стрижкой предпочитает фирму M;

2) если девушки с длинными волосами предпочитают фирму K, то девушка, не работающая в фирме D, покупает одежду в фирме L, а блондинки – в фирме M;

3) если девушки, носящие туфли на высоких каблуках, отдают предпочтение фирме L, то не блондинки покупают одежду в фирме K;

4) если девушки, не носящие туфель на высоких каблуках, покупают одежду в фирме K, то, девушки на туфлях с высокими каблуками предпочитают магазины фирмы M.

Необходимо проверить выполнимость этих условий.

Для формализации условий задачи имена девушек можно записать в виде множества {a, b, c, d}. Тогда множество блондинок будет A={a, b}, множество девушек с короткой стрижкой B = {c}, множество девушек, носящих высокие каблуки, C = {a, d}, и множество девушек, работающих в фирме D, D = {a, b, c}.

Пусть предикат Y(z) обозначает девушек с признаком Y, отдающих предпочтение фирме Z. Тогда условия задачи можно записать в виде следующей логической формулы:

P(k, l, m) = ($\neg$A(k) $\supset$ B(m)) $\wedge$ ($\neg$B(k) $\supset$ $\neg$D(l)) $\wedge$ ($\neg$B(k) $\supset$ A(m)) $\wedge$

$\wedge$ (C(l)) $\supset$ $\neg$A(k)) $\wedge$ ($\neg$C(k) $\supset$ C(m)).

Следует отметить одну особенность этой задачи. При распознавании выполнимости в формулах исчисления предикатов обязательным завершающим этапом их решения является алгоритм унификации, в результате которого исходная задача преобразуется в задачу исчисления высказываний, которая решается различными методами, в частности, методом резолюций [15]. Предложенная задача выходит за рамки задач исчисления высказываний, тем не менее, её можно решить без преобразования в формулу исчисления высказываний. Для этого можно воспользоваться алгоритмом преобразования D-системы в C-систему (теорема 25), а для уменьшения трудоёмкости алгоритма – методом ортогонализации.

Сначала преобразуется исходная формула в КНФ:

P(k, l, m) = (A(k) $\vee$ B(m)) $\wedge$ (B(k) $\vee$ $\neg$D(l)) $\wedge$ (B(k) $\vee$ A(m)) $\wedge$

$\wedge$ ($\neg$A(k) $\vee$ $\neg$C(l))) $\wedge$ (C(k) $\vee$ C(m)).

Для преобразования формулы P(k, l, m) в D-систему выбирается универсум K $\times$L $\times$ M = {a, b, c, d}³, а интерпретации предикатов A(x), B(x), C(x), D(x) используются в качестве компонент A, B, C, D в соответствующих атрибутах. Например, второй дизъюнкт (B(k) $\vee$ ØD(l)) записывается как D-кортеж P₂[KL] = ]B $\overline{D}$[. Если применить операцию +Atr, то в схеме отношения [KLM] он выражается как P₂[KL] = ]B $\overline{D}$ $\varnothing$[.

После преобразования всех дизъюнктов в однотипные D-кортежи получается:

P[KLM] =$\left]\begin{array}{ccc}A& \varnothing & B\\ B& \overline{D}& \varnothing \\ B& \varnothing & A\\ \overrightarrow{A}& \overline{C}& \varnothing \\ C& \varnothing & C\end{array}\right[$= $\left]\begin{array}{ccc}\{a,b\}& \varnothing & \left\{c\right\}\\ \left\{c\right\}& \left\{d\right\}& \varnothing \\ \left\{c\right\}& \varnothing & \{a,b\}\\ \{c,d\}& \{b,c\}& \varnothing \\ \{a,d\}& \varnothing & \{a,d\}\end{array}\right[$.

Обозначив D-кортежи с номером i в D-системе P[KLM] как P_i, можно приступить к вычислениям, используя теоремы 2, 3, 8, 25 и 27.

P₁ $\cap$ P₂ = $\left[\begin{array}{ccc}\{a,b\}& \ast & \ast \\ \{c,d\}& \ast & \left\{c\right\}\end{array}\right]$$\cap$$\left[\begin{array}{ccc}\left\{c\right\}& \ast & \ast \\ \{a,b,d\}& \left\{d\right\}& \ast \end{array}\right]$=$\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \ast \\ \left\{c\right\}& \ast & \left\{c\right\}\\ \left\{d\right\}& \left\{d\right\}& \left\{c\right\}\end{array}\right]$.

P₁ $\cap$ P₂ $\cap$ P₃ =$\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \ast \\ \left\{c\right\}& \ast & \left\{c\right\}\\ \left\{d\right\}& \left\{d\right\}& \left\{c\right\}\end{array}\right]$$\cap$$\left[\begin{array}{ccc}\left\{c\right\}& \ast & \ast \\ \{a,b,d\}& \ast & \{a,b\}\end{array}\right]$=$\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \{a,b\}\\ \left\{c\right\}& \ast & \left\{c\right\}\end{array}\right]$.

P₁ $\cap$ P₂ $\cap$ P₃ $\cap$ P₄ =$\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \{a,b\}\\ \left\{c\right\}& \ast & \left\{c\right\}\end{array}\right]$$\cap$$\left[\begin{array}{ccc}\{c,d\}& \ast & \ast \\ \{a,b\}& \{b,c\}& \ast \end{array}\right]$= [{c} * {c}].

P₁ $\cap$ P₂ $\cap$ P₃ $\cap$ P₄ $\cap$ P₅ = [{c} * {c}] $\cap$$\left[\begin{array}{ccc}\{a,d\}& \ast & \ast \\ \{b,c\}& \ast & \{a,d\}\end{array}\right]$= $\varnothing$.

Отсюда следует, что условия задачи невыполнимы.

Задача 2. Некоторые пациенты любят всех докторов. Ни один пациент не любит знахарей. Следовательно, никакой доктор не является знахарем. Проверить корректность этого рассуждения. В [15] эта задача решается двумя способами: сначала с помощью интерпретации (пример 3.15), затем методом резолюций с использованием алгоритма унификации (пример 5.21). Эту задачу можно решить с помощью АК.

Пусть заданы множества P – пациенты, D – доктора, Q – знахари, P₁ $\subseteq$ P – некоторые пациенты, L[XY] – отношение «x любит y», заданное как C-система.

Тогда первая посылка: A₁[XY] = [P₁  D].

Вторая посылка: A₂[XY] = L[XY] $\cap$ [P $\overline{Q}$] (при пересечении образуется C-система, в которой из атрибута X исключены все не пациенты, а из атрибута Y – все знахари).

Вычисляется минимальное следствие:

A[XY] = L[XY] Ç [P₁  D] $\cap$ [P  $\overline{Q}$] = L[XY] $\cap$ [P₁  D$\cap$$\overline{Q}$].

Анализ заключения. Можно предположить противное, т.е. что некоторые доктора – знахари. Это означает, что D$\cap$Q = Q₁ $\ne$ $\varnothing$. Множество Q₁ может присутствовать в атрибуте Y отношения L[XY], поэтому в качестве отрицания заключения выбирается C-кортеж [*  Q₁] и вычисляется его пересечение с минимальным следствием:

A[XY] $\cap$ [*  Q₁] = L[XY] $\cap$ [P₁  D$\cap$Q₁$\cap$$\overline{Q}$] = $\varnothing$, т.к. Q₁$\cap$$\overline{Q}$= $\varnothing$ и, следовательно, [P₁  D$\cap$Q₁$\cap$$\overline{Q}$] = $\varnothing$ (теорема 3) и L[XY] $\cap$ $\varnothing$ = $\varnothing$. Отсюда ясно, что заключение корректно.

3. Свойства интересных следствий

Многочисленные примеры задач логического вывода [10, 15, 22] характеризуются тем, что часто проверяемые следствия содержат небольшой, по сравнению с исходными данными, состав переменных.

В задаче Steamroller (№ 47 в [22]) при формализации получается три логических переменных, но в ней сокращение осуществляется для предикатов, используемых в этой задаче. К этим предикатам относятся «волки», «лисы», «растения», «меньше» и т.д. Следствие этой задачи содержит три предиката, в то время как в посылках приведено 10 разных предикатов. Таким образом, одно из свойств интересных следствий – сокращённый по сравнению с исходными данными состав переменных или предикатов.

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

Ещё одно свойство интересных следствий было установлено при исследовании задач с сокращённым составом переменных в следствии. Нередко результатом вычислений становится формула с большим объёмом записей (например, C-система с большим числом C‑кортежей). Можно сократить объём записи следствия, в частности, представить его в виде одного или двух дизъюнктов. Таким образом, третье свойство интересных следствий – сокращённый объём записи.

Теорема о проекциях. Пусть задана C-система R[W], где W – множество атрибутов из схемы отношения R, и V $\subset$ W. Тогда

R[W]${\subseteq }_G$Pr_V(R).   (3)

Доказательство. Пусть в множестве W содержится n атрибутов, а в множестве V – k атрибутов. Не нарушая общности, можно считать, что все атрибуты из V содержатся в левой части C-системы R[W] (перестановка столбцов в матричном представлении АК-объектов вместе с соответствующими перестановками имён атрибутов в схеме отношения является эквивалентным преобразованием). Пусть

R[W] = $\left[\begin{array}{cccccc}{С}_1^1& \mathrm{...}& C_1^k& C_1^{k+1}& \mathrm{...}& C_1^n\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ C_m^1& \mathrm{...}& C_m^k& C_m^{k+1}& \mathrm{...}& C_m^n\end{array}\right]$. Тогда Pr_V(R) =$\left[\begin{array}{ccc}{C}_1^1& \mathrm{...}& C_1^k\\ \mathrm{...}& \mathrm{...}& \mathrm{...}\\ C_m^1& \mathrm{...}& C_m^k\end{array}\right]$. Для проверки обобщённого включения (3) необходимо добавить в Pr_V(R) недостающие фиктивные атрибуты. Результатом является C-система

Q[W] =$\left[\begin{array}{cccccc}{С}_1^1& \mathrm{...}& C_1^k& \ast & \mathrm{...}& \ast \\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ C_m^1& \mathrm{...}& C_m^k& \ast & \mathrm{...}& \ast \end{array}\right]$, у которой правые n–k столбцов содержат только полные компоненты. Если сравнивать C-кортежи C_i из R[W] и Q[W], то, используя теорему 1, можно убедиться, что каждый C-кортеж из R включён в соответствующий C-кортеж из Q, что доказывает теорему.

4. Методы вычисления интересных следствий

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

Когда задано множество АК-объектов {A₁, A₂, …, A_n}, представляющих аксиомы (или посылки), то нужно вычислить минимальное следствие A = A₁ $\cap$_G A₂ $\cap$_G … $\cap$_G A_n. Тогда для вычисления любого следствия достаточно построить АК-объект B такой, чтобы выполнялось соотношение A${\subseteq }_G$B. Из (3) следует, что любая проекция A является его следствием. Одним из методов вывода следствий с сокращённым составом атрибутов может быть вычисление проекций минимального следствия A.

4.1 Вычисление следствий с сокращённой схемой отношения

Если A – C-система, то любую её проекцию легко вычислить с помощью элиминации атрибутов. При этом не всякая проекция представляет интересное следствие, т.к. могут быть проекции, равные универсуму – в этом случае они не содержат полезной информации.

В качестве примера можно рассмотреть задачу 1 из раздела 2. Пусть в задаче используются только первые два условия (т.е. первые три D-кортежа из D-системы P[KLM]). Соответствующий промежуточный результат решения задачи 1 имеет вид:

A[KLM] = P₁ $\cap$ P₂ $\cap$ P₃ =$\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \{a,b\}\\ \left\{c\right\}& \ast & \left\{c\right\}\end{array}\right]$.

Любая проекция A[KLM] является следствием. Проекции Pr_K(A)= {a, b, c} и Pr_L(A) = * являются формальными следствиями, в которых содержатся сведения о подругах, предпочитающих магазины определённой фирмы. Из содержания проекций ясно, что в фирме K совершают покупки только девушки, работающие в фирме D, в то время как товары фирмы L желательны для всех подруг.

4.2 Вычисление следствий с заданным составом атрибутов

Задача поиска следствий с заданным составом атрибутов решается также с помощью вычисления и анализа соответствующих проекций минимального следствия. В качестве примера можно рассмотреть следующую задачу исчисления высказываний. Пусть посылки заданы дизъюнктами: $\neg$P$\vee$Q$\vee$R;  $\neg$P$\vee$$\neg$Q$\vee$$\neg$S;  $\neg$P$\vee$Q$\vee$$\neg$R$\vee$S;  P$\vee$$\neg$R;  P$\vee$R$\vee$S.

Требуется выяснить, может ли следствием данной задачи быть формула, содержащая только пропозициональные переменные P и Q (другой вариант: Q и S)?

В АК все задачи и формулы исчисления высказываний можно выразить АК-объектами, у которых атрибутами являются имена пропозициональных переменных, а в качестве их доменов используется множество {0, 1}. При этом литералу X соответствует компонента {1}, а литералу $\neg$X – компонента {0}. Тогда конъюнкт, например, P$\wedge$$\neg$R$\wedge$S можно выразить как C‑кортеж A₁[PRS] = [{1}  {0}  {1}], а дизъюнкт P$\vee$$\neg$R – как D-кортеж A₂[PR] = ]{1}  {0}[.

Выразив посылки задачи в виде D-кортежей и применив операцию +Atr, можно построить D систему: A[PQRS] =$\left]\begin{array}{cccc}\left\{0\right\}& \left\{1\right\}& \left\{1\right\}& \varnothing \\ \left\{0\right\}& \left\{0\right\}& \varnothing & \left\{0\right\}\\ \left\{0\right\}& \left\{1\right\}& \left\{0\right\}& \left\{1\right\}\\ \left\{1\right\}& \varnothing & \left\{0\right\}& \varnothing \\ \left\{1\right\}& \varnothing & \left\{1\right\}& \left\{1\right\}\end{array}\right[$.

С помощью методов, изложенных в разделе 1.1, можно преобразовать D-систему A[PQRS] в C‑систему. Тогда получается минимальное следствие: A[PQRS] =$\left[\begin{array}{cccc}\left\{0\right\}& \ast & \left\{0\right\}& \left\{1\right\}\\ \left\{1\right\}& \left\{1\right\}& \ast & \left\{0\right\}\\ \left\{1\right\}& \left\{0\right\}& \left\{1\right\}& \left\{1\right\}\end{array}\right]$.

Для решения задачи рассматривается сначала проекция Pr_PQ(A), которая содержит четыре разных элементарных кортежа, что говорит о том, что она равна универсуму и не годится для следствия (универсум является следствием для любых посылок). Проекция Pr_QS(A) содержит три элементарных кортежа: [{0} {1}], [{1} {0}] и [{1} {1}]. По таблице истинности им соответствует формула Q$\vee$S. Следовательно, эта формула есть решение задачи.

Используя теорему 20, можно проверить то, что полученный результат действительно является следствием. Для этого можно выразить формулу Q$\vee$S как D-кортеж B[PQRS] = ]$\varnothing$ {1} $\varnothing$ {1}[ и проверить включение каждого C-кортежа из C-системы A[PQRS] в D-кортеж B[PQRS].

4.3 Сокращение объёмов записи в следствиях

При вычислении следствий могут получаться C-системы, содержащие значительное число C-кортежей. Во многих случаях C-системы трудно преобразовать так, чтобы в них содержалось меньшее число C-кортежей, однако объём записи минимального следствия или его неполных проекций можно существенно уменьшить с помощью других методов АК.

Пусть известно следствие A с большим объёмом записи. Тогда можно вычислить $\overline{A}$ и каким-то образом выделить его часть A_j $\subset$ $\overline{A}$ с малым объёмом записи. При вычислении его дополнения методами АК также получится АК-объект $\overline{A_j}$ с малым объёмом записи, и при этом в силу закона контрапозиции будет соблюдаться соотношение A$\subset$$\overline{A_j}$, что позволяет выбрать $\overline{A_j}$ в качестве искомого следствия.

Пусть в задаче 1 из раздела 2 в качестве посылок используются первые два D-кортежа D-системы P[KLM].

Промежуточный результат имеет вид:

A[KLM] = P₁ $\cap$ P₂ = $\left[\begin{array}{ccc}\{a,b\}& \left\{d\right\}& \ast \\ \left\{c\right\}& \ast & \left\{c\right\}\\ \left\{d\right\}& \left\{d\right\}& \left\{c\right\}\end{array}\right]$, $\overline{A}$[KLM] =$\left]\begin{array}{ccc}\{c,d\}& (a,b,c\}& \varnothing \\ \{a,b,d\}& \varnothing & \{a,b,d\}\\ \{a,b,c\}& \{a,b,c\}& \{a,b,d\}\end{array}\right[$

.

Чтобы выделить часть полученной D-системы, необходимо преобразовать её в C-систему c помощью известного алгоритма.

Тогда получается: $\overline{A}$ [KLM] =$\left[\begin{array}{ccc}\left\{d\right\}& \{a,b,c\}& \ast \\ \left\{d\right\}& \left\{d\right\}& \{a,b,d\}\\ \left\{c\right\}& \ast & \{a,b,d\}\\ \{a,b\}& \{a,b,c\}& \ast \end{array}\right]$.

Из этой C-системы выбирается какой-либо C-кортеж, например, A_j[KLM] = [{d} {a, b, c} *] и вычисляется его дополнение $\overline{A_j}$ [KLM] = ]{a, b, c} {d} $\varnothing$ [.

В $\overline{A_j}$ [KLM] можно удалить фиктивный атрибут. Тогда получается следующий результат: D-кортеж $\overline{A_j}$ [KL] = ]{a, b, c} {d}[ является следствием задачи. Его можно выразить как дизъюнкт с соответствующими предикатами, определёнными в задаче 1.

Полученный результат легко проверяется. Для этого, используя теорему 20, достаточно проверить включение каждого C-кортежа из C-системы A[KLM] в D-кортеж $\overline{A_j}$[KLM].

Таким образом, одним из методов сокращения объёма записи следствия A является следующий порядок действий:

• вычислить дополнение A и преобразовать его в C-систему;
• если в полученной C-системе много C-кортежей, то удалить некоторые из них;
• вычислить дополнение структуры, полученной на предыдущем шаге.

Заключение

Для заданной системы посылок предложены алгоритмы вычисления следствий со следующими свойствами:

• с сокращённым составом переменных;
• с заданным составом переменных;
• с сокращённым объёмом записи.

Во всех случаях используется понятие минимального следствия, представляющего собой обобщённое пересечение АК-объектов, которые моделируют посылки. Интересные следствия в ряде случаев являются неполными проекциями минимального следствия.

Значительная часть современных классических и неклассических логических систем предусматривает для вывода новых следствий механизм исчислений, т.е. получение результатов на основе правил вывода. В АК наряду с этим механизмом предлагается получение новых следствий с помощью вычислений, т.е. на основе алгоритмов, позволяющих получить требуемый результат с помощью определённых операций над заданными в условии задачи структурами. В некоторых случаях, в частности, в задаче вычисления следствий с заранее заданными свойствами, этот метод имеет определённые преимущества.

¹ Формулировки теорем из [9], номера которых упоминаются в тексте данной статьи, приведены в разделе 1.2.

² Законы де Мо́ргана — логические правила, связывающие пары логических операций при помощи логического отрицания.

Об авторах

Борис Александрович Кулик

Автор, ответственный за переписку.
Email: ba-kulik@yandex.ru
Scopus Author ID: 6603756784
ResearcherId: F-1539-2014

д.ф.-м.н., ведущий научный сотрудник лаборатории Интеллектуальных электромеханических систем Института проблем машиноведения РАН, член Российской ассоциации искусственного интеллекта

Список литературы

Дополнительные файлы