7.4. Экспертные системы, основанные на логике предикатов первого порядка

Существует классический язык, специально созданный для моделирования формальных человеческих рассуждений, — это язык математической логики. На самом деле правило продукций “ситуация возможное следствие” представляет собой теорему, несколько необычно формализованную: это логическое выражение, состоящее из утверждений, которые могут быть интерпретированы как истинные или ложные. Единственное различие состоит в том, что все экспертные правила заранее допустимы (аксиомы) даже в том случае, если их невозможно доказать. Таким образом, правила продукций очень близки к правилам преобразований, известным в математике: формальным преобразованиям выражений, преобразованиям в полугруппах, в формальных грамматиках, в логарифме Маркова. Для лучшего понимания экспертной системы представляется привлекательным использовать формализм, принятый в логике.

Большинство из рассмотренных выше экспертных систем хорошо описывается логикой высказываний (гл. 3), в которой все существенные понятия выражаются константами. Сейчас мы опишем последовательно две важные системы, а именно PROLOG и SNARK, основанные на формализме логики предикатов первого порядка (с переменными) и некоторых их приложений. На самом деле язык программирования Пролог,

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

7.4.1. Язык Пролог

Пролог — язык программирования, единицей которого является не команда, а теорема логики предикатов первого порядка (разд. 3.1.10). Теорема содержит переменные или параметры, относящиеся к квантору всеобщности: эти переменные могут быть замещены любым правильно построенным выражением языка. Переменные принадлежат -арным предикатам. Запись где — переменные, а Р - -арный предикат, интерпретируется так: истинно (Colmerauer, 1971 и Roussel, 1975). Сами предикаты в языке Пролог не могут быть включены в сферу действия кванторов. (Если предикаты находятся под знаками действия кванторов, речь идет об исчислении предикатов высших порядков, т. е. 2-го 3-го и т. д.) (Huet, 1978).

Пролог — специальный интернретатор для формул логики предикатов первого порядка. Его действие распространяется на предикаты, приведенные к нормальной дизъюнктивной форме. Любое предложение (дизъюнкция предикатов) записывается в виде

что, очевидно, интерпретируется в виде

Характерной особенностью языка Пролог является то, что он имеет дело только с хорновскими предложениями, т. е. с предложениями, которые имеют самое большее один “положительный” литерал (справа), другими словами, только одно заключение Язык запрещает иметь дело с дизъюнктивными заключениями типа Под литералом понимается любой терм или из предложения, представленного в нормальной форме.

Различные реализации языка Пролог фактически являются производными от версии языка на Фортране (Roussel, 1975), опирающейся на переносимый интерпретатор (Battani, 1973). В основном Пролог получил распространение в Португалии (Соelho, 1980), Эдинбурге (Warren, 1977), Венгрии (Szeedi, 1977) и Японии. В Японии программа создания ЭВМ “пятого поколения” предусматривает его использование в качестве микропрограммного языка завтрашнего дня. Машина EPILOG, созданная Сансонне и Алии, уже дает пример высокоэффективного

языка программирования Пролог (Тулуза, Университет П. Сабатье, 1982).

Все интерпретаторы для языка Пролог на самом деле являются иллюстрацией доказательства теорем с использованием принципа резолюции. Этот принцип, предложенный еще Эрбраном (Herbrandt, 1931), был заново воссоздан и запрограммирован Робинсоном в 1965 г. (Robinson, 1965). Он является обобщением метода доказательства от противного: принцип резолюции состоит в том, что доказывается противоречивость предложения и тем самым доказывается справедливость импликации Этот метод априори является полным и позволяет доказывать все теоремы данной формальной системы, но связан с большим объемом комбинаторных вычислений и недостаточно естествен для человека. Обычно мы очень редко рассуждаем от противного. Тем не менее интерпретирующие программы оказываются эффективнее нас...

На самом деле любое предложение языка Пролог может быть интерпретировано двумя способами: 1) процедурным образом через интерпретатор и 2) чисто логически или декларативно как простое утверждение теоремы в рабочем пространстве (гл. 3).

Программирование на языке Пролог представляет интерес по трем причинам:

1) предложения непосредственно выражают полезные утверждения (теоремы);

2) интерпретатор содержит полностью запрограммированный алгоритм унификации;

3) дерево поиска, рождаемое множеством попарных унификаций, обрабатывается в системе автоматически.

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

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

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