Назад | Содержание| Вперёд 2. 3. Декларативный смыслпролог-программ ...

Назад | Содержание| Вперёд

2. 3. Декларативный смыслпролог-программ

В главе 1 мы уже видели, что пролог-программуможно понимать по-разному: с декларативной ипроцедурной точек зрения. В этом и следующемразделах мы рассмотрим более формальноеопределение декларативного и процедурногосмыслов программ базисного Пролога. Но сначаладавайте еще раз взглянем на различия между этимидвумя семантиками.

Рассмотрим предложение

Р :- Q, R.

где Р, Q и R имеют синтаксис термов. Приведемнекоторые способы декларативной интерпретацииэтого предложения:

Р - истинно,если Q и R истинны.

Из Q и R следует Р.

А вот два варианта его "процедурного"прочтения:

Чтобы решить задачу Р, сначала реши подзадачу

Q, а затем -подзадачу R.

Чтобы достичь Р, сначаладостигни Q, а затем R.

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

Формализуем теперь декларативный смысл.

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

имеетребенка( X) :-родитель( X, Y).

Приведем два варианта этого предложения:

имеетребенка( А) :-родитель( А, В).

имеетребенка( X1) :-родитель( X1, Х2).

Примеры конкретизаций этого же предложения:

имеетребенка(питер) :- родитель( питер, Z).

имеетребенка( барри) :-родитель( барри,

маленькая( каролина) ).

Пусть дана некоторая программа и цель G, тогда, всоответствии с декларативной семантикой, можноутверждать, что

Цель G истинна (т.е. достижима илилогически следует из программы) тогда и толькотогда, когда

(1) в программе существуетпредложение С, такое, что

(2) существует такая его (С) конкретизация I, что

(a) голова I совпадает с G и

(б) все цели втеле I истинны.

Это определение можно распространить навопросы следующим образом. В общем случае вопроск пролог-системе представляет собой списокцелей, разделенных запятыми. Список целейназывается истинным (достижимым), если всецели в этом списке истинны (достижимы) при одинаковыхконкретизациях переменных. Значения переменныхполучаются из наиболее общей конкретизации.

Таким образом, запятая между целями обозначает конъюнкцию целей: они вседолжны быть истинными. Однако в Прологевозможна и дизъюнкция целей:должна быть истинной, по крайней мере однаиз целей. Дизъюнкция обозначается точкой сзапятой. Например:

Р :- Q; R.

читается так: Р - истинно, если истинно Q или истинно R. То есть смыслтакого предложения тот же, что и смысл следующейпары предложений:

Р :- Q.

Р :- R.

Запятая связывает (цели) сильнее, чем точка сзапятой. Таким образом, предложение

Р :- Q, R; S, Т, U.

понимается как:

Р :- (Q, R); (S, Т, U).

и имеет тот же смысл, что и два предложения

Р :- Q, R.

Р :- S, T, U.

Упражнения

2. 6. Рассмотрим следующуюпрограмму:

f( 1, один).

f( s(1), два).

f( s(s(1)), три).

f( s(s(s(X))), N) :-

f(X, N).

Как пролог-система ответит на следующиевопросы? Там, где возможны несколько ответов,приведите по крайней мере два.

(a) ?- f( s( 1),A).

(b) ?- f( s(s(1)),два).

(d) ?- f( D, три).

Посмотреть ответ

2. 7. В следующей программеговорится, что два человека являютсяродственниками, если

(a) одинявляется предком другого, или

(b) у них естьобщий предок, или

родственники( X, Y) :-

предок( X, Y).

родственники( X, Y) :-

предок( Y, X).

родственники( X, Y) :-

% X и Y имеют общего предка

предок( Z, X),

предок( Z, Y).

родственники( X, Y) :-

% X и Y имеют общего потомка

предок( X, Z),

предок( Y, Z).

Сможете ли вы сократить эту программу,используя запись с точками с запятой?

Посмотреть ответ

2. 8. Перепишите следующуюпрограмму, не пользуясь точками с запятой.

преобразовать( Число, Слово) :-

Число = 1, Слово =один;

Число = 2, Слово =два;

Число = 3, Слово =три.

Посмотреть ответ

Назад | Содержание| Вперёд

Оглавление