Семинар Доом. Применение графов к решению логических задач.

Версия 18:35, 2 декабря 2007

участник: Болонина Людмила Александровна, 022.

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

Задача 1.

Из трех человек, стоящих рядом, один всегда говорит правду (правдивый), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит правду или ложь («дипломат»). У стоящего слева спросили: «Кто стоит рядом с тобой?» Он ответил: «Правдолюб». Стоящему в центре, задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он ответил: «Лжец». Кто где стоял?

Решение:

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

Файл:Risyn1.bmp

Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.

Задача 2.

В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д-третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.

Решение:

Составим граф:

Файл:Risyn2.bmp

 Ответ: №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А

Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.

Задача 3.

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

Решение:

Файл:Risyn3.bmp

Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. Суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа. Следовательно, в данной задаче предприниматели выписывают шесть наименований газет. Всего предпринимателей: 6*(6-1)/2=15 чел. Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов.

Задача 4.

Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?

Решение:

Логический квадрат для этого случая имеет вид:

Аня Валя Катя Красное 0 1 0 Белое 0 0 1 Синее 1 0 0

Графы для этой задачи имеют вид.

Файл:Risyn4.bmp

И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем. Ребята оценивают достоинства и недостатки каждого из этих способов.