5.12.3. Задача из области формальной логики

В данном случае рабочим пространством являются высказывания на языке логики первого порядка, но от читателя никаких знаний в этой области не требуется: можно рассматривать все это как игру, в которой мы должны манипулировать цепочками букв в соответствии с определенными правилами. Кстати, прежде чем эта задача была запущена в программу GPS, два американских психолога О. Моор и С. Андерсон (1954) предложили ее студентам, чтобы постараться понять, как действует человек в подобных ситуациях. Напомним, что в то время алгоритм унификации еще не был известен (см. гл. 3).

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

Ниже приведены разрешенные преобразования:

Символы с индексами 1—11 не входят в правила и являются порядковыми номерами правил.

Символ расположенный между двумя цепочками символов читается как “можно также записать”; он означает, что мы всегда можем преобразовать в Двойная стрелка означает, что одновременно

Кроме того, при переписывании всегда разрешается заменить любую букву, встретившуюся в рассматриваемом правиле, на любую другую, при условии что такая замена будет произведена по обе стороны знака

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

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

Таким образом, начав с цепочки мы можем применить правило (Р соответствует ) и получить

Теперь мы можем применить правило (использована замена А на и В на в результате чего выражение приводится к следующему виду

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

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

Таблица 5.12. (см. скан) Таблица зависимостей для решения логической задачи с помощью

Характер возможных различий между объектами здссь более разнообразен. В самом деле, в двух произвольных цепочках может быть:

1) разное число букв: увеличивающееся или уменьшающееся

2) разное число символов

3) разное число прочих связок

4) измененная расстановка скобок

5) перестановка порядка букв

Анализируя действия, которые оказывают на эти различия наши правила, можно построить таблицу зависимостей (табл. 5.12).

Здесь мы не задаем относительного порядка различий. Теперь для программы GPS имеем:

исходный объект

конечный объект .

Решение. Первое различие между двумя объектами, зафиксированное программой, состоит в исчезновении в конечном

объекте переменной Итак, первая порождаемая нами цель — по переменной Как следует из таблицы зависимостей (обозначения остались те же), достичь этой цели можно с помощью правил . Правило (единственное среди всех) может быть непосредственно применено к левой части оно порождает новый объект:

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

Левые части правил в данный момент не могут быть поставлены в соответствие цепочке Итак, мы отмечаем различия и добавляем подцели типа левая часть где . Кроме того, программа GPS отмечает, что правило может быть применено к некоторым другим способом.

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

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

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

(кликните для просмотра скана)

(см. скан)

Программа GPS продолжает поиск. Прежде чем прийти к изображенной ниже схеме, она уже породила 52 цели:

(см. скан)

(см. скан)

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

Конечно, нередко мы хорошо “чувствуем” рабочее пространство, что иногда позволяет нам действовать более прямо и менее тупо, чем программа GPS. Но ведь мы также способны и быстро сдаваться там, где GPS продолжает работать и в конце концов добивается результата!

На рис. 5.31 приведено дерево поиска для данной задачи.