Логические основы Пролога
Введение
Традиционно под программой понимают последовательность операторов (команд, выполняемых компьютером). Этот стиль программирования принято называть императивным. Программируя в императивном стиле, программист должен объяснить компьютеру, как нужно решать задачу.
Противоположный ему стиль программирования — так называемый декларативный стиль, в котором программа представляет собой совокупность утверждений, описывающих фрагмент предметной области или сложившуюся ситуацию. Программируя в декларативном стиле, программист должен описать, что нужно решать. В их основе лежит формализованная человеческая логика. Человек лишь описывает решаемую задачу, а поиском решения занимается декларативная система программирования. Декларативные языки можно назвать языками наивысшего уровня, т.к. они очень близки к человеческому языку и мышлению. По статистике строка исходного текста на языке Пролог соответствует 14 строкам на императивном языке.
Основные области языка Пролог:
· автоматизированный перевод с одного языка на другой
· быстрая разработка интерфейсов для существующих систем
· символьные вычисления для решения уравнений, дифференцирование и интегрирование
· экспертные системы и оболочки
· автоматическое доказательство теорем
· полуавтоматическое составление расписаний
· САПР
Области, для которых Пролог не предназначен: большой объем арифметических вычислений (обработка аудио, видео и т.д.); написание драйверов.
Задана формализованная система F, если определены:
1. Алфавит – счетное множество символов
2. Формулы системы – некоторое подмножество всех слов, которое можно образовать из символов, входящих в алфавит
3. Аксиомы – выделенное множество формул системы
4. Правила вывода системы – конечное множество отношений между формулами системы.
Зададим логику первого порядка (или логику предикатов), на которой основывается Пролог. Язык логики предикатов — один из формальных языков, наиболее приближенных к человеческому языку.
Алфавит логики первого порядка составляют следующие символы:
- переменные (будем обозначать их последними буквами английского алфавита u, v, x, y, z);
- константы (будем обозначать их первыми буквами английского алфавита a, b, c, d);
- функциональные символы (используем для их обозначения ближние буквы f и g);
- предикатные символы (обозначим их дальними буквами p, q и r);
- пропозициональные константы истина и ложь (true и false);
- логические связки ¬ (отрицание), (конъюнкция), (дизъюнкция), (импликация);
- кванторы: (существования), (всеобщности);
- вспомогательные символы (, ), ,.
Если предикатный или функциональный символ имеет N – аргументов, он называется N-местным предикатным или функциональным символом.
Терм – выражение, образованное из переменных и констант, возможно с применением функций. Все объекты в Пролог представляются в виде Термов.
Атомная (элементарная) формула получается путём применения предиката к термам.
Формулы логики первого порядка получаются следующим образом:
1. Всякая атомная формула есть формула
2. Если А и В – формулы, х – переменная, тогда - тоже формулы.
3. Других формул нет
Литералом называют атомную формулу или отрицание атомной формулы. Атом называют положительным литералом, а его отрицание – отрицательным литералом.
Дизъюнкт – дизъюнкция конечного числа литералов. Если дизъюнкт не содержит литералов, его называют пустым дизъюнктом.
КНФ – конъюнкция конечного числа дизъюнктов.
Существуют алгоритмы приведения произвольной формулы исчисления к множеству дизъюнктов.
Унификация позволяет отождествлять формулы логики 1-го порядка путем замены свободных переменных на термы.