Логические основы Пролога

Введение в язык Пролог

Название языка «Пролог» происходит от слов «ЛОГическое ПРОграммирование». Пролог основывается на таком разделе математической логики, как исчисление предикатов.

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

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

Основные области языка Пролог:

· автоматизированный перевод с одного языка на другой

· быстрая разработка интерфейсов для существующих систем

· символьные вычисления для решения уравнений, дифференцирование и интегрирование

· экспертные системы и оболочки

· автоматическое доказательство теорем

· полуавтоматическое составление расписаний

· САПР

Области, для которых Пролог не предназначен: большой объем арифметических вычислений (обработка аудио, видео и т.д.); написание драйверов.

Логические основы Пролога

Задана формализованная система F, если определены:

1. Алфавит – счетное множество символов

2. Формулы системы – некоторое подмножество всех слов, которое можно образовать из символов, входящих в алфавит

3. Аксиомы – выделенное множество формул системы

4. Правила вывода системы – конечное множество отношений между формулами системы.

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

Алфавит логики первого порядка составляют следующие символы:

1. переменные (будем обозначать их последними буквами английского алфавита u, v, x, y, z);
2. константы (будем обозначать их первыми буквами английского алфавита a, b, c, d);
3. функциональные символы (используем для их обозначения ближние буквы f и g);
4. предикатные символы (обозначим их дальними буквами p, q и r);
5. пропозициональные константы истина и ложь (true и false);
6. логические связки (отрицание), (конъюнкция), (дизъюнкция), (импликация);
7. кванторы: (существования), (всеобщности);
8. вспомогательные символы (, ), ,.

Если предикатный или функциональный символ имеет N – аргументов, он называется N-местным предикатным или функциональным символом.

Терм – выражение, образованное из переменных и констант, возможно с применением функций. Все объекты в Пролог представляются в виде Термов.

Атомная (элементарная) формула получается путём применения предиката к термам.

Формулы логики первого порядка получаются следующим образом:

1. Всякая атомная формула есть формула

2. Если А и В – формулы, х – переменная, тогда - тоже формулы.

3. Других формул нет

Литералом называют атомную формулу или отрицание атомной формулы. Атом называют положительным литералом, а его отрицание – отрицательным литералом.

Дизъюнкт – дизъюнкция конечного числа литералов. Если дизъюнкт не содержит литералов, его называют пустым дизъюнктом.

КНФ – конъюнкция конечного числа дизъюнктов.

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

Унификация позволяет отождествлять формулы логики 1-го порядка путем замены свободных переменных на термы.