Программирование на языке пролог (ЛП)

Полнота метода резолюций является полезным математическим свойством. Это свойство означает, что, если некоторый факт следует из гипотез, то имеется возможность доказать его истинность (показав несовместность множества дизъюнктов, содержащего гипотезы и отрицание доказываемого факта)» используя для этого метод резолюций. Однако, когда мы говорим, что методом резолюций можно вывести пустой дизъюнкт, это значит, что существует последовательность шагов, на каждом из которых правило резолюций применяется к аксиомам или к дизъюнктам выведенным на предыдущих шагах, и эта последовательность заканчивается выводом дизъюнкта, не содержащего литералов. Единственная проблема – найти соответствующую последовательность шагов. Так как, хотя метод резолюций и говорит о том, как получить следствие двух дизъюнктов, он не сообщает, какие дизъюнкты выбрать для очередного шага и какие литералы в этих дизъюнкциях необходимо «сопоставить». Обычно, если имеется большое количество гипотез, то существует и много вариантов выбора среди них. Более того, на каждом шаге выводится новый дизъюнкт и он тоже становится кандидатом на участие в последующей обработке. Большинство из имеющихся возможностей выбора дизъюнктов и литералов в них не имеют отношения к решаемой задаче и, если не производить тщательного отбора среди кандидатов, то можно потратить слишком много времени на бесплодные поиски, а путь, ведущий к решению, так и не найти.

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

10.5. Хорновские дизъюнкты

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

Прежде всего, очевидно, что существуют два вида хорнов-ских дизъюнктов – дизъюнкты, содержащие один литерал без отрицания и дизъюнкты, не содержащие таких литералов. Будем называть эти два типа хорновских дизъюнктов соответственно дизъюнктами с заголовкоми дизъюнктами без заголовка.Следующие примеры иллюстрируют указанные типы дизъюнктов (необходимо помнить, что литералы без отрицания записываются слева от знака ':-'):

холостяк(Х):- мужчина(Х), неженат(Х).

:- холостяк(Х).

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

•Имеется только один дизъюнкт без заголовка. Все остальные дизъюнкты имеют заголовки.

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

Почему мы должны рассматривать лишь такие совокупности хорновских дизъюнктов, которые вписываются в эту схему? Во-первых, легко видеть, что для того, чтобы задача была разрешима, необходимо наличие по крайней мере одного дизъюнкта без заголовка. Это объясняется тем, что в результате применения правила резолюций к двум хорновским дизъюнктам с заголовками вновь получается хорновский дизъюнкт с заголовком. Поэтому, если все дизъюнкты имеют заголовки, то единственное что можно делать – это выводить другие дизъюнкты с заголовками. Так как пустой дизъюнкт не имеет заголовка, то он никогда не будет выведен. Второе требование – это необходим лишь один дизъюнкт без заголовка – обосновать несколько труднее. Од-нако оказывается, что, если среди аксиом имеют несколько дизъюнктов без заголовка, то каждое доказательство нового дизъюнкта методом резолюций может быть преобразовано в доказательство, в котором используется не более чем один из них. Поэтому, если пустой дизъюнкт следует из данного множества аксиом, то он следует и из его подмножества, содержащего все дизъюнкты с заголовками и не более одного дизъюнкта без заголовка.

10.6. Пролог