1.4. Конъюнкции

1.4. Конъюнкции

Предположим, что мы хотим получать ответы на вопросы о более сложных отношениях, таких как: «Нравятся ли Джон и Мэри друг другу?». Один из способов сделать это – узнать сначала, нравится ли Джону Мэри, и если Пролог ответит да, то спросить, нравится ли Мэри Джон. Таким образом, эта задача состоит из двух «целевых утверждений» (или целей), которые Пролог должен согласовать. Ввиду того что подобная комбинация часто используется при программировании на Прологе, для нее имеется специальное обозначение. Предположим, мы имеем следующую базу данных:

нравится(мэри,пища).

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

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

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

Мы хотим узнать, нравятся ли Джон и Мэри друг другу. Для этого мы спрашиваем: «Нравится ли Джон Мэри и нравится ли Мэри Джон?». Связка и выражает тот факт, что нас интересует конъюнкция двух указанных целей – мы хотим последовательно согласовать с базой данных обе цели. Мы выражаем это в вопросе, записывая обе цели через запятую:

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

Запятая читается как «и» и используется для разделения произвольного числа различных целей, которые должны быть согласованы с базой данных для того, чтобы ответить положительно на вопрос. Если задана последовательность целей (разделенных запятыми), то Пролог пытается согласовать каждую цель по очереди, просматривая базу данных в поисках сопоставимых фактов. Чтобы согласовать с базой данных последовательность целей, необходимо согласовать все отдельные цели. Что должен напечатать Пролог в ответ на приведенный выше вопрос? Ответ будет нет. Действительно, так как имеет место факт, что Джону нравится Мэри, то первая цель согласуется с базой данных. Однако вторая цель не согласуется с базой данных, так как в ней отсутствует факт нравится(мэри,джон). Учитывая, что мы хотели знать, нравятся ли они оба друг другу, окончательным ответом на вопрос является нет.

Сочетая возможности конъюнкции и использования переменных, можно строить достаточно содержательные вопросы. Теперь, когда мы знаем, что нельзя выяснить, нравятся ли Джон и Мэри друг другу, мы спрашиваем: «Существует ли что-нибудь такое, что нравится обоим - Джону и Мэри?». Этот вопрос также содержит две цели:

• Существует ли такой объект X, который нравится Мэри.

• Нравится ли Джону найденное значение X.

В Прологе два указанных целевых утверждения следует объединить, используя конъюнкцию, как показано ниже:

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

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

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

1. База данных просматривается в попытке согласовать первую цель. Так как второй аргумент (X) неконкретизирован, то ему может соответствовать все что угодно. Первый факт, сопоставимый с целью, в приведенной выше базе данных есть нравится(мэри, пища). С этого момента каждому появлению переменной X в вопросе соответствует значение пища. Пролог отмечает в базе данных то место, где был обнаружен соответствующий факт, так что при необходимости найти другой способ согласования цели с фактами он может вернуться в эту точку и продолжить поиск. Более того, следует помнить, что переменная X была конкретизирована в этой точке и Пролог может «забыть» найденное для X значение в случае необходимости найти новое соответствие в фактах для рассматриваемой цели.

2. Теперь в базе данных ищется факт нравится(джон,пища), так как следующая цель – это нравится (джон,X), а переменная X теперь имеет значение пища. Как можно видеть, база данных такого факта не содержит, так что эта цель с базой данных не согласуется. В этой ситуации мы должны попытаться найти новое соответствие в фактах для предыдущей цели. Поэтому Пролог предпринимает попытку найти новое соответствие для нравится(мэри,X), при этом поиск в базе данных начинается с отмеченного маркером места. Но сначала необходимо «расконкретизировать» переменную X так, чтобы X опять могла быть сопоставлена с любым объектом.

3. Отмеченным маркером местом является факт нравится(мэри, пища). Поэтому Пролог начинает поиск со следующего непосредственно за ним факта. Так как мы еще не достигли конца базы данных, то мы не исчерпали всех объектов, которые нравятся Мэри. Следующим сопоставимым фактом является нравится(мэри, вино). Теперь переменная X принимает значение вино, и Пролог отмечает это место на случай, если потребуется найти новое соответствие для того, что нравится Мэри.

4. Как и ранее, Пролог пытается теперь согласовать с фактами вторую цель в вопросе, осуществляя поиск в базе данных факта нравится(джон,вино). Пролог не пытается при этом использовать механизм поиска нового соответствия для этой цели. Это новая цель, которую он выбирает, продвигаясь, как и раньше, слева направо по списку целей в исходном вопросе, поэтому он должен начать поиск с начала базы данных. Когда после недолгого поиска будет найден сопоставимый факт, Пролог выдает надлежащее сообщение. Как только вторая цель согласована, Пролог отмечает соответствующий ей факт в базе данных на случай, если вдруг потребуется найти для нее новое соответствие. Для каждой цели, которую Пролог пытается согласовать, в базе данных имеется свой маркер, указывающий факт, поставленный в соответствие этой цели.

5. Теперь обе цели согласованы. Переменная X обозначает имя вино. Маркер первого целевого утверждения отмечает в базе данных факт нравится(мэри,вино), а маркер второго целевого утверждения отмечает факт нравится(джон,вино).

Как и в случае других запросов, как только Пролог находит ответ, он прекращает поиск и ожидает дальнейших указаний.

Если ввести ;