Стратегии резолюции. 
Системы поддержки принятия решений часть 1

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

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

Начинается он с поиска резольвент между предложениями базового множества. Базовым будем называть множество предложений посылок вкупе с предложениями, полученными при отрицании заключения. Это будут резольвенты первого уровня. По мерс их вычисления они подсоединяются к концу списка предложений. Далее вычисляются резольвенты второго уровня как результаты резолюций базового множества дизъюнктов и дизъюнктов первого уровня или их потомков и т. д. Метод можно проследить на простом примере.

Пример 3.17

Пусть S — заданное множество (четыре дизъюнкта).

Этот бесхитростный перебор не сулит быстрого успеха, но зато гарантирует нахождение пустого дизъюнкта (если он, конечно, имеется). Такая стратегия называется полной. По указанной стратегии дизъюнкт Л будет 39-м!

Из данного примера следуют важные выводы. Так, оказалось, что было порождено много ненужных, а потому — лишних дизъюнктов. Многие из них повторяются: 5 и 17, 6 и 18, 13—16. Некоторые являются тавтологиями — 7—10. При поиске методом опровержения мы ищем невыполнимый дизъюнкт, и эту невыполнимость нам нельзя потерять. Тавтологии же всегда выполнимы, к делу не относятся и могут быть вычеркнуты, иначе они сами начнут порождать лишние резольвенты. Если из списка порождаемых дизъюнктов исключать повторяющиеся, а также тавтологии, то число резольвент значительно уменьшится и метод полного перебора окажется не таким уж громоздким. Его можно еще более оптимизировать, если применить так называемый принцип подсуммирования (поглощения).

Пусть у нас имеются такие два дизъюнкта С и D, что С = A, D = A v В. Далее С, как видим, является составной частью D. Говорят, что С подсуммирует D. Если теперь окажется, что D невыполним (= Л), то по свойству дизъюнкции С = А = Л. Замена D на С сохраняет невыполнимость, и D можно просто отбросить: С поглощает D.

Примеры подсуммирования:

П:

Л v В v R,

Р (У) v Q (z),.

P (f (A)) v Q (B) v R (z),

P (q (y)) v Q (f (q (y)), a) V R (z).

С:

Л v R Р (х)

Р (х) V <2(?).

Р (х) v Q (f (x), а)

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

Вычеркивая ненужные дизъюнкты и применяя подсуммирование, мы в определенном смысле видоизменяем сам метод полного перебора. Мы применяем теперь стратегию упрощения. Обладая полнотой исходного метода, такая стратегия существенно сокращает список резольвент. Алгоритм перебора остается прежним, но каждая возникающая резольвента анализируется и при необходимости отбрасывается. Так, рассмотренный выше пример разрешится следующим образом.

Резолюции:

• 5) Q (1,2)
• 6) Р, (1,3)
• 7) Р, (2, 4)
• 8) Q, (3, 4)
• 9) Л, (5, 8) — начало второго уровня.