Примеры использования дизъюнкции в Прологе

Предложения в Прологе бывают трех видов:

· факт – предложение, у которого нет тела. В терминах логики предикатов, факт – это и есть предикат. Например, факт, что Наташа является мамой Даши, может быть записан в виде[2]:

mama('Наташа', 'Даша').

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

grandmama(X, Y):-

mama(X, Z), mama(Z, Y).

grandmama(X, Y):-

mama(X, Z), papa(Z, Y).

или

grandmama(X, Y):-

mama(X, Z), mama(Z, Y);

mama(X, Z), papa(Z, Y).

или

grandmama(X, Y):-

mama(X, Z), (mama(Z, Y); papa(Z, Y)).

· вопрос (запрос, цель) – предложение, состоящее только из тела. Автоматическая система логического вывода Пролога рассматривает вопрос как цель, к которой надо стремиться. Если цель будет достигнута, Пролог выдает положительный ответ (true), иначе – отрицательный (false). Обычно в интерпретаторах Пролога вопросы задаются в отдельном командном окне и перед каждым новым вопросом ставится «?-». Например, вопросы с ответами «Наташа является мамой Даши?» и «Кто является мамой Даши?» выглядят:

?- mama('Наташа', 'Даша').

true.

и

?- mama(X, 'Даша').

X='Наташа'.

Предложения, записанные с использованием перевернутой импликации, называются фразами Хорна. Разновидности предложений Пролога, записанные в виде фраз Хорна (B A), можно интерпретировать следующим образом:

· факт: B true;

· правило: B A;

· вопрос: true A.

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

Переменные могут быть свободными или связанными.

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

Переменная, которая получила какое-то значение, называется связанной. Такой переменной не может быть присвоено новое значение, т. е., по сути, переменная становится константой.

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно и то же имя переменной для обозначения разных сущностей. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания «_». Анонимная переменная предписывает интерпретатору (компилятору) проигнорировать значение аргумента (терма). Если в правиле несколько анонимных переменных, то все они отличаются друг от друга, несмотря на то, что записаны с использованием одного и того же символа «_». Анонимные переменные могут записываться только в качестве терма предиката. Использовать их в выражениях (например, арифметических) нельзя. Пример использования анонимной переменной в вопросе «Есть ли у Даши мама?»:

?- mama(_, 'Даша').

true.

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

Для поиска ответа на вопрос (доказательства целевого утверждения)
в Прологе используется метод перебора с возвратами[3] (поиск в глубину).
В то же время, за счет структуры и порядка формул можно добиться реализации поиска в ширину.