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

Васильева Александра в 11:11, 10 января 2008

2008-01-10T11:11:30Z

Егорчева Светлана Валентиновна в 14:35, 2 декабря 2007

2007-12-02T14:35:32Z

Егорчева Светлана Валентиновна в 14:19, 2 декабря 2007

2007-12-02T14:19:40Z

Егорчева Светлана Валентиновна: Новая: Основой применения графов для решения логических задач служит выявление и последовательное исклю...

2007-12-02T14:17:18Z

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

Новая страница

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

'''Задача 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

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

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

← Предыдущая		Версия 11:11, 10 января 2008
Строка 61:		Строка 61:
	Ребята оценивают достоинства и недостатки каждого из этих способов.		Ребята оценивают достоинства и недостатки каждого из этих способов.

−	[[Категория:Проект ДООМ]]	+	[[Категория:Проект ДООМ 2007-2008 (1 цикл)]]

@@ Строка 1: / Строка 1: @@
 [[участник: Болонина Людмила Александровна, 022.]]
@@ Строка 11: / Строка 10: @@
 Если в данной задаче ребро графа будет соответствовать месту, занимаемому тем или иным человеком, то нам могут представиться следующие возможности.
+  [[Изображение:risyn1.bmp]]<br><br>
 Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, находится «правдолюб». У нас же стоит лжец. Рассмотрев таким образом все остальные возможности,  мы придем к выводу, что расстановка «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и следовательно, лжет, а стоящий справа также лжет. Таким образом все условия задачи выполнены. В качестве задачи второго типа можно предложить следующую.
@@ Строка 21: / Строка 20: @@
   Составим граф:
-−
- '''Ответ:''' №1-Г; №2-А или №2-Б; №3-Д; №4-В; №5-Б или №5-А
+[[Изображение:risyn2.bmp]]<br><br>
 Возникает вопрос: так ли уж нужны были графы в этой задаче? Разве нельзя прийти к решению логическим путем? Можно, но графы придали условия наглядность, упростили решение.
@@ Строка 30: / Строка 31: @@
 '''Решение:'''
 Решение этой задачи достигается построением следующего графа, где каждая вершина обозначает соответствующую газету и соответственно 5 подписчиков, а каждое ребро будет соответствовать одному подписчику.
@@ Строка 37: / Строка 40: @@
 Полезно решать логические задачи разными методами.  Например, следующую задачу можно решить способом логических квадратов и с помощью графов.
-'''Задача 3.'''
+'''Задача 4.'''
 Три ученицы - Аня, Валя. Катя - участвовали  в новогоднем бале - маскараде. Одна из них была в красном костюме, другая - в белом, третья - в синем. Если сказать, что Аня была в красном, Валя – не в красном, и Катя –не в синем, то одно из этих утверждений будет верным, а два других –неверными. В каком костюме была каждая из учениц?
@@ Строка 50: / Строка 53: @@
 Синее	1	0	0
 Графы для этой задачи имеют вид.
 И в том, и в другом случае получаем ответ: Валя была в красном платье, Катя – в белом и Аня - в синем.