Семинар Доом. Применение графов к решению логических задач.
Основой применения графов для решения логических задач служит выявление и последовательное исключение логических возможностей, задаваемых условиями задач. Это выявление и исключение логических возможностей часто может быть истолковано с помощью построения и рассмотрения соответствующих графов.
Задача 1.
Из трех человек, стоящих рядом, один всегда говорит правду (правдивый), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит правду или ложь («дипломат»). У стоящего слева спросили: «Кто стоит рядом с тобой?» Он ответил: «Правдолюб». Стоящему в центре, задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он ответил: «Лжец». Кто где стоял?
Решение:
Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.
Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.
Задача 2.
В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта - в корзинах А. Б, Г; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д-третьего. Пронумеруйте каждую корзину так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно); в корзине № 2-второго и т.д.
Решение:
Составим граф:
Ответ: №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А
Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.
Задача 3.
В обеденный перерыв предприниматели разговорились, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читают пять человек, и любая комбинация читается одним человеком. Сколько названий газет выписывают предприниматели? Сколько всего было человек?
Решение:
Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику. Суть метода решения этой и подобных ей задач состоит в установлении связей между множеством вершин и множеством ребер графа. Следовательно, в данной задаче предприниматели выписывают шесть наименований газет. Всего предпринимателей: 6*(6-1)/2=15 чел. Полезно решать логические задачи разными методами. Например, следующую задачу можно решить способом логических квадратов и с помощью графов.
Задача 3.
Три ученицы - Аня, Валя. Катя - участвовали в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?
Решение:
Логический квадрат для этого случая имеет вид:
Аня Валя Катя Красное 0 1 0 Белое 0 0 1 Синее 1 0 0
Графы для этой задачи имеют вид.
И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем. Ребята оценивают достоинства и недостатки каждого из этих способов.
