Методы решения логических задач

Методы решения логических задач

Учитель Коптева Л.М.

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

Логические задачи встречаются в текстах олимпиад по математике, а также в КИМах ЕГЭ базового уровня по математике. Как правило, задачу можно решить несколькими способами (методами). Чтобы выбрать наиболее простой и эффективный способ для каждой конкретной задачи, необходимо знать все эти способы.

Прием моделирования на полупрямой

Если в задаче имеется множество объектов и требуется установить взаимоотношение между элементами этого множества, то задачу можно решать на полупрямой.

Задача 1. На вечеринку собрались четверо друзей: Аня, Вика, Миша и Коля. Коля пришел раньше Ани, но не был первым. Определите, в какой последовательности друзья приходили к месту встречи, если Вика пришла последней.

Решение. Построим модель описанной ситуации, считая обычный луч «линией времени». Условимся пришедшего на вечеринку раньше обозначать на полупрямой (первой буквой его имени) правее, пришедшего позже – левее. По порядку каждое условие отметим на полупрямой

а) Коля пришел раньше Ани:

б) Коля не был первым, то есть кто-то из друзей опередил Колю:

в) Вика пришла последней:

г) Значит, Миша пришел раньше всех:

Ответ: Миша, Коля, Аня, Вика.

Задача 2. В очереди в школьный буфет стоят Вика, Соня, Боря, Денис и Алла. Вика стоит впереди Сони, но после Аллы; Боря и Алла не стоят рядом; Денис не находится рядом ни с Аллой, ни с Викой, ни с Борей. В каком порядке стоят ребята? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М.: Айрис-пресс, 2008; задача № 9.11)

Решение.

а) Вика стоит впереди Сони, но после Аллы

б) Денис не находится рядом ни с Аллой, ни с Викой, значит он – крайний слева

в) Боря и Алла не стоят рядом, Борис не находится рядом с Денисом, значит место Бориса – после Вики

Ответ: Алла, Вика, Борис, Соня, Денис.

Задача 3. При взвешивании животных в зоопарке выяснилось, что буйвол тяжелее льва, медведь легче буйвола, а рысь легче льва. Выберите утверждения, которые верны при указанных условиях.

1) Рысь тяжелее буйвола.

2) Буйвол самый тяжелый из всех этих животных.

3) Медведь тяжелее буйвола.

4) Рысь легче буйвола. (ЕГЭ 2016. Математика. Базовый уровень. 30 вариантов типовых тестовых заданий / под ред И.В. Ященко. – М.: Издательство «Экзамен», 2016; вариант 15, задача № 18)

Решение. Отметим данные задачи на полупрямой, причем с одной стороны полупрямой отметим однозначные данные, с другой стороны – неоднозначные.

М

М

М

Ответ: 24.

Прием моделирования с помощью таблицы

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

Задача 4. Перед соревнованиями по плаванию каждого из четырех участников А, Б, В, Г спросили, на какое место он рассчитывает. А сказал: «Я буду первым», Б сказал: «Я не буду последним», В сказал: «Я не буду ни первым, ни последним» и Г сказал: «Я буду последним». После заплыва оказалось, что только один из них ошибочно предсказал результат. Кто из пловцов ошибся? (Задачи повышенной трудности в курсе алгебры 7-9 классов: Кн. для учителя / Н.П. Кострикина. – М.: Просвещение, 1991; задача № 50)

Решение. Составим таблицу, в которой знаком «плюс» укажем предполагаемые результаты.

Пловец	Места
	1	2	3	4
А	+
Б	+	+	+
В		+	+
Г				+

Предположим, что ошибся А, тогда он мог занять 2-е или 3-е место (4-е место занял пловец Г, который, если ошибся А, правильно предсказал свой результат, так как по условию ошибся только один пловец). В этом случае возможны следующие варианты распределения мест:

а) А – 2, Б – 1, В – 3, Г – 4;

б) А – 3, Б – 1, В – 2, Г – 4.

Докажем, что действительно ошибся пловец А. Если бы ошибся Б, т.е. занял 4-е место, то ошибся бы и пловец Г, что противоречит условию задачи. Если бы ошибся В, тогда он должен быть или первым или последним. В таком случае ошибся бы еще один пловец – А или Г. Если бы ошибся Г, то ошибся бы еще один пловец, в противном случае последнее место не занял бы никто. Так как по условию задачи мог ошибиться только один пловец, то Г не ошибся.

Ответ: ошибся пловец А.

Задача 5. В летний лагерь приехали отдыхать три друга: Миша, Володя и Петя. Известно, что каждый из них имеет одну из следующих фамилий: Иванов, Семенов, Герасимов. Миша – не Герасимов. Отец Володи – инженер. Володя учится в 6 классе, Герасимов учится в 5 классе. Отец Иванова – учитель. Какая фамилия у каждого из трех друзей? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М.: Айрис-пресс, 2008; 6 класс, вариант 4, задача № 5)

Решение. Начертим таблицу и заполним последний столбец таблицы, исходя из условий: Миша – не Герасимов, Володя учится в 6 классе, Герасимов – в 5 классе. Значит, Володя – не Герасимов.

Имя	Фамилия
	Иванов	Семенов	Герасимов
Миша			-
Володя			-
Петя

Следовательно, Герасимов – Петя. Поэтому ставим плюс на пересечении строки «Петя» со столбцом «Герасимов» и минусы – в остальных клетках строки «Петя».

Имя	Фамилия
	Иванов	Семенов	Герасимов
Миша			-
Володя			-
Петя	-	-	+

По условию отец Володи – инженер, отец Иванова – учитель. Значит Володя – не Иванов. Поставим минус в соответствующей клетке, увидим, что Володя – Семенов. Тогда Миша – Иванов.

Имя	Фамилия
	Иванов	Семенов	Герасимов
Миша	+	-	-
Володя	-	+	-
Петя	-	-	+

Ответ: Миша – Иванов, Володя – Семенов, Петя – Герасимов.

Задача 6. После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них - математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью:

1) Иван живет не в Минске;

2) Андрей – не в Витебске;

3) житель Минска преподает не математику;

4) Андрей преподает не физику;

5) повезло только жителю Витебска: он преподает любимую им химию.

Можно ли по этим данным определить, кто где живет и что преподает?

Решение. По условиям задачи имеем:

Имя	Город			Дисциплина
	Минск	Витебск	Харьков	Математика	Физика	химия
Иван	–
Андрей		–			–	–
Борис

Значит, Андрей преподает математику. Но математику не может преподавать житель Минска. Таким образом, Андрей – житель Харькова. Но тогда, ни Иван, ни Борис в Харькове не живут.

Отобразим наши рассуждения в таблице:

Имя	Город				Дисциплина
	Минск	Витебск	Харьков	Математика		Физика	химия
Иван	–		–	–
Андрей	–	–	+	+		–	–
Борис			–	–

Из таблицы видно, что Иван не живет ни в Минске, ни в Харькове. Следовательно, Иван – житель Витебска и преподает химию:

Имя	Город				Дисциплина
	Минск	Витебск	Харьков	Математика		Физика	химия
Иван	–	+	–	–		–	+
Андрей	–	–	+	+		–	–
Борис		–	–	–			–

Значит, Борис – житель Минска и преподает физику. Окончательно получим:

Имя	Город				Дисциплина
	Минск	Витебск	Харьков	Математика		Физика	химия
Иван	–	+	–	–		–	+
Андрей	–	–	+	+		–	–
Борис	+	–	–	–		+	–

Ответ: Андрей преподает математику и живет в Харькове, Борис – физику и живет в Минске, Иван – химию и является жителем Витебска.

Прием моделирования с помощью графов

Ситуации, в которых требуется найти соответствие между элементами различных множеств, можно моделировать с помощью графов. В этом случае элементы различных множеств будем обозначать точками (кружочками, прямоугольниками и т. п.), а соответствия между ними – отрезками (дугами).

Задача 7. Три товарища – Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы, Тулы и Новгорода. О них известно следующее:

1. Иван работает не в Москве, а Дмитрий – не в Новгороде;

2. москвич преподает физику;

3. тот, кто работает в Новгороде, преподает химию;

4. Дмитрий и Степан преподают не биологию.

Какой предмет, и в каком городе преподает каждый? (Журнал «Математика в школе», № 3, 2005, стр. 32))

Решение.

В задаче можно выделить три множества: учебных предметов, городов, учителей. Каждое множество содержит по три элемента. Обозначим их точками – вершинами графа.

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

Так, используя условие 1), проведем пунктирную линию, соединяющую объекты Иван и Москва, Дмитрий и Новгород. В соответствии с условием 2) соединим сплошной линией вершины Москва и физика, а условие 3) выразим сплошной линией от точки Новгород до точки химия. По условию 4) Дмитрий и Степан преподают не биологию, соединим соответствующие вершины пунктирными линиями.

Получается, что биологию преподает Иван. Известно, что химик живет в Новгороде, а физик – в Москве, значит, биолог живет в Туле. Проведем соответствующие сплошные линии.

Обратим внимание на треугольник, образованный вершинами Иван, Тула, биология: в нем есть две сплошные стороны, значит, третью сторону (Иван – Тула) также можно выделить сплошной линией. В самом деле, если Иван преподает биологию, а биолог живет в Туле, то Иван живет в Туле.

Что известно про Дмитрия? Дмитрий не живет в Новгороде (по условию) и не живет в Туле (там живет Иван), значит, Дмитрий живет в Москве – проведем соответствующую сплошную линию. Но москвич преподает физику – эта линия тоже сплошная. В треугольнике с вершинами в точках Дмитрий, Москва и физика две стороны сплошные, следовательно, третью сторону тоже можно выделить сплошной линией.

Что же известно про Степана? Степан не живет в Туле (там живет Иван) и не живет в Москве (там живет Дмитрий), следовательно, Степан живет в Новгороде – проведем сплошную линию. Но тот, кто живет в Новгороде, преподает химию – эта линия тоже сплошная. Так появляется третий треугольник из сплошных линий.

Ответ: Иван преподает биологию и живет в Туле, Дмитрий – физику и живет в Москве, Степан – химию и является жителем Новгорода.

Задача 8. Однажды в туристическом лагере оказались вместе пять ребят. Их имена: Леонид, Сергей, Николай, Олег и Петр. Их фамилии: Антонов, Борисов, Васильев, Дроздов и Иванов. Кроме того, известно, что Петр знаком со всеми, кроме одного. Борисов знаком только с двумя. Леонид знает только одного из всех. Дроздов и Сергей не знакомы. Николай и Иванов хорошо знают друг друга. Сергей, Николай и Олег давно знакомы между собой. Антонов знаком только с Петром.

Попробуйте по этим сведениям узнать имена и фамилии всех мальчиков.

Решение. Будем соединять отрезками объекты (ребят), которые знакомы между собой. По условию, что Сергей, Николай и Олег давно знакомы между собой, имеем:

Из условия: Антонов знаком только с Петром делаем вывод, что Леонид – Антонов и соединяем линией Леонида и Петра.

По условию задачи Дроздов и Сергей не знакомы. Следовательно, Петр – Дроздов.

Петр знаком со всеми, кроме одного. Выше сказано, что с Сергеем он не знаком, значит знаком с Леонидом, Николаем и Олегом.

Так как Борисов знаком только с двумя, делаем вывод: Сергей – Борисов. По условию Николай и Иванов хорошо знают друг друга, значит Олег – Иванов, Николай - Васильев.

Борисов

Васильев

Иванов

Ответ: Антонов Леонид, Борисов Сергей, Васильев Николай, Дроздов Петр, Иванов Олег.

Задача 9. 5 школьников приехали из 5 различных городов в Архангельск на областную математическую олимпиаду. «Откуда вы, ребята?» - спросили их хозяева. Вот что ответил каждый из них.

Андреев: «Я приехал из Онеги, а Григорьев живет в Каргополе».

Борисов: «В Каргополе живет Васильев. Я же прибыл из Коряжмы».

Васильев: «Я прибыл из Онеги, а Борисов – из Котласа».

Григорьев: «Я прибыл из Каргополя, а Данилов из Вельска».

Данилов: «Да, я действительно из Вельска, Андреев же живет в Коряжме».

Хозяева очень удивились противоречивости ответов приехавших гостей. Ребята объяснили им, что каждый из них высказал одно утверждение правильное, а другое ложное. Но по их ответам вполне можно установить, кто откуда приехал. Откуда приехал каждый школьник? (Математические олимпиады в школе. 5-11 классы / А.В. Фарков – М. : Айрис-пресс, 2008; 7 класс, вариант 1, задача № 6)

Решение.

Решим задачу, представив ее условие в виде графа.

Вершины графа – фамилии мальчиков и названия городов, откуда они приехали. Ребра графа – высказывания школьников:

мнение Андреева – жирные линии;

мнение Борисова – тонкие линии;

мнение Васильева – жирные пунктирные линии;

мнение Григорьева – тонкие пунктирные линии;

мнение Данилова – штрихпунктирные линии.

Так как каждый из мальчиков сделал только одно правильное заявление, то надо оставить только по одной линии каждого типа. Всего в графе должно остаться 5 линий разных типов.

Предположим, что у Андреева верно первое утверждение, то есть он из Онеги. Тогда надо удалить из графа ребра Григорьев – Каргополь (только одно утверждение Андреева верное), Андреев – Коряжма (он из Онеги), Васильев – Онега (из Онеги – Андреев). Значит, верно первое утверждение Данилова, что он из Вельска и ложно первое утверждение Григорьева, поэтому удаляем из графа ребро Григорьев – Каргополь, а также ребро Борисов – Коряжма (он из Котласа).

Итак, получилось, что Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Данилов из Вельска, значит Григорьев из Коряжмы.

Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение правильное, тогда Григорьев приехал из Каргополя. Значит, Данилов приехал не из Вельска (ложное второе утверждение Григорьева), а Андреев не из Онеги. Тогда у Борисова первое утверждение ложное (в Каргополе живет Григорьев), значит, Борисов прибыл из Коряжмы.

Поэтому Андреев не из Коряжмы (в Коряжме живет Борисов) и получается, что верно первое высказывание Данилова – я из Вельска. Получили противоречие: Данилов из Вельска и не из Вельска. Значит, второй вариант невозможен.

Ответ: Андреев из Онеги, Борисов из Котласа, Васильев из Каргополя, Григорьев из Коряжмы, Данилов из Вельска.

Прием моделирования с помощью диаграмм (кругов) Эйлера-Венна

Данный метод позволяет графически решать математические задачи на основе применения теории множеств.

Задача 10. В классе 36 человек. Ученики этого класса посещают математический, физический и химический кружки, причем математический кружок посещают 18 человек, физический – 14, химический – 10. Кроме того, известно, что 2 человека посещают все три кружка, 8 человек – и математический и физический, 5 – и математический и химический, 3 – и физический и химический.

Сколько учеников класса не посещают никаких кружков?

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

Пусть МФХ – множество ребят, каждый из которых посещает все 3 кружка. Дадим аналогичные имена и другим множествам: МФ – множество занимающихся и в математическом, и в физическом кружке (и, возможно, также в химическом), МФ - и в математическом, и в физическом, но не в химическом и т.д.

Впишем нужные имена множеств в области, изображенные на рисунке:

Х

Обратимся к числовым данным. В область МФХ впишем число 2, так как все три кружка посещают 2 ученика. Далее известно, что ребят, посещающих и математический, и физический кружок, - 8. Значит, множество МФ состоит из 8 человек. Но это множество является объединением множеств МФХ и МФ, причем в МФХ входят 2 человека. Значит, на долю МФ остается 6 человек.

Теперь рассмотрим множество МХ, состоящее из 5 человек. Оно также состоит из двух частей: на МФХ приходится 2 человека. Значит, на МХ – 3.

Множество ФХ состоит из 3 человек. На ФХ приходится 1 человек.

Рассмотрим теперь множество М, в которое входит 18 учеников. Оно состоит из четырех частей. Количественный состав трех подмножеств мы уже нашли: это 2, 6 и 3. Значит, в четвертое подмножество, а именно в М, входит 18 – (2 + 3 + 6) = 7 человек.

Аналогично определим количество учащихся в множествах и :
14 – (6 + 2 + 1) = 5, 10 – (3 + 2 + 1) = 4.

Три пересекающихся круга образуют 7 непересекающихся областей, изображающих непересекающиеся подмножества учеников, каждый из которых посещает хотя бы 1 кружок. Просуммируем цифры в этих областях: 6 + 5 + 7 + 3 + 2 + 1 + 4 = 28 человек посещает кружки.

Значит, 36 – 28 = 8 ребят не посещают никаких кружков.

Ответ: в классе 8 учеников, не посещающих кружки.

Задача 11. Среди 150 школьников марки собирают только мальчики. 67 человек собирают марки СССР, 48 человек – Африки и 32 человека – Америки, 11 человек – только СССР, 7 человек – только Африки, 4 человека – только Америки и только Иванов собирал марки СССР, Африки, Америки. Найдите максимальное число девочек. (Задачи повышенной трудности в курсе алгебры 7-9 классов: Кн. для учителя / Н.П. Кострикина. – М.: Просвещение, 1991, задача № 176)

Решение. Изобразим с помощью кругов Эйлера условие задачи

Имеем систему трех уравнений:

(56 = 67 – 11),

(41 = 48 – 7),

(28 = 32 – 4),

откуда 2 (x + y + z) = 122, т.е. x + y + z = 61.

Следовательно, марки собирают 61 + 11 + 7 + 4 + 1 = 84 мальчика, максимальное число девочек: 150 – 84 = 66.

Ответ: 66 девочек.

Задача 12. После зимних каникул классный руководитель спросил, кто из ребят ходил в театр, кино или цирк. Оказалось, что из 36 учеников класса двое не были ни в кино, ни в театре, ни в цирке. В кино побывало 25 человек, в театре – 11, в цирке – 17; и в кино, и в театре – 6; и в кино, и в цирке – 10; и в театре, и в цирке – 4.

Сколько человек побывало и в кино, и в театре, и в цирке?

Решение. Изобразим с помощью кругов Эйлера условие задачи.

К

Т

4-х

Ц

6-х

9 + х

1 + х

10-х

2

х

3 + х

В область КТЦ впишем х. Известно, что в кино и в театре побывала 6 человек, значит, на долю КТ остается (6 –х) человек. Аналогично на КЦ приходится (10 – х) человек, на ТЦ – (4 – х) человек.

Рассмотрим множество К, в которое входит 25 человек. Оно состоит из четырех частей. Количественный состав трех подмножеств мы уже нашли: это х, 6-х и 10-х. Значит, в четвертое подмножество, содержащее ребят, которые побывали только в кино входит
25 – (х + 6 – х + 10 – х) = 9 + х человек.

Аналогично определим количество учащихся, посетивших только театр:
11 – (х + 6 – х + 4 – х) = 1 + х и количество учащихся, посетивших только цирк:
17 – (х + 10 – х + 4 – х) = 3 + х.

Просуммируем выражения в 7 непересекающихся областях, изображающих подмножества учеников, каждый из которых посетил хотя бы одно культурное заведение:

(9+х)+(6-х)+(1+х)+(10-х)+х+(4-х)+(3+х)=33+х.

По условию из 36 учеников класса 2 ученика нигде не были. Значит,

33 + х = 34, х = 1

Ответ: один человек побывал и в кино, и в театре, и в цирке.

Прием моделирования с помощью блок-схемы

При применении данного метода каждый шаг в рассуждении выделяется отдельным изображением (прямоугольником).

Задача 13. На некотором острове отдельными селениями живут правдолюбы и шутники. Правдолюбы всегда говорят только правду, а шутники постоянно шутят, а поэтому всегда лгут. Жители одного племени бывают в селении другого, и наоборот. В одно из селений попал путешественник, но не знает, в какие именно. Доказать, что путешественнику достаточно первому встречному задать вопрос: «Вы местный?», чтобы по ответу определить, в селении какого племени он находится.

Решение. Путешественник может попасть или в селение, или в селение «шутников» - появляются два различных варианта. В селении «правдолюбов» путешественник может встретить как «правдолюба», так и «шутника». Аналогично, в селении «шутников» путешественник может встретить как «шутника», так и «правдолюба». Возможных вариантов стало уже четыре.

Блок-схема позволяет их представить наглядно и заметить, что положительный ответ в любом случае возможен только в селении «правдолюбов», а ответ «нет» - только в селении «шутников».

Прием моделирования с помощью алгебры высказываний

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

Задача 14. В одном королевстве были незамужние принцессы, голодные тигры и приговоренный к казни узник. Но король всякому узнику, осужденному на смерть, давал последний шанс спастись. Ему предлагалось угадать, в какой из двух комнат находится тигр, а в какой принцесса. Хотя вполне могло быть, что король в обеих комнатах разместил принцесс или, что хуже, в обеих тигров. Выбор надо было сделать на основании табличек на дверях комнат. Причем, узнику было известно, что утверждения на табличках либо оба истинны, либо оба ложны. Надписи гласили:

Первая комната: Вторая комната:

По крайней мере, в одной из этих комнат находится принцесса

Тигр
в другой комнате

Какую дверь должен выбрать узник?

Решение.

Введем обозначения:

П₁ = В первой комнате находится принцесса.

= В первой комнате находится тигр.

П₂ = Во второй комнате находится принцесса.

= Во второй комнате находится тигр.

А – утверждение на первой двери: А = П₁  П₂

В – утверждение на второй двери: В =

Условие задачи о том, что утверждения на табличках либо одновременно истинные, либо одновременно ложные, записывается так:

А & B  = 1.

Подставим вместо А и В соответствующие формулы и упростим:

А & B  = ((П₁  П₂) & )  ((

= .

Итак, = 1. Значит, в первой комнате находится тигр, во второй – принцесса.

Ответ: в первой комнате – тигр, во второй – принцесса.

Литература

1. Логика в информатике / В.Ю. Лыскова, Е.А. Ракитина. – М.: Лаборатория Базовых Знаний, 2001.

2. Задачи повышенной трудности в курсе алгебры 7-9 классов: Кн. для учителя / Н.П. Кострикина. – М.: Просвещение, 1991.

3. Математические олимпиады в школе. 5-11 классы / А.В. Фарков. – М.: Айрис-пресс, 2008.

4. Журнал «Математика в школе», № 3, 2005.

5. ЕГЭ 2016. Математика. Базовый уровень. 30 вариантов типовых тестовых заданий / под ред. И.В. Ященко. – М.: Издательство «Экзамен», 2016.