Выполнимые формулы и проблема разрешения

Формула логики предикатов называется выполнимой на множестве X, если она превращается в истинное высказывание при некоторой интерпретации ее на этом множестве. Формула общезначима, если ее отрицание невыполнимо ни на одном множестве. Это простое замечание показывает, что проблема разрешения может рассматриваться применительно к выполнимым формулам. Несмотря на отрицательное решение общей проблемы, тем не менее, сужая проблему, иногда удается найти соответствующие алгоритмы (например, построение таблиц истинности для формул, которые содержат только высказывания).

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

Пример.Проверим выполнимость формулы

∀x∃y(P(y,y)∧P(x,y))

на двухэлементном множестве {a,b}. Имеем:

[∀x∃y(P(y,y)∧P(a,y))] =

= [∃y(P(y,y)∧P(a,y))] ∧ [∃y(P(y,y)∧P(b,y))] =

= ([(P(a,a)∧P(a,a))] ∨ [(P(b,b)∧P(a,b))]) ∧

∧ ([(P(a,a)∧P(b,a))] ∨ [(P(b,b)∧P(b,b))]).

Полагая

A=P(a,a), B=P(a,b), C=P(b,a), D=P(b,b),

получаем

[∀x∃y(P(y,y)∧P(a,y))] =

= ([A∧A]∨[D∧B]) ∧ ([A∧C]∨ [D∧D]).

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

D∧B∧A∧C.

Если в итоговом столбце встречается хотя бы один раз значение 1, исходная формула логики предикатов выполнима. В данном случае легко убедиться, что это так.􀀀

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

Теорема.Если формула логики предикатов, содержащая только одноместные предикатные символы, выполнима, то она выполнима на конечном множестве, содержащем не более 2ⁿ переменных, где n – число различных предикатных символов, входящих в рассматриваемую формулу.

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

Пример.Рассмотрим формулу

(∀x∃yP(x,y)) ∧ (∀x(P(x,x)) ∧ (∀x∀y∀z((P(x,y)∧P(y,z))→P(x,z)). Предикат P(x,y) можно трактовать как упорядочение (x предшествует y). Второй и третий конъюнктивные члены говорят о том, что упорядочение антирефлексивно и транзитивно. Первый говорит о том, что для каждого элемента существует следующий за ним. Если интерпретировать P(x,y) как x<y на множестве натуральных чисел, рассматриваемая формула станет истинной. Значит, она выполнима на бесконечном множестве.

Нетрудно показать, что формула не выполнима ни на каком конечном множестве. Предположим, что формула выполнима на некотором непустом множестве X, и P(x,y) – некоторый предикат на этом множестве, который превращает формулу в истинное высказывание. Пусть a∈X. Существует b∈X такое, что P(a,b). Так как P(a,a) и P(b,b) должны быть ложны, a отлично от b. В свою очередь для b найдется такое c∈X, отличное от b, что P(b,c). По транзитивности заключаем, что P(a,c). Но тогда a и c различны. Продолжая подобные построения, можно продолжить цепочку a,b,c, …, состоящую из различных элементов сколь угодно далеко. Если множество X конечно, сделать это невозможно.􀀀