Иван Братко - Программирование на языке Пролог для искусственного интеллекта Страница 10

треугольник = треугольник,

точка( 1, 1) = X,

А = точка( 4, Y),

точка( 2, 3) = точка( 2, Z).

Весь процесс сопоставления успешен, поскольку все сопоставления в этой последовательности успешны. Результирующая конкретизация такова:

X = точка( 1, 1)

A = точка( 4, Y)

Z = 3

В приведенном ниже примере показано, как сопоставление само по себе можно использовать для содержательных вычислений. Давайте вернемся к простым геометрическим объектам с рис. 2.4 и напишем фрагмент программы для распознавания горизонтальных и вертикальных отрезков. "Вертикальность" — это свойство отрезка, поэтому его можно формализовать в Прологе в виде унарного отношения. Рис. 2.8 помогает сформулировать это отношение. Отрезок является вертикальным, если x-координаты его точек-концов совпадают; никаких других ограничений на отрезок не накладывается. Свойство "горизонтальности" формулируется аналогично, нужно только в этой формулировке x и y поменять местами. Следующая программа, содержащая два факта, реализует эти формулировки:

верт( отр( точка( X, Y), точка( X, Y1) ) ).

гор( отр( точка( X, Y), точка( X1, Y) ) ).

Рис. 2.7. Сопоставление треугольник(( точка( 1, 1), А, точка( 2, 3)) = треугольник( X, точка( 4, Y), точка( 2, Z))

С этой программой возможен такой диалог:

?- верт( отр( точка( 1, 1), точка( 1, 2) ) ).

да

?- верт( отр( точка( 1, 1), точка( 2, Y) ) ).

нет

?- гор( отр( точка( 1, 1), точка( 2, Y) ) ).

Y = 1

На первый вопрос система ответила "да", потому. что цель, поставленная в вопросе, сопоставима с одним из фактов программы. Для второго вопроса сопоставимых фактов не нашлось. Во время ответа на третий вопрос при сопоставлении с фактом о горизонтальных отрезках Y получил значение 1.

Рис. 2.8. Пример вертикальных и горизонтальных отрезков прямых.

Сформулируем более общий вопрос к программе: "Существуют ли какие-либо вертикальные отрезки, начало которых лежит в точке (2,3)?"

?- верт( отр( точка( 2, 3), P) ).

P = точка( 2, Y)

Такой ответ означает: "Да, это любой отрезок, с концом в точке (2,Y), т.е. в произвольной точке вертикальной прямой x = 2". Следует заметить, что ответ пролог-системы возможно будет выглядеть не так красиво, как только что описано, а (в зависимости от реализации) приблизительно следующим образом:

P = точка( 2, _136)

Впрочем, разница здесь чисто внешняя. В данном случае _136 — это неинициализированная переменная. Имя _136 — законное имя прологовской переменной, которое система построила сама во время вычислений. Ей приходится генерировать новые имена, для того чтобы переименовывать введенные пользователем переменные в программе. Это необходимо по двум причинам: первая — одинаковые имена обозначают в разных предложениях разные переменные; и вторая — при последовательном применении одного и того же предложения используется каждый раз его "копия" с новым набором переменных.

Другим содержательным вопросом к нашей программe является следующий: "Существует ли отрезок, который одновременно и горизонтален в вертикален?"

?- верт( S), гор( S).

S = отр( точка( X, Y), точка( X, Y) )

Такой ответ пролог-системы следует, понимать так: "да, любой отрезок, выродившийся в точку, обладает как свойством вертикальности, так и свойством горизонтальности одновременно". Этот ответ снова получен лишь из сопоставления. Как и раньше, в ответе вместо X и Y могут появиться некоторые имена, сгенерированные системой.

2.3. Будут ли следующие операции сопоставления успешными или неуспешными? Если они будут успешными, то какова будет результирующая конкретизация переменных?

(а) точка( А, В) = точка( 1, 2)

(b) точка( А, В) = точка( X, Y, Z)

(c) плюс( 2, 2) = 4

(d) +( 2, D)= +( E, 2)

(e) треугольник( точка( -1, 0), Р2, Р3) =

     треугольник( P1, точка( 1, 0), точка( 0, Y)

Результирующая конкретизация определяет семейство треугольников. Как бы Вы описали это семейство?

2.4. Используя представление отрезков, применявшееся в данной разделе, напишите терм, соответствующий любому отрезку на вертикальной прямой x = 5.

2.5. Предположим, что прямоугольник представлен термом прямоугольник( P1, P2, P3, Р4), где P — вершины прямоугольника, положительно упорядоченные. Определите отношение

регулярный( R)

которое имеет место, если R — прямоугольник с вертикальными и горизонтальными сторонами.

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

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

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

P :- Q, R.

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

 P — истинно, если Q и R истинны.

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

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

 Чтобы решить задачу P, сначала реши подзадачу Q, а затем — подзадачу R.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

P :- Q; R.

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

P :- Q.

P :- R.

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

P :- Q, R; S, T, U.

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

P :- ( Q, R); (S, T, U).

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

P :- Q, R.

P :- S, T, U.

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

f( 1, один).

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

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

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

 f(X, N).

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