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

Введение

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

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

Дата добавления: 2014-01-07