В 1973 году "группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (от Programmation en Logique). Она и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алана Колмероэ. Программа была написана на Фортране и работала довольно медленно.
Большое значение для развития логического программирования имела работа Роберта Ковальского "Логика предикатов как язык программирования" (Kowalski R. Predicate Logic as Programming Language. IFIP Congress, 1974), в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов. Кстати, известно, что Ковальский и Колмероэ работали вместе в течение одного лета.
В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции.
В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC-10, который послужил прототипом для многих последующих реализаций Пролога. Что интересно, компилятор был написан на самом Прологе. Эта реализация Пролога, известная как "эдинбургская версия", фактически стала первым и единственным стандартом языка. Алгоритм, использованный при его реализации, послужил прототипом для многих последующих реализаций языка. Как правило, если современная Пролог-система и не поддерживает эдинбургский Пролог, то в ее состав входит подсистема, переводящая прологовскую программу в "эдинбургский" вид. Имеется, конечно, стандарт ISO/IEC 13211- 1:1995, но его поддерживают далеко не все Прологсистемы.
В 1980 году Кларк и Маккейб в Великобритании разработали версию Пролога для персональных ЭВМ.
В 1981 году стартовал вышеупомянутый проект Института по разработке методов создания компьютеров нового поколения.
На сегодня существует довольно много реализаций Пролога. Наиболее известные из них следующие: BinProlog, AMZI-Prolog, Arity Prolog, CProlog, Micro Prolog, МПролог, Prolog-2, Quintus Prolog, SICTUS Prolog, Silogic Knowledge Workbench, Strawberry Prolog, SWI Prolog, UNSW Prolog и т. д.
В нашей стране были разработаны такие версии Пролога как Пролог-Д (Сергей Григорьев), Акторный Пролог (Алексей Морозов), а также Флэнг (А. Манцивода, Вячеслав Петухин).
Стерлинг и Шапиро в книге "Искусство программирования на языке Пролог" пишут: "Зрелость языка означает, что он больше не является доопределяемой и уточняемой научной концепцией, а становится реальным объектом со всеми присущими ему пороками и добродетелями. Настало время признать, что хотя Пролог и не достиг высоких целей логического программирования, но, тем не менее, является мощным, продуктивным и практически пригодным формализмом программирования".
3. Исчисление высказываний.
Исчисление высказываний представляет собой логику неанализируемых предположений, в которой пропозициональные константы могут рассматриваться как представляющие определенные простые выражения вроде "Сократ -- мужчина" и "Сократ смертен". Строчные литеры р, q, r, ... в дальнейшем будут использоваться для обозначения пропозициональных констант, которые иногда называют атомарными формулами, или атомами.
Ниже приведены все синтаксические правила, которые используются для конструирования правильно построенных формул (ППФ) в исчислении высказываний.
(S. U) ЕслиU является атомом, то у является ППФ.
(S¬) Если U является ППФ, то --U также является ППФ.
(S. v) Если U и ф являются ППФ, то (U u ф) также является ППФ.
В этих правилах строчные буквы греческого алфавита (например, U и ф) представляют пропозициональные переменные, т.е. не атомарные формулы, а любое простое или составное высказывание. Пропозициональные константы являются частью языка высказываний, который используется для приложения исчисления пропозициональных переменных к конкретной проблеме.
Выражение -U читается как "не U", а (U v ф) читается как дизъюнкция "U или ф (или оба)". Можно ввести другие логические константы -- "л" (конъюнкция), "D" (импликация, или обусловленность), "=" (эквивалентность, или равнозначность), которые, по существу, являются сокращениями комбинации трех приведенных выше констант. .
(U ^ ф) Эквивалентно¬(¬U v ф). Читается "U и ф".
(U ф) Эквивалентно (¬U v ф). Читается "U имплицирует ф".
(U==ф) Эквивалентно (Uф)^(фU). Читается "U эквивалентно ф".
В конъюнктивной нормальной форме исчисления высказываний константы "импликация" и "эквивалентность" заменяются константами "отрицание" и "дизъюнкция", а затем отрицание сложного выражения раскрывается с помощью формул Де Моргана:
¬(U^ф) преобразуется в (¬Uv¬ф), ¬(U v ф) преобразуется в (-U^ф) , ¬¬U преобразуется в U .
Последний этап преобразований -- внесение дизъюнкций внутрь скобок: (Ј v (U ^ф))) заменяется ((ЈvU\(U)^(Јvф)).
Принято сокращать вложенность скобочных форм, отбрасывая в нормальной конъюнктивной форме знаки операций v и л. Ниже представлен пример преобразования выражения, содержащего импликацию двух скобочных форм, в нормальную конъюнктивную форму.
¬(pvq)(-p^A-q) Исходное выражение.
¬¬(pvg)v(-p^- q) Исключение~.
(pvq)v(-p^- q) Ввод - внутрь скобок.
(¬pv(pvq))v(¬pv(pvq)) Занесение v внутрь скобок.
{{-p, р, q}, {¬q, р, q} } Отбрасывание А и v в конъюнктивной нормальной форме.
Выражения во внутренних скобках -- это либо атомарные формулы, либо негативные атомарные формулы. Выражения такого типа называются литералами, причем с точки зрения формальной логики порядок литералов не имеет значения. Следовательно, для представления множества литералов -- фразы -- можно позаимствовать из теории множеств фигурные скобки. Литералы в одной и той же фразе неявно объединяются дизъюнкцией, а фразы, заключенные в фигурные скобки, неявно объединяются конъюнкцией.
Фразовая форма очень похожа на конъюнктивную нормальную форму, за исключением того, что позитивные и негативные литералы в каждой дизъюнкции группируются вместе по разные стороны от символа стрелки, а затем символ отрицания отбрасывается. Например, приведенное выше выражение
преобразуется в две фразы:
p,q<¬q.
в которых позитивные литералы сгруппированы слева от знака стрелки, а негативные справа.
Более строго, фраза представляет собой выражение вида
в котором p1..., рт q1,..., qn являются атомарными формулами, причем т=>0 и п=>0. Атомы в множестве р1,..., рт представляют заключения, объединенные операторами дизъюнкции, а атомы в множестве q1 ..., qn -- условия, объединенные операторами конъюнкции.
3.1 Исчисление предикатов
Исчисление высказываний имеет определенные ограничения. Оно не позволяет оперировать с обобщенными утверждениями вроде "Все люди смертны". Конечно, можно обозначить такое утверждение некоторой пропозициональной константой р, а другой константой q обозначить утверждение "Сократ -- человек". Но из (р л q) нельзя вывести утверждение "Сократ смертен".
Для этого нужно анализировать пропозициональные символы в форме предикатов и аргументов, кванторов и квантифщированных переменных. Логика предикатов предоставляет нам набор синтаксических правил, позволяющих выполнить такой анализ, набор семантических правил, с помощью которых интерпретируются эти выражения, и теорию доказательств, которая позволяет вывести правильные формулы, используя синтаксические правила дедукции. Предикатами обозначаются свойства, такие как "быть человеком", и отношения, такие как быть "выше, чем".
Аргументы могут быть отдельными константами, или составным выражением "функция-аргумент", которое обозначает сущности некоторого мира интересующих нас объектов, или отдельными квантифицируемыми переменными, которые определены в этом пространстве объектов. Специальные операторы -- кванторы -- используются для связывания переменных и ограничения области их интерпретации. Стандартными являются кванторы общности (V) и существования (3). Первый интерпретируется как "все", а второй -- "кое-кто" (или "кое-что").
Ниже приведены синтаксические правила исчисления предикатов первого порядка.
Любой символ (константа или переменная) является термом. Если rk является символом k-местной функции и а1 ..., <xk являются термами, то Гk(a1..., ak) является термом.
(S 40
Если Tk является символом k-местного предиката
и а1 ..., ak являются термами,
то U(а1 ..., ak) является правильно построенной формулой (ППФ).
(S. -) и (S. v)
Правила заимствуются из исчисления высказывании.
(S. V) Если U является ППФ и % является переменной,
то (любой Х) U является ППФ.
Для обозначения используются следующие символы:
U -- произвольный предикат;
Г -- произвольная функция;
a -- произвольный терм;
X -- произвольная переменная.
Действительные имена, символы функций и предикатов являются элементами языка первого порядка.
Использование квантора существования позволяет преобразовать термы с квантором общности в соответствии с определением
(EX)U определено как -(любой X)-U.
Выражение (EХ)(ФИЛОСОФ(Х)) читается как "Кое-кто является философом", а выражение (любой Х)(ФИЛОСОФ(Х)) читается как "Любой является философом". Выражение ФИЛОСОФ(Х) представляет собой правильно построенную формулу, но это не предложение, поскольку область интерпретации для переменной X не определена каким-либо квантором. Формулы, в которых все упомянутые переменные имеют определенные области интерпретации, называются замкнутыми формулами.
Как и в исчислении высказываний, в исчислении предикатов существует нормальная форма представления выражений, но для построения такой нормальной формы используется расширенный набор правил синтаксических преобразований. Ниже приведена последовательность применения таких правил. Для приведения любого выражения к нормальной форме следует выполнить следующие операции.
Страницы: 1, 2, 3, 4
