Основы современных компьютерных технологий
Пролог и логическое программирование - часть 2
Вычисление ответа на запрос соответствует доказательству существования такого объекта. Правила, по которым проводятся вычисления, образуют процедурную - операционную - семантику логической программы. Успехи языка Пролог обусловлены тем, что, с одной стороны, с помощью используемых в нем логических формул - хорновских дизъюнктов - можно описать многие практические задачи, а с другой - найдена простая интерпретация этих формул и построена достаточно эффективная реализация системы логического программирования.
Правило в Прологе имеет вид:
A0 где А0,А1,.. .Аm - атомы. Атом А0 называется заголовком, а А1... -Аm- телом правила. Тело 304 может быть пустым (при m=0) - такие правила называют фактами. Атом имеет вид ?(t1,t2,...tn) где ? - n-арный предикатный символ или имя отношения; t1, t2,...tn- термы. Терм - это либо имя переменной, либо константа, либо составной терм вида f (t1 ,t2. . .tn), f - n-арный функциональный символ. Функции, задаваемые логической программой, представляются в виде отношений - n-местная функция y=f(x1,x2...xn) представляется в виде (n+1)-местного отношения вида F(x1,x2...xn,y). Запрос (цель) имеет вид: < С1С2...Сr- где r ?0 и С1С2...Сr- атомы. Каждое правило допускает логическую и процедурную интерпретации (семантики). Логическая интерпретация правила A0 < Ar...Am - "истинность А0 следует из истинности А1 и истинности А2, и... и истинности Аm" или "А0 истинно, если истинны А1 и А2, и... и Аm". Таким образом, правила рассматриваются как формулы языка логики предикатов вида: ? x1, ? x2... ? xn(A1? A2?... ? Am> A0). Здесь ? - квантор общности, ? - логическая связка И, > - логическая связка ЕСЛИ - ТО. В Прологе, в силу традиции, данные формулы записываются в обратную сторону и используются другие обозначения для логических связок: ? обозначается "," (запятой) или словом and; ? обозначается ";" (точкой с запятой) или словом or ; > обозначается в теории |, а в языке программирования используется конструкция ":-" (двоеточие и минус) или слово if.
