"Решение логических задач различными способами".
Автор: Петухова Анна Алексеевна, учитель математики и информатики и ИКТ.
Описание работы: Логика одна из традиционных тем, которая присутствует в любом варианте курса информатики, олимпиадных задач по математике. Данный материал будет полезен для учителей информатики и математики, желающих сделать свои уроки интереснее, мотивировать учеников для дальнейшего развития логического мышления. Успешное решение трудной задачки, потребовавшей немалых умственных усилий, приносит чувство удовлетворения, независимо от того отличаются они особой одарённостью или нет, но кроме того, эти способы решения задач помогают совершенствованию умения решать те проблемы, которые ставит перед нами жизнь. Развитие навыков решения задач, безусловно, способствует повышению уровня интеллекта. Возраст учащихся 7 –10 класс. Представленные задания можно использовать как в процессе проведения урока по предмету, так и для внеурочных мероприятий или включать в тестовые работы. Некоторые задачи даны с решениями.
Цели занятия:
- знакомство с логическими задачами. Знакомство с табличным способом решения задач.
- развитие логического мышления, повышение уровня интеллекта.
- совершенствованию вашего умения решать те проблемы, которые ставит перед вами жизнь.
Решение логических задач табличным способом.
Главным в предлагаемых задачах является способ решения — построение таблицы, строки которой соответствуют элементам одного из рассматриваемых в условии задачи множеств, столбцы — элементам другого, пересечение строки и столбца — комбинации двух элементов разных множеств. С помощью такой таблицы анализируются условия задачи, делаются выводы, проверяется избыточность, полнота и правильность выводов.
Задача 1. После соревнований бегунов на табло появилась надпись:
• Рустам не был вторым.
• Эдуард отстал от Рустама на два места.
• Яков не был первым.
• Галина не была не первой ни последней.
• Карина финишировала сразу за Яковом.
Кто же победил в этих соревнованиях? Каково было распределение бегунов на финише?
Решение:
Рисуем таблицу, где столбцы –имена детей, а строки – номера мест. Читаем задачу, пошагово анализируем условие и ставим в таблицу «+», если соответствие установлено и «–», если точно соответствия нет.
Так как Рустам не был вторым и Эдуард отстал от Рустама на два места, то Эдуард не может быть ни первым, ни вторым, ни четвёртым.
Яков не был первым и Галина не была не первой ни последней и так как Карина финишировала сразу за Яковом то она не могла быть ни первой ни второй.
Отсюда видно, что Рустам был первым тогда Эдуард (по условию 2) был третьим.
Так как Карина финишировала сразу за Яковом, то очевидно, что Яков был четвёртым, а Карина последней и тогда Галина была второй.
Итак, можно выделить
Пять простых шагов на пути поиска решения логических задач.
1. Составляйте таблицу, так как в таблице удаётся учесть все возможные варианты.
2. Внимательно читайте каждое утверждение, так как в каждом содержится что-то такое, что позволит вам исключить хотя бы один из вариантов.
3. Старайтесь отыскать ключевое утверждение, оно поможет развязать весь клубок.
4. После того как вы сравнили все утверждения и исключили из них те, невероятность которых была на поверхности, сравните утверждения между собой, установите связи и противоречия.
5. Решение можно найти простым методом последовательных исключений.
Чем больше будете тренироваться, тем лучше у вас это будет получаться. А теперь за дело.
Задача 2.
В субботний вечер Семен, Коля и Витя решили развлечься. У них был выбор: кино, рок-концерт или танцы.
• Семён любит кино, но к танцам менее нетерпим, чем к рок-музыке.
• Коля любит танцевать, но готов пойти в кино скорее, чем на рок концерт.
• Витя любит рок-музыку меньше чем танцы, но кино ему всё-таки не так неприятно, как танцы или концерт.
Поскольку вопрос решатся большинством голосов, то куда, на ваш взгляд отправились эти ребята?
Задача 3.
Трое мальчиков Костя, Фома и Марат дружили с тремя девочками – Женей, Светой и Мариной. Но вскоре компания разделилась на пары, потому, что оказалось:
• Света ненавидит ходить на лыжах.
• Костя, Женин брат часто катается со своей подружкой на лыжах
• А Фома теперь бежит на свидание к Костиной сестре.
С кем же проводит время Марат?
Задача 4.
Шестеро друзей в ожидании электрички заскочили в буфет.
• Маша взяла то же, что и Егор, и вдобавок ещё бутерброд с сыром.
• Аня купила, то же, что и Саша, но не стала покупать шоколадное печенье.
• Кирилл ел то же, что и Мила, но без луковых чипсов.
• Егор завтракал тем же что и Аня, но бутерброду с котлетой предпочел картофельные чипсы.
• Саша ел то же, что и Мила, но вместо молочного коктейля пил лимонад.
Из чего состоял завтрак каждого из друзей?
Решение: Так как
• Маша взяла то же, что и Егор, и вдобавок ещё бутерброд с сыром;
• Аня купила, то же, что и Саша, но не стала покупать шоколадное печенье;
• Кирилл ел то же, что и Мила, но без луковых чипсов;
• Егор завтракал тем же что и Аня, но бутерброду с котлетой предпочел картофельные чипсы;
• Саша ел то же, что и Мила, но вместо молочного коктейля пил лимонад, то:
Второй раз проанализируем условия.
• Маша взяла то же, что и Егор, и вдобавок ещё бутерброд с сыром.
• Аня купила, то же, что и Саша, но не стала покупать шоколадное печенье.
• Кирилл ел то же, что и Мила, но без луковых чипсов.
• Егор завтракал тем же что и Аня, но бутерброду с котлетой предпочел картофельные чипсы и Маша взяла то же, что и Егор, и вдобавок ещё бутерброд с сыром.
• Саша ел то же, что и Мила, но вместо молочного коктейля пил лимонад, то и Кирилл ел то же, что и Мила, но без луковых чипсов.
Третий раз проанализируем условия.
• Аня купила, то же, что и Саша, но не стала покупать шоколадное печенье.
• Саша ел то же, что и Мила, но вместо молочного коктейля пил лимонад, то и Кирилл ел то же, что и Мила, но без луковых чипсов.
• Аня купила, то же, что и Саша, но не стала покупать шоколадное печенье
• Маша взяла то же, что и Егор, и вдобавок ещё бутерброд с сыром
Задача 5.
В одном небольшом кафе в смене одновременно работали 5 человек: администратор, повар, кондитер, кассир, дворник. Одновременно на работу выходили мисс Галбрейт, мисс Шерман, мистер Вильямс, мистер Вортман и мистер Блейк. При этом известно, что:
1. Повар – холостяк.
2. Кассир и администратор жили в одной комнате, когда учились в колледже.
3. Мистер Блейк и мисс Шерман встречаются только на работе.
4. Миссис Вильямс расстроилась, когда муж сказал ей, что администратор отказал ему в отгуле.
5. Вортман собирается быть шафером на свадьбе у кассира и кондитера.
Кто на какой должности в этом кафе?
Решение:
Естественно, что на уроке я не использую все предложенные задачи, а подбираю для каждого класса индивидуально, в зависимости от их подготовленности и способностей.
2.Задачи для самостоятельного решения.
Задача 1.
Коля, Боря, Вова и Юра заняли первые четыре места в спортивном соревновании. На вопрос, какие места они заняли, они ответили:
1) "Коля не занял ни первое, ни четвертое места".
2) “Боря занял второе место”.
3) “Вова не был последним”.
Какое место занял каждый мальчик?
Задача 2.
Три одноклассника - Влад, Тимур и Юра встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой - физиком, а третий - юристом. Один увлекся туризмом, другой - бегом, третий - регби.
1. Юра сказал, что, на туризм ему не хватает времени, хотя его сестра - единственный врач в семье, заядлый турист.
2. Врач сказал, что он разделяет увлечение коллеги.
3. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен.
Кто чем любит заниматься в свободное время и у кого какая профессия?
Задача 3.
Три друга — Иван, Дмитрий, Степан преподают различные предметы (химию, литературу, физику) в школах Москвы, Калининграда и Перми. Известно:
1) Иван работает не в Москве, а Дмитрий не в Калининграде;
2) москвич преподает не физику;
3) тот, кто работает в Калининграде, преподает химию;
4) Дмитрий преподает не литературу.
Какой предмет и в каком городе преподает каждый из товарищей?
Задача 4.
Четыре девочки Маша, Таня, София и Полина взяли в кафе сок. Каждая из них покупал только один сок, причем две из них купили сок яблочный, одна виноградный, и одна – грушевый. Известно, что у Маши и Тани разные вкусы. Разные соки взяли Маша с Софией, Полина с Софией, Полина с Машей и Таня с Софией. Кроме того известно, что Маша купила не грушевый сок. Определить, какой сок пила каждая из них.
Задача 6. (Один из вариантов «Задачи Эйнштейна»)
Пять домов стоят вдоль дороги, один за другим.
1. Доцент живёт в красном доме.
2. Гробовщик держит собак.
3. Сантехник пьёт чай.
4. Зелёный дом слева от белого.
5. Хозяин зелёного дома пьёт кофе.
6. Любитель «Примы» держит птицу.
7. Хозяин жёлтого дома курит «Беломор канал».
8. В центральном доме любят молоко.
9. Приёмщик стеклотары живёт в первом доме.
10. Курящий «Яву» сосед хозяина кошек.
11. Хозяин лошадей – сосед курящего «Беломор».
12. Любитель пива курит «Кубинские» сигары.
13. Ночной сторож предпочитает сигареты «Друг».
14. Приёмщик стеклотары живёт рядом с синим домом.
15. Курящий «Яву» сосед пьющего воду.
Кто держит рыб? (номер дома, цвет профессия, напитки)
Решение:
Задачи, составленные моими учениками.
1.На дискотеку пошли 4 девочки: Маша, Оля, Рита. На медленный танец их приглашали Сергей, Рома, Саша, Паша. Кто с кем танцевал, если:
1) Оля не танцевала с Пашей;
2) Таня не танцевала с Пашей и Романом;
3) Рита танцевала с Ромой;
4) Оле понравился Сергей, но она не танцевала с ним.
2. Бизнесмены Боря Вова Гриша и Гена зарабатывают сумасшедшие деньги, их фамилии засекречены, но удалось их узнать, правда непонятно какая кому принадлежит. Их фамилии: Иванов, Енин, Сидоров, Петров. Так же наши шпионы выяснили:
1) Боря и Петров не имеют личные самолёты.
2) Гриша и Иванов вообще ничего личного не имеют, кроме счетов в швейцарском банке.
3) Гена теперь важнее Енина, хотя Енин и имеет личный самолёт.
4) Петров важнее Енина.
У кого какая фамилия?
3. Четыре подружки: Даша, Маша, Ольга и Таня ходили в магазин покупать подарки. И все подарки разные. Блокнот, альбом, брелок, и книга. На вопрос кто какие подарки купил, они ответили так:
1) Даша и Оля не знали кто купил блокнот;
2) Оля сказала, что Даша и Маша вместе с ней посещали магазин, где продают брелки.
3) Даша не покупала альбом.
Кто какой подарок купил
Решение задач с помощью алгебры логики.
Одним из мощных методов решения логических задач является решение с помощью законов алгебры логики.
Алгоритм решения логических задач с помощью алгебры логики:
1) внимательно изучить условие;
2) выделить простые высказывания и обозначить их латинскими буквами;
3) записать условие задачи на языке алгебры логики;
4) составить конечную формулу, для этого объединить логическим умножением формулы каждого утверждения, приравнять произведение единице;
5) упростить формулу, проанализировать полученный результат или составить таблицу истинности, найти по таблице значения переменных, для которых F = 1, проанализировать результаты.
Задача 1. " Кто преступник"
Определить участника преступления, исходя из двух
посылок:
1) "Если Иванов не участвовал или Петров участвовал,
то Сидоров участвовал";
2) "Если Иванов не участвовал, то Сидоров не
участвовал".
Рассмотрим решение этой несложной задачи двумя способами: с помощью таблиц истинности и с помощью алгебраических преобразований.
1 способ.
Составим выражения:
I - "Иванов участвовал в преступлении";
P - "Петров участвовал в преступлении";
S - "Сидоров участвовал в преступлении"
.
Запишем посылки в виде формул:
¬I˅P→S и ¬I→¬S
Из таблицы видно, что совершил преступление Иванов
Способ 2.
Применим для решения этой же задачи преобразования с
помощью законов алгебры логики:
( ¬I˅P→S) &( ¬I→¬S)=(¬(¬I˅P)˅S) & (I˅¬S) =
= (I & ¬P ˅S) &(I ˅¬S) = I&¬P˅ I & S˅ I &¬P &¬S ˅0=
= I&¬P ˅ I & S =I & (¬P˅S)
Из последнего выражения видно, что выражение верно, если I=1, значит преступник - Иванов.
Задача 2 "Прогноз погоды"
На вопрос, какая завтра будет погода, синоптик ответил:
1. Если не будет ветра, то будет пасмурная погода без дождя.
2. Если будет дождь, то будет пасмурно и без ветра.
3. Если будет пасмурная погода, то будет дождь и не будет ветра.
Так какая же погода будет завтра?
Решим эту задачу средствами алгебры логики.
Решение:
1. Выделим простые высказывания и запишем их через переменные:
A – «Ветра нет»
B – «Пасмурно»
С – «Дождь»
2. Запишем логические функции (сложные высказывания) через введенные переменные:
Если не будет ветра, то будет пасмурная погода без дождя:
A → B & C
Если будет дождь, то будет пасмурно и без ветра:
С → B & A
Если будет пасмурная погода, то будет дождь и не будет ветра
B → C &
в) Запишем произведение указанных функций:
F=(A→ B & C) & (C→B & A) & (B→ C & A)
Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):
F=(A→ B & ¬C) & (C→B & A) & (B→ C & A)
= (¬A v B & ¬C) & (¬C v B&A) & (¬B v C&A) =
= (¬A v B & ¬C) & (¬B v C&A) & (¬C v B&A) =
= (¬A &¬ B v B&¬C&¬B v ¬A&C&A v B&¬C&C&A) &
(C v B&A)=
= ¬A & ¬B &(C v B&¬A) =A&¬B&C v¬ A&¬B&B&¬A =
= ¬A&¬B&¬C
3. Приравняем результат единице, т.е. наше выражение должно быть истинным:F = ¬A &¬ B & ¬C = 1 и проанализируем результат:
Логическое произведение равно 1, если каждый множитель равен 1.
¬A = 1; ¬B = 1; ¬C = 1.значит: A = 0; B = 0; C = 0;
Ответ: погода будет ясная, без дождя, но ветреная.
Задача 3 «История с амфорой».
Алеша, Боря и Гриша нашли в земле сосуд. Рассматривая удивительную находку, каждый высказал по два предположения.
Алеша: «Это сосуд греческий и изготовлен в V веке». Боря: «Это сосуд финикийский и изготовлен в III веке». Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?
Введем следующие обозначения:
«Это сосуд греческий» — G;
«Это сосуд финикийский» — F;
«Сосуд изготовлен в III веке» — V3;
«Сосуд изготовлен в IV веке» — V4;
«Сосуд изготовлен в V веке» — V5.
Формализуем задачу, записав в данных обозначениях условия задачи.
Со слов учителя следует, что Алеша прав только в чем-то одном: или G = 1, или V5 = 1.
Таким образом, тождественно истинным будет высказывание: G¬V5 v¬GV5.=1
Аналогично, из слов Бори и учителя следует: F¬V3 v ¬FV3 = 1,
а из слов Гриши и учителя: ¬G¬V4 v GV4 = 1.
Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия можно записать так:
V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5 = 1,
F¬G v ¬FG = 1.
Итак, мы получили пять тождественно истинных высказываний. Их нужно логически перемножить. Результат должен быть также тождественно истинным высказыванием:
1 = (G¬V5 v ¬GV5) & (F¬V3 v ¬FV3) & (¬G¬V4 v GV4) & (F¬G v ¬FG) &(V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) =
(упростим: сначала перемножим первую и третью скобки и вторую и четвертую скобки)
=(G¬V5¬G¬V4˅¬GV5¬G¬V4 ˅ G¬V5GV4 ˅ ¬GV5 GV4)&( F¬V3F¬G˅¬FV3 F¬G˅ F¬V3 ¬FG ˅ ¬FV3¬FG) & (V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) =
учитывая, что, G¬G = 0, GG = G,¬ G¬G =¬ G, упростим выражения в первой и второй скобках:
=(¬GV5¬V4 ˅ ¬V5GV4 ) &( ¬FV3G ˅¬V3 F¬G)& (V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) =
(перемножим первую и вторую скобки и упростим полученное выражение)
(¬GV5¬V4 ¬FV3G˅¬V5GV4¬FV3G˅¬GV5¬V4 ¬V3 F¬G ˅ ¬V5GV4¬V3F¬G) & (V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ (¬V3¬V4V5)=(¬V5V4¬FV3G˅¬GV5¬V4 ¬V3 F) & (V3¬V4¬V5 ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5)= ¬GV5¬V4 ¬V3 F
¬GV5¬V4 ¬V3 F=1, если ¬G=1, V5=1, ¬V4 =1, ¬V3=1, F=1
Итак, сосуд финикийский и изготовлен в V веке.
Задача 4 «Поход в кино».
Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма.
Андрей сказал: «Я хочу посмотреть французский боевик».
Маша сказала: «Я не хочу смотреть французскую комедию».
Аня сказала: «Я хочу посмотреть американскую мелодраму».
Каждый из них слукавил в одном из двух пожеланий. На какой фильм пошли ребята?
Решение:
1. Выделим простые высказывания и запишем их через переменные:
А — «Французский фильм»
В — «Боевик»
С — «Комедия»
2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении:
а) «Французский боевик» ¬A&B˅A&¬B
б) «Американскую мелодраму» ¬¬A&¬B˅¬ А &¬¬В
в) «Нефранцузская комедия» ¬¬A&C˅¬A&¬C
3. Запишем произведение :
(¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)=1.
Упростим формулу: (¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)=
(¬A&B˅A&¬B) & (A&¬B˅¬ А&В)&( A&C˅¬A&¬C)=
=(¬A&B& A&¬B˅ A&¬B& A&¬B˅¬A&B &¬А&В˅ A&¬B&¬A&B)&( A&C˅¬A&¬C)=
=(A&¬B ˅¬A&B)&( A&C˅¬A&¬C)= A&¬B& A&C˅¬A&B& A&C˅ A&¬B&¬A&¬C˅¬A&B&¬A&¬C=
= ¬A&B&¬C˅ A&¬B&C =1
6. Составим таблицу истинности для выражения:
¬A&B&¬C˅ A&¬B&C:
| А | В | С | ¬A&B&¬C˅A&¬B&C | |
| 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | |
| 0 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | |
| 1 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 |
|
| 1 | 1 | 1 | 0 |
|
7. Найдем по таблице значения переменных, для которых F=1.
А)
| 0 | 1 | 0 | 1 |
| Б)
| |||
| 1 | 0 | 1 | 1 |
8. Проанализируем результат:
Результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что противоречит условию задачи.
Результат А) полностью удовлетворяет условию задачи и поэтому является верным решением.
Ответ: ребята выбрали американский боевик.
А
