Статья: Решение логических задач различных типов на занятиях кружка Умники и умницы

Приказчикова Татьяна Алексеевна,
Учитель информатики и ИКТ,
педагог дополнительного образования
ГБОУ школа №302 Фрунзенского района
Санкт-Петербурга

Решение логических задач различных типов
Тема «Алгебра логики» позволяет развивать логическое мышление. Целесообразно проводить решение логических задач в системе, начиная от самых простейших, которые способен решить любой ученик начальной школы, причём обязательно обращать внимание старшеклассников на объём знаний по информатике, необходимый для решения задачи. Как показывает практика, простейшие задачи не требуют знаний из области алгебры логики, а достаточно владеть методом рассуждений.
В данной работе собраны, систематизированы по типам и ранжированы по уровню сложности задачи по логике, а также из смежных с информатикой теоретических областей, которые могут быть предложены для решения учащимся 5-11 классов. В 11 классе желательно рассмотреть решение задач различных типов. Внутри каждого типа задачи расположены в порядке возрастания сложности. Для их решения необходимо вдумчиво проанализировать исходные данные, творчески отнестись к уже имеющимся знаниям и применить их в новых ситуациях. Ко всем задачам, включенным в работу, приведены ответы; для ряда задач имеются указания, дающие ключ к решению. Кроме того, приведены полные решения наиболее сложных задач.
При решении задач методом рассуждений, необходимо обратить внимание учащихся, на то, что предположение в задачах необходимо делать только одно, и затем, исходя из него, выходить либо на правильный ответ, либо получать несоответствие с условием задачи. Обратить внимание учащихся, на то, что решение любой задачи начинаем со слов « Предположим, что.. сказал истину, тогда..». Проводим дальнейшее рассуждение по условию задачи. На начальном этапе изучения рассматривать все варианты, даже, если первое предположение приводит к правильному решению, тем самым убедить учеников, что все остальные варианты будут иметь расхождения с условием. В каждой задаче имеется важное условие или высказывание, которое на первоначальном этапе необходимо выделять для учащихся другим цветом и обращать их внимание на важность этого условия, без которого задача нерешаема вообще или имеет множество решений.
Составление таблиц соответствия
При решении задач запись представлена в виде таблицы, в которой наглядно отображено соответствие между понятиями. Учащиеся 5-7 классов могут решать задачи, обозначая соответствие -«+», а несоответствие «-». Для учащихся 5-7 класса полезно дать определения кругов Эйлера. Закрепление провести при решении задач. ( См. приложение, урок №1).
1.Три девочки Роза, Маргарита и Анюта представили на конкурс цветоводов корзины выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек?

Р
М
А

Р
0
1
0

М
0
0
1

А
1
0
0

2. Пятеро одноклассников: Ирина, Тимур, Камилла, Эльдар и Залим стали победителями олимпиад школьников по физике, математике, информатике, литературе и географии. Известно, что:
победитель олимпиады по информатике учит Ирину и Тимура работе на компьютере;
Камилла и Эльдар тоже заинтересовались информатикой;
Тимур всегда побаивался физики;
Камилла, Тимур и победитель олимпиады по литературе занимаются плаванием;
Тимур и Камилла поздравили победителя олимпиады по математике;
Ирина сожалеет о том, что у нее остается мало времени на литературу.
Победителем какой олимпиады стал каждый из этих ребят?

И
Т
К
Э
З

Ф
0
0
1
0
0

М
1
0
0
0
0

И
0
0
0
0
1

Л
0
0
0
1
0

Г
0
1
0
0
0

3.Ирина любит мороженое с фруктами. В кафе был выбор из таких вариантов:
пломбир с орехами;
пломбир с бананами;
пломбир с черникой;
шоколадное с черникой;
шоколадное с клубникой.

В четырёх вариантах Ирине не нравились или тип мороженого, или наполнитель, а в одном варианте ей не нравились ни мороженое, ни наполнитель. Она попросила приготовить из имеющихся продуктов порцию по своему вкусу. Какое же мороженое и с какими фруктами любит Ирина?
4.Три молодые мамы Анна, Ирина и Ольга, гуляя в парке со своими малышами, встретили свою четвертую подругу. На вопрос, как зовут малышей, желая подшутить над подружкой, они ответили:
Анна: моего малыша зовут Денис, а Кирилл – сын Ирины.
Ирина: моего сыночка зовут Максим, а Кирилл – сын Анны.
Ольга: мой мальчик – Кирилл, а сына Анны зовут Максим.
Каждая из них один раз сказала правду и один раз солгала. Как зовут мальчиков Анны, Ирины и Ольги? В ответе перечислите подряд без пробелов буквы, соответствующие именам мальчиков в указанном порядке имен их мам, например КМД.

А
И
О
А
И
О

Д
1
0
0
1
1
1

К
0
0
1
0
0
0

М
0
1
0




Ответ: ДМК
5. При составлении расписания на пятницу были высказаны пожелания, чтобы информатика была первым или вторым уроком, физика первым или третьим, история вторым или третьим. Можно ли удовлетворить одновременно все высказанные пожелания?
Инф
Ф
Ис
Инф
Ф
Ис

1
0
0
0
1
0

0
0
1
1
0
0

0
1
0
0
0
1

Ответ: И ИС Ф или Ф И ИС
Составление соответствия на прямой
При решении данных задач соответствие выставляем на прямой, причем первые четыре условия позволяют определить порядок размещения на прямой, а затем табличное представление соответствия.
6. На одной улице в ряд четыре дома, в которых живут Алексей, Егор, Виктор, Михаил. Известно, что каждый из них владеет ровно одной профессией Токарь, Столяр, Хирург, Окулист.
Известно, что
Токарь живёт через дом от Столяра;
Хирург живёт левее Токаря;
Окулист живёт правее Токаря;
Хирург живёт не рядом со Столяром;
Михаил не Токарь;
Алексей живёт рядом с Окулистом;
Егор живёт справа от Токаря;
Виктор рядом с Хирургом.
Запишите имена (слева направо)
7. На одной улице в ряд четыре дома, в которых живут Алексей, Егор, Виктор, Михаил. Известно, что каждый из них владеет ровно одной профессией Токарь, Столяр, Хирург, Окулист.
Известно, что
Токарь левее Столяра;
Хирург правее Окулиста;
Окулист рядом со Столяром;
Токарь не рядом со Столяром;
Виктор правее Окулиста;
Михаил не Токарь;
Егор рядом со Столяром;
Виктор левее Егора.
Запишите имена (слева направо)
Метод рассуждения путём анализа истинности частей сложных высказываний
8.Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:
А) Макс победит, Билл – второй;
В) Билл – третий, Ник – первый;
С) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
Рассмотрим решение данной задачи двумя способами
I способ:
каждый из трех болельщиков высказал два утверждения, всего получилось 6; обозначим их так:
A: М1 = «Макс – первый», Б2 = «Билл – второй»
B: Н1 = «Ник – первый», Б3 = «Билл – третий»
C: Д1 = «Джон – первый», М4 = «Макс – четвертый»

A: М1 + Б2 = 1, (по крайней мере одно из двух условий истинно)
М1 · Б2 = 0 (по крайней мере, одно из двух условий ложно)
аналогично для остальных болельщиков
B: Н1 + Б3 = 1, Н1 · Б3 = 0
С: Д1 + М4 = 1, Д1 · М4 = 0

(М1 + Б2) · (Н1 + Б3) · (Д1 + М4) = 1

(М1 · Н1 + М1 · Б3 + Б2 · Н1 + Б2 · Б3) · (Д1 + М4) = 1
во-первых, два человека (Макс и Ник) не могут одновременно находиться на первом месте, поэтому М1 · Н1 = 0
во-вторых, один человек (Билл) не может одновременно находиться и на втором, и на третьем месте, поэтому Б2 · Б3 = 0, так что
(М1 · Б3 + Б2 · Н1) · (Д1 + М4) = 1

М1 · Б3 · Д1 + М1 · Б3 · М4 + Б2 · Н1 · Д1 + Б2 · Н1 · М4 = 1
М1 · Д1 = 0, М1 · М4 = 0 и Н1 · Д1 = 0, так что
Б2 · Н1 · М4 = 1 (*)
Б2 = 1 (Билл на втором месте), Н1 = 1 (Ник – на первом) и М4 = 1 (Макс – на четвертом), а Джону осталось третье
таким образом, правильный ответ 3124
обратите внимание, что вторые условия (М1 · Б2 = 0, Н1 · Б3 = 0 и Д1 · М4 = 0 ) мы даже нигде не использовали, все получилось «само собой», поскольку уравнение (*) имеет единственное решение.


II способ:



Ответ: 3124
9. Когда сломался компьютер, его хозяин сказал «Память не могла выйти из строя». Его сын предположил, что сгорел процессор, а винчестер исправен. Пришедший специалист по обслуживанию сказал, что, скорее всего, с процессором все в порядке, а память неисправна. В результате оказалось, что двое из них сказали все верно, а третий – все неверно. Что же сломалось?
П Пр В
Х Сын Спец
1 1 0
0 1 0

Ответ: Процессор.
10. Три друга Олег, Борис и Арсений, закончив институт, разъехались по разным городам. И вот спустя несколько лет, они, встретившись на вечере встречи выпускников, решили разыграть своего товарища. На его вопрос, где они теперь живут, друзья ответили:
Олег: я живу в Екатеринбурге, а Борис - в Мурманске.
Борис: я живу в Волгограде, а Олег - в Мурманске.
Арсений: я живу в Мурманске, а Олег - в Волгограде.
Каждый из них один раз сказал правду и один раз солгал. Где живут Арсений, Борис и Олег? В ответе перечислите подряд без пробелов первые буквы названий городов, соответствующие именам друзей в указанном порядке, например ВМЕ.
А Б О
М В Е
О Б А
1 1 1
0 0 0

Ответ: Арсений из Мурманска; Борис из Волгограда, Олег из Екатеринбурга
Метод рассуждений
11. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГАИ, что это были “Жигули”, первая цифра номера машины единица. Второй свидетель сказал, что машина была марки “Москвич”, а номер начинался с семёрки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?
Ответ: Жигули, номер начинается с 7.
12. Алеша, Витя и Игорь после уроков нашли на полу в кабинете физики маленькую гирьку. Каждый из них, рассматривая находку, высказал два предположения. Алеша сказал: «Это гирька из латуни, и весит она, скорей всего, 5 г», Витя предположил, что гирька сделана из меди и весит 3 г. Игорь же считал, что гирька не из латуни и вес ее – 4 г. Учитель физики обрадовался, что пропажа нашлась, и сказал ребятам, что каждый из них прав только наполовину. Из какого металла – латуни (Л) или меди (М) – изготовлена гирька, и каков ее вес? В ответе запишите первую букву названия металла, а затем цифру, соответствующую весу гирьки, например, Л4.


Ответ: М5
Метод рассуждений путём анализа истинности высказываний каждого участника
13.1 апреля три подружки Аня, Света и Оля решили разыграть одноклассников и договорились, что одна из них будет говорить сегодня только ложь, другая только правду, а третья через раз то ложь, то правду. Они втроем прогуляли классный час и пришли только на праздник, хотя раньше так никогда не поступали. Классный руководитель выслушала девочек:
Аня: Я всегда прогуливаю классный час, а Света скажет вам неправду.
Света: Я сегодня первый раз прогуляла классный час.
Оля: Аня сегодня говорит только чистую правду.
Классный руководитель догадалась, кто из девочек сегодня в какой роли выступает. Расположите первые буквы имен девочек в таком порядке: «Всегда говорит правду», «Всегда лжет», «Говорит правду через раз». (Пример: если бы имена девочек были: Зина, Маша и Вера, ответ тогда был бы: МВЗ )
Ответ: САО.
14. Проверяя дневники, классный руководитель заметил, что мальчику Роме исправлены все двойки за неделю, а сделать это могли только три его друга: Максим (М), Андрей (А) и Костя (К), которые задержались на перемену в классе. Они были вызваны к директору, где их спросили о том, кто подделал оценку:
Андрей: Максим этого не делал, это все Костя красной ручкой!
Костя: Я этого не делал, потому что оценку исправил Максим!
Максим: Ничего я не исправлял! Да и Андрей тоже...
Стало известно, что один из мальчиков сказал чистую правду, второй все соврал, а третий сказал правду только в половине своего ответа. Кто же подделал оценку Роме? Запишите только первую букву имени.
Ответ: М
15. На перемене в кабинете биологии 8 ребят баловались и разбили дорогой микроскоп. Их всех вызвали к директору и выслушали:

Ира: Это Антон разбил.
Наташа: Нет, Антон не бил!
Сергей: А я тоже знаю, что это Наташа разбила!
Антон: Нет, ни Наташа, ни Сергей этого не делали!
Оля: А я видела, что разбил Сергей!
Максим: Это кто-то чужой!
Костя: Это либо Наташа, либо Сергей больше некому!
Кто разбил микроскоп, если известно, что из этих высказываний истинны только два?(Ответ запишите в виде первой буквы имени.)
Составление логического выражения или таблицы истинности по значению логического умножения или сложения нескольких высказываний
16. Из двух высказываний «Дядя Федор и кот Матроскин не любят молоко» и «Кот Матроскин не любит молоко» одно ложно, а другое истинно. Кто из них не любит молоко?
Оба не любят молоко.
Оба любят молоко.
Кот Матроскин любит молоко, а Дядя Федор нет.
Дядя Федор любит молоко, а Кот Матроскин нет.





17.На вопрос, кто из десятиклассников, присутствующих на олимпиаде по физике, сможет решить самую трудную задачу, учитель ответил: «Если задачу может решить Виктор, то ее может решить и Степан, но неверно, что если задачу может решить Антон, то может решить ее и Степан» и оказался прав, когда результаты олимпиады стали известны. Кто из трех десятиклассников решил самую трудную задачу?
Пусть В – Виктор, С – Степан, А – Антон.
I способ: Составить таблицу истинности для выражения
II способ:
13 EMBED Equation.3 1415
Ответ: Антон
18. На вопрос, какая завтра будет погода, синоптик ответил:
а) «если не будет ветра, то будет пасмурная погода без дождя»;
б) «если будет дождь, то будет пасмурно и без ветра»;
в) «если будет пасмурная погода, то будет дождь и не будет ветра».
С помощью алгебры логики определить погоду на завтра.
Решение:
Пусть А-ветер, В-пасмурно, С-дождь.
а) 13 EMBED Equation.3 1415 13 EMBED Equation.3 141513 EMBED Equation.3 1415
б) 13 EMBED Equation.3 1415 =13 EMBED Equation.3 1415
в) 13 EMBED Equation.3 1415
Ответ: ветер, непасмурно, без дождя.
Список литературы

Занимательные задачи по информатике Л. Л. Босова, А. Ю. Босова, Ю. Г. Коломенская. – М.: Бином. Лаборатория знаний, 2005. – 119 с.
ЕГЭ 2010: Информатика: сборник заданий /Е. М. Зорина, М. В. Зорин. – М.: Эксмо, 2009. – 208 с.
Готовимся к ЕГЭ по информатике. Элективный курс: учебное пособие / Н.Н. Самылкина, С. В. Русаков, А. П. Шестаков, С. В. Баданина. – 2-е изд., испр. – М.: БИНОМ. Лаборатория знаний, 2008. – 298 с.
Единый государственный экзамен 2009. Информатика. Универсальные материалы для подготовки учащихся / Под редакцией В. Р. Лещинера / ФИПИ. – М.: Интеллект-Центр, 2009. – 136 с.
Учимся информатике: задачи и методы их решения А. И. Гусева. – 2-е изд. – М.: «Диалог-МИФИ», 2001. – 384 с.
Информатика: Учеб. пособие для 10 – 11 кл. общеобразоват. Учреждений / Л. З. Шауцукова. – 2-е изд., дораб. – М.: Просвещение, 200









1 0
1 0
1 0
0 0
0 1
0 0
0 1
0 0
1 0
1 0
0 0
0 0
0 1
1 1
1 0


Ответ: Пломбир с клубникой


Решение:


Х Т О С
М
*
М
М

*
А
*
А

*
*
Е
Е

*
В
*
*


Ответ: М В Е А

Решение:


Т О С Х
*
*
В
В

*
М
М
М

*
Е
*
Е

А
*
*
*


Ответ: А М В Е

И 1
Н 0
С 0
А 1
О 0
М 0
К 0

Ответ: Антон

Решение:
А – д. Федор не любит молоко
В – кот Матроскин не любит молоко

А
0
0
1
1
В
0
1
0
1
А и В
0
0
0
1

Ответ: д. Федор – любит молоко, кот Матроскин – не любит.

Д Н Б М
3 м 1 м
А В С
1 1 0
0 0 0

Д Н Б М
3 м 1 м 2 м 4 м
А В С
0 0 1
1 1 0



1) 2) 3)
Ж 1 1 0 0
М 7 0 1 1

5гр 1) 2) 3)
Л 3гр 1 0 0
М 4гр 0 1 0

5гр 1) 2) 3)
Л 3гр 0 1 1
М 4гр 1 0 0

А С О
0 1 0
0