Фраза хорна в общем случае состоит из

Обновлено: 04.11.2024

Фразы Хорна (Horn clause) представляют собой подмножество фраз, содержащих только один позитивный литерал. В общем виде фраза Хорна представляется выражением.

В языке PROLOG эта же фраза записывается в таком виде (обратите внимание на символ точки в конце): р: -q₁,…,q_n. Такая фраза интерпретируется следующим образом:

"Для всех значений переменных в фразе p истинно, если истинны q₁ и… и q_n", т.е. пара символов ":-" читается как "если", а запятые читаются как "и".

PROLOG – это не совсем обычный язык программирования, в котором программа состоит в основном из логических формул, а процесс выполнения программы представляет собой доказательство теоремы определенного вида.

Фраза в форме: р: -q₁,…,q_n. может рассматриваться в качестве процедуры. Такая процедура предполагает следующий порядок выполнения операций.

(1) Литерал цели сопоставляется с литералом р (унифицируется с р), который называется головой фразы.
(2) Хвост фразы q_l,…,q_n конкретизируется подстановкой значений переменных (или унификаторов), сформированных в результате этого сопоставления.
(3) Конкретизированные термы хвостовой части образуют затем множество подцелей, которые могут быть использованы другими процедурами.

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

Например, рассмотрим набор фраз языка PROLOG, представленных в листинге 8.1. Предположим, что a, b и с – какие-то блоки в мире блоков. Две первые фразы утверждают, что а находится на (on) b, a b находится на (on) с. Третья фраза утверждает, что X находится выше (above) Y, если X находится на (on) Y. Четвертая фраза утверждает, что X находится выше (above) Y, если существует какой-то другой блок Z, размещенный на (on) Y, и X находится выше (above) Y.

Листинг 8.1. Простая программа на языке PROLOG, определяющая отношение on (на).

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

Читайте также: