8.9. Решение логических задач на prolog

8.9.1. Понятие о методе резолюций

Мы познакомились с правилами логического вывода при работе PROLOG. Попробуем разобраться, какая именно логическая формализация используется при этом PROLOG-системой. Решая предложенные нами задачи, мы убедились, что однозначный ответ PROLOG дает лишь в одном случае – вывод неверен, ответ – "ложь". Если же результат – "истина", то выполняется дальнейший поиск альтернативных решений. Таким образом, процесс решения использует известный закон логики "modus ponens".

Примеры

8.21. Если верно А и верно не А

Резольвента: «ложь».

8.22. Верно А и В, верно А и В -> С, верно не С

Резольвента: не (А и В) = (не А) или (не В).

8.23. Задача о ханойской башне.

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

Введем предикат "переместить" с аргументами:

1. сколько дисков надо переместить;

2. с какого стержня;

3. на какой стержень;

4. какой стержень будет запасным.

Например, переместить(К,В,А,С) означает, что надо переместить К дисков со стержня В на стержень А, используя стержень С.

Строим граничное условие: на левом стержне дисков нет, то есть переместить(0,-,-,-) if!

Построим рекурсивное правило:

переместить(N,A,B,C) if M=N-1, переместить(М,А,С,В), сообщить(А,В), переместить(М,С,В,А).

сообщить(X,Y) if write ([переместили, диск, с, X, на, Y]),nl.

Декларативный смысл правила: переместить N дисков с А на В, используя С – это переместить N-1 диск с А на С, используя В, нижний диск с А переместить на В и переместить N-1 диск с С на В, используя А.

8.24. Решение задач на соответствие.

Беседуют трое друзей: Белов, Рыжов, Чернов. Брюнет сказал Белову: "Посмотри, один из нас блондин, другой – рыжий, третий – брюнет, но ни у кого цвет волос не соответствует фамилии". Какой цвет волос у каждого собеседника?

Фамилия("Белов").

Фамилия("Чернов").

Фамилия("Рыжов").

Цвет("светлый").

Цвет("рыжий").

Цвет("четный").

Соответствие(X,Y) if фамилия(X), цвет(Y), X= "Белов", not (Y= "черный"), not(Y= "светлый").

/*если Х – это Белов, а У – цвет его волос, то У – не черный и не светлый*/

Соответствие(X,Y) if фамилия(X), цвет(Y), X= "Чернов", not (Y= "черный"), not(соответствие("Белов",У)).

/*если Х – это Чернов, то он не черный и не такой как Белов*/

Соответствие(X,Y) if фамилия(X), цвет(Y), X= "Рыжов", not (соответствие("Белов",У)), not(соответствие("Чернов",У)).

/*если Х – это Рыжов, то он не такой, как Белов, и не такой, как Чернов*/

Заметим, что в приведенной задаче устанавливается взаимно-однозначное соответствие между двумя множествами. Если этих ограничений нет, то задача сильно усложняется.

Упражнения

111. На соревнованиях по бегу Джон, Пол и Эндрю заняли три первых места. Какое место занял каждый из них, если Пол занял не 2 и не 3 место, а Эндрю не 3.

112. Антон и Максим носят фамилии Шилов и Гвоздев. Какую фамилию носит каждый из них, если Максим с Шиловым живут в разных домах.

113. Три подружки вышли в белом, зеленом и синем платьях. Только у Ани цвета платья и туфель совпадают, ни туфли, ни платье Вали не были белыми. Наташа была в зеленых туфлях. Определить цвета платьев и туфель каждой из подруг.

114. На заводе работают 3 друга: слесарь, токарь и сварщик. Их фамилии Борисов, Иванов и Семенов. У слесаря нет ни братьев, ни сестер. Он – младший из друзей. Семенов, женат на сестре Борисова, старше токаря. Назвать фамилии слесаря, токаря и сварщика.

115. В бутылке, стакане, кувшине и банке находится молоко, квас, лимонад и вода. Известно, что молоко и вода – не в бутылке, сосуд с лимонадом находится между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан находится около банки и сосуда с молоком. Как распределены жидкости по сосудам?

116. У Ивана машина красная, у Петра – не черная, не синяя, не голубая, у Максима – черная и синяя, у Александра есть машины любого цвета (из перечисленных), у Бориса машины белого и синего цветов. У кого какого цвета машины, если все водители ехали на машинах разных цветов.

117. Три друга разной национальности на соревнованиях заняли 1, 2, 3 места. Зовут друзей по-разному и занимаются они разными видами спорта. Майкл предпочитает баскетбол и играет лучше американца. Англичанин Саймон играет лучше теннисиста. Игрок в крикет занял 1-ое место. Кто является австралийцем? Какое место занял Сигурд?

118. В гостинице за круглым обеденным столом встретились 5 гостей родом из Москвы, Петербурга, Новгорода, Перми и Томска. Их фамилии Юрин, Томин, Алешин, Николаев и Викторов. Москвич сидел между томичем и Викторовым, петербуржец – между Юриным и Томиным, а напротив него сидел пермяк и Алешин. Николаев никогда не был в Петербурге, Юрин бывал в Москве и Томске, а томич с Томиным регулярно переписываются. Определите, в каком городе живет каждый из постояльцев гостиницы.

119. Воронов, Панков, Левин и Сахаров – 4 талантливых человека, один из них танцор, другой художник, третий певец, четвертый писатель. Известно, что Воронов и Левин сидели в зале консерватории, когда певец давал сольный концерт; Панков и писатель вместе позировали художнику; писатель написал повесть о Сахарове и собирается писать о Воронове; Воронов никогда не слышал о Левине. Кто чем занимается?

120. Три рыцаря со своими оруженосцами, спасаясь от врагов, должны переправиться через реку в маленькой двухместной лодке. Но ни один оруженосец не соглашается остаться на вражеском берегу без своего хозяина. Каким образом всем шестерым удалось все же переправиться на другой берег?

121. Четыре друга A, B, C, D играют каждый на одном из инструментов: флейте, рояле, гитаре и скрипке. Каждый из друзей владеет одним из иностранных языков: английским, французским, немецким и испанским. Известно, что

1. юноша, играющий на гитаре, говорит по-испански;

2. B не играет ни на скрипке, ни на флейте, ни на рояле:

3. A не играет ни на скрипке, ни на флейте и не знает английского;

4. D говорит по-французски, но не играет на скрипке.

Кто на каком инструменте играет и на каком языке говорит?

111. По древнему поверью, у каждого месяца есть свой камень-талисман. Так, июню, июлю и сентябрю соответствуют камни рубин, сапфир и жемчуг. Эти камни означают мудрость, здоровье и благополучие. У какого месяца какой камень-талисман и что он означает, если известно, что:

1. жемчуг и рубин не соответствую сентябрю;

2. в июне и июле мудрости не наблюдается;

3. здоровье не соответствует рубину;

4. благополучие не относится к июню.