systemII2003 (Лабораторные работы по Прологу (задания уточнять у преподавателя))

41

ЧАСТЬ I. ВВЕДЕНИЕ В ЛОГИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

ЛАБОРАТОРНАЯ РАБОТА №1

1. МЕТОД РЕЗОЛЮЦИИ

Целью лабораторной работы является изучение метода резолюций для логики предикатов первого порядка. Понимание метода важно для дальнейшего изучения принципов программирования в языке ПРОЛОГ, которому посвящены все последующие лабораторные работы настоящего методического пособия.

Теоретическое введение

Логическое программирование и, в частности, язык Пролог основан методе резолюции.

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

Формула В является логическим следствием А1,А2,...Аn тогда и только тогда, когда формула А1А2...АnВ противоречива.

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

Применение метода резолюций для логики высказываний достаточно просто. Если в любых двух дизъюнктах С₁ и С₂ имеется контрарная пара литер (L и L), то вычеркивая ее, мы формируем новый дизъюнкт из оставшихся частей дизъюнктов. Этот вновь сформированный дизъюнкт будем называть резольвентой дизъюнктов С₁ и С₂.

Пример. Пусть

С₁: PQR,

С₂: QP.

Тогда резольвента С: PR.

Обоснованность получения таким образом резольвенты вытекает из теоремы:

Резольвента С, полученная из двух дизъюнктов С₁ и С₂, является логическим следствием этих дизъюнктов.

Если в процессе вывода новых дизъюнктов мы получим два однолитерных дизъюнкта, образующих контрарную пару, то резольвентой этих двух дизъюнктов будет пустой дизъюнкт .

Таким образом, выводом пустого дизъюнкта  из множества дизъюнктов S называется конечная последовательность дизъюнктов С₁,С₂,...,С_k такая, что любой С_i является дизъюнктом S или резольвентой, полученной принципом резолюций и С_k=.

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

С₁: P(x) R,(x)

С₂: P(g(x))  Q(y),

то резольвента может быть получена только после применения к С₁ подстановки g(x) вместо х. Имеем

С₁: P(g(x)) R,(g(x))

С₂: P(g(x))  Q(y),

C: R,(g(x))  Q(y).

Однако для случая

С₁: P(f(x)) R,(x)

С₂: P(g(x))  Q(y),

никакая подстановка неприменима и никакая резольвента не образуется. Отсюда следует определение, что является подстановкой.

Подстановкой называется конечное множество типа {t₁/x₁,t₂/x₂,...,t_n/x_n}, где t_i– терм, а x_i– переменная, не входящая в t_i.

Подстановку  будем называть унификатором для множества выражений {W₁,W₂,...,W_k}, если W₁=W₁=...=W_k. Унификатор  для множества выражений {W₁,W₂,...,W_k} называется наиболее общим унификатором (НОУ) тогда и только тогда, когда для каждого унификатора  для этого множества найдется подстановка  такая, что =_, где _ есть композиция двух подстановок  и .

Пример. W={P(x,a,f(g(a))),P(z,y,f(u))}. Тогда ={z/x, a/y, g(a)/u} есть НОУ, а ={b/x, a/y, g(a)/u} есть унификатор. Подробно о подстановках и алгоритме унификации см. [1], стр 61, §2.6.

Задание 1. Запустить программу 2.exe из каталога RESOL. Внимательно прочитайте объяснения. Все неясные вопросы можно выяснить в разделе ПОМОЩЬ. Выполнит три задачи в интерактивном режиме по указанию преподавателя.

2. ИНТЕРПРЕТАТОР ARITY/PROLOG И ЗАПУСК ПРОСТОЙ ПРОГРАММЫ

ЦЕЛЬ. Знакомство с интерпретатором ARITY/PROLOG, включая использование меню, создание программных файлов, запуск и трассировку программ на ARITY/PROLOG.

Главное меню

Войдите в директорию, содержащую файл api.exe, и запустите его. На экране появится главное меню и главное (диалоговое) окно с приглашением ARITY/PROLOG. Главное меню можно сделать активным, нажав F10. Когда главное меню активно, его элементы можно выбрать с помощью клавиш управления курсором (,) и последующим нажатием клавиши Enter. Другой способ выбора элементов главного меню -нажать комбинацию клавиш Alt+начальная буква имени элемента (например, Alt+F - выбор элемента меню File).

1. Первая программа

Программа на Прологе состоит из фактов и правил, которые образуют базу Пролог-программы, и запроса к этой базе, который задает цель поиска решений. Факты описывают отношение между объектами. Например, "Эллен любит теннис." в синтаксисе Пролога имеем

Имя предиката (функтора) и объекта должно начинаться с маленькой буквы и может содержать только латинские буквы, цифры и символ подчеркивания (_). Обычно предикатам дают такие имена, чтобы они отражали смысл отношения. Например: main, add_file_name. Два предиката могут иметь одинаковые имена, тогда система распознает их как разные предикаты, если они имеют различное число аргументов (арность). Например, likes/2, likes/3.

 Имя предиката может совпадать с именем какого-либо встроенного предиката Arity. Однако когда Вы определяете предикат таким образом, а потом обращаетесь к нему (либо из интерпретатора, либо из программы), Ваше определение предиката отменяет встроенное определение предиката.

Правила описывают связи между фактами. Например,

Билл любит все, что любит Том.

В синтаксисе Пролога:

'любит'('Билл',Нечто):- 'любит'('Том',Нечто).

Символ :- соответствует союзу если... , то. В общем виде правило - это конструкция вида:

P0:- P1,P2,...,Pn,

которая читается так: "P0 истинно, если P1 и P2 и ... Pn истинны". Предикат P0 называется заголовком правила, выражение P1,...,Pn- телом правила, а предикаты Pi -подцелями правила. Запятая означает логическое "И".

Факты и правила называются утверждениями. Факт можно рассматривать как утверждение, имеющее заголовок и пустое тело.

Процедура - это совокупность утверждений, заголовки которых имеют одинаковый функтор и одну и ту же арность. Процедура задает определение предиката.

Отметим, что

 переменная в Прологе обозначается как последовательность латинских букв, начинающаяся с заглавной буквы или символа подчеркивания ( _ );

 если значением аргумента предиката или его именем является слово, содержащее русские буквы или начинающееся с заглавной латинской, то оно пишется в апострофах (см. прилож. 2);

 в Прологе различаются строчные и заглавные буквы; конец предложения отмечается точкой, поэтому все факты, правила и запросы должны заканчиваться точкой;

 между именем предиката и скобкой не должно быть пробелов

Рассмотрим следующую программу на Прологе, которую будем использовать для иллюстрации процессов создания, выполнения и редактирования Пролог-программ.

Программа 1./* кто что любит */

likes('Ellen',tennis). %Эллен любит теннис

ikes('John',football). %Джон любит футбол

likes('Tom',baseball). %Том любит бейсбол

likes('Eric',swimming). %Эрик любит плавание

likes('Mark',tennis). %Марк любит теннис

likes('Bill',X):-

likes('Tom',X). %Билл любит то, что любит Том

*Коммментарий в строке программы начинается с символа % и заканчивается концом строки. Блок комментариев выделяется специальными скобками: /* и */.

Задание 2. Войдите в редактор (в 1-ый буфер) из главного окна нажатием клавиши F8. На экране появится окно 1-ого буфера (по умолчанию имя файла – APIBUF1.ARI).

Прочитайте приложение 1 (команды редактора и работа с буфером). Введите программу 1 и запишите в файл, используя подменю File.(Для этого используйте опции Save File или Save File As)

Чтобы запустить программу, необходимо ее загрузить для выполнения. Это делается выбором опции Consult в подменю File. На экране появится диалоговое окно. Укажите имя файла, который Вы хотите загрузить, и выберите Reconsult. Если Вы попытаетесь загрузить для выполнения файл, в котором есть синтаксические ошибки, то он не загрузится, а Вы получите сообщение об ошибке в главном окне. Угловые скобки << >> будут выделять место, где встретилась ошибка.

Программу можно загрузить на выполнение и по-другому: с помощью подменю Buffers, используя опции Save on Exit и Reconsult on

Exit, которые сохраняют и загружают содержимое текущего окна при выходе из редактора.

После того, как Вы запомнили и загрузили программу, войдите в интерпретатор Arity/Prolog. Для этого нажмите клавишу F8. Когда Вы переключитесь в главное окно, Вы увидите приглашение интерпретатора (?-), которое означает, что интерпретатор ждет запрос.

Запрос - это конструкция вида:

?- P1,P2,...,Pn,

которая читается "Верно ли P1 и P2...и Pn ?". Предикаты Pi называются подцелями запроса

Просмотрите Вашу базу с помощью встроенного предиката listing, задав запрос: "?-listing.".

Введите запрос:

?-likes('Bill',baseball). % Любит ли Билл бейсбол?

Получите ответ yes (да) и новое приглашение к запросу.

Введите следующие запросы и посмотрите на результаты.

likes('Bill', tennis). %Любит ли Билл теннис?

likes(Who, tennis). %Кто любит теннис?

likes('Mark',Wt),likes('Ellen',Wt). %Что любят Марк и Эллен?

likes(Who, What). %Кто что любит?

likes(Who, _). %Кто любит?

При поиске решений по базе Вы получите первое решение. Например,

?-likes(Who,tennis). Who = 'Ellen' ->

 Если Вы хотите продолжить поиск в базе по этому запросу, то введите точку с запятой (;). Если Вы не хотите, чтобы набранный Вами запрос выполнялся (например, Вам нужно набрать другой запрос), используйте комбинацию Ctrl + Break. Если Вы хотите повторить один из предыдущих запросов, воспользуйтесь клавишами "стрелка вверх" или "стрелка вниз".

3. Слияние файлов