Подразделы

Другие разделы

Дата и время

19/04/2024 03:55:04

Авторизация

Логическое программирование

Логическое программирование и язык Пролог Синтаксис. Операторы. Списки Сопоставление Арифметические и логические выражения Семантика программы на языке Пролог Списки. Обработка списков Предикаты для классификации и обработки термов Предикаты для управления процессом доказательства Предикаты для ввода и вывода данных Предикаты для работы с утверждениями Предикаты порождения Отладка программ на языке Пролог Примеры программ на языке Пролог Логика предикатов. Метод резолюции Верификация программ: основные обозначения и термины Правильность алгоритмов и способ верификации программ Синтез программ

Логическое программирование и язык Пролог

Язык Пролог основывается на языке исчисления предикатов первого порядка и методике автоматического доказательства теорем (метод резолюции с ограничениями для уменьшения пространства поиска). Пролог был разработан в 1972 г. А. Кольмероэ из Марсельского университета. В течение следующего десятилетия язык получил дальнейшее развитие благодаря работам Р. Ковальского и других исследователей. Теперь Пролог применяется в следующих областях:

– общение с ЭВМ на естественном языке;
– интерфейсы реляционных баз данных;
– создание систем автоматического программирования;
– представление и обработка знаний в задачах искусственного интеллекта;
– экспертные системы;
– символические вычисления;
– решение задач в области математической логики;
– написание компиляторов.

К достоинствам языка Пролог относятся:

– сочетание декларативного и процедурного подхода;
– простые и легко понимаемые тексты программ;
– высокая степень модульности, облегчающая модификацию и отладку программ;
– эффективность реализации и доступность транслятора на всех типах ЭВМ.

Программа на языке Пролог описывает знания о некоторой предметной области. Эти знания включают в себя факты, описывающие свойства объектов и отношения между ними, и правила, на основании которых могут быть получены новые знания о свойствах объектов и отношениях между ними. Факт состоит из имени отношения и списка объектов, между которыми это отношение существует. Каждый факт должен заканчиваться точкой. Имена всех объектов и отношений должны начинаться со строчной буквы. Например, факт "Джону нравится Мэри" записывается так:

нравится(джон,мэри).

Выполнение программы инициализируется запросом. Интерпретатор пытается логически вывести запрос, используя знания о предметной области, содержащиеся в программе, которая является своего рода базой данных (БД) об объектах в задаче. Если существует факт, сопоставимый с целью, указанной в запросе, то интерпретатор отвечает утвердительно. В противном случае будет получен отрицательный ответ. Например, пусть БД содержит следующие факты:

нравится(джон,мэри).
нравится(джон,пиво).
нравится(мэри,кино).
нравится(джон,кино).

Запрос обычно вводится в диалоговом режиме после подсказки "?–" и должен заканчиваться точкой. Например, на эти запросы будут получены следующие ответы:

?-нравится(джон,деньги).
no
?-нравится(мэри,джон).
no
?-нравится(мэри,кино).
yes
?-президент(буш,сша).
no

На второй запрос был получен отрицательный ответ, так как из того, что Джону нравится Мэри, не следует, что Мэри нравится Джон. Остальные отрицательные ответы связаны с ограниченностью БД, в которой не отражаются связи, возможно существующие в действительности. Чтобы узнать все объекты, которые нравятся Джону, нужно указать в запросе вместо имени конкретного объекта переменную. Имя переменной должно начинаться с прописной буквы или символа подчеркивания.

?-нравится(джон,X).
X=мэри;
X=пиво;
X=кино;
no

Интерпретатор сопоставляет цель в запросе с фактами в БД, при этом переменная получает значение аргумента отношения, стоящего в соответствующей позиции. Если согласование цели с БД возможно, то значение переменной выводится на экран, и можно ввести символ ";", чтобы получить другой вариант решения. Если вариантов больше нет, то выводится отрицательный ответ. Если альтернативные решения не нужны, то вместо ";" нужно нажать клавишу Enter.

Используя конъюнкцию целей, можно строить более сложные запросы. При этом цели в запросе перечисляются через запятую, а для получения утвердительного ответа необходимо согласование всех целей в запросе. Например, запрос "Существует ли что-либо, что нравится и Джону, и Мэри?" выглядит так:

?-нравится(джон,X),нравится(мери,X).

Если факт – это отношение, которое безусловно истинно, то правило – это отношение, которое является истинным, только если выполняется некоторое условие. Правило состоит из головы, которая определяет новое свойство или отношение объектов, и тела, которое содержит условие. При попытке сопоставления цели в запросе и головы правила выполняется согласование целей в теле правила. Если это согласование успешно, то отношение, задаваемое головой правила, истинно.

Правило должно заканчиваться точкой, а голова от тела правила отделяется обозначением ":–", которое читается как "если". Например, правило "Мэри нравится любой, кому нравится кино" записывается как:

нравится(мэри,X):-нравится(X,кино).

Рассмотрим теперь задачу о родственных связях. Пусть БД содержит факты:

мужчина(адам).
мужчина(каин).
мужчина(авель).
женщина(ева).
родитель(адам,каин).
родитель(адам,авель).
родитель(ева,каин).
родитель(ева,авель).

Правило "X приходится сестрой Y, если X является женщиной, и X и Y имеют общих родителей" на языке Пролог выглядит следующим образом:

сестра(X,Y):-женщина(X),родитель(Z,X),родитель(Z,Y).

Данное определение может привести к ошибке, так как Пролог не требует различия объектов, обозначаемых разными именами, которое неявно подразумевается в определении на естественном языке. Поэтому эта проверка должна быть сделана явно:

сестра(X,Y):-женщина(X),родитель(Z,X),родитель(Z,Y),X\=Y.

Упражнения

1. Используя БД о родственных связях определите отношения: дедушка, дядя, кузен, племянник, отец, тетя, кузина, племянница, внучатый племянник, предок, ближайший общий предок.

2. Предполагая, что если X и Y имеют общих детей, то они женаты, определите отношения: зять, тесть, свекровь, шурин, невестка.