Методическая разработка урока тема: «Решение логических задач»

Тема: «Решение логических задач»

Предмет: Информатика и ИКТ

Время занятия: 2 академических часа

Вид кейса: обучающий

Тип кейса: аналитический

Цель: сформировать умения обучающихся к работе со специальным набором учебно-методических материалов (кейсом) по решению логических задач и максимально активизировать каждого обучающегося в самостоятельную работу по решению кейса.

Задачи: - обобщить знания о преобразовании логических выражений;

- развивать инициативу, любознательность, умственную активность;

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

Оборудование: набор учебно-методических материалов (кейс) для самостоятельной работы, компьютеры подключенные к интернету и локальной сети, мультимедиа проектор, интерактивная доска.

На уроке преподаватель сообщает тему урока и дает комментарии об объеме работ, формулирование вместе с учащимися цели и задач урока, ознакомление с критериями оценок и прогнозируемого результата, объяснение порядка работы с кейсом.

Затем идет проверка домашнего задания (краткое изложение обучающимися домашнего задания – творческая практическая работа кейса и их обсуждение).

ЗАДАНИЕ ПОДГРУППАМ: Три школьника, Миша (М), Коля (К) и Сергей (С), остававшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:

Миша: «Я не бил окно, и Коля тоже…»

Коля: «Миша не разбивал окно, это Сергей разбил футбольным мячом!»

Сергей: «Я не делал этого, стекло разбил Миша».

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

РАБОТА С КЕЙСОМ:

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

Далее идет ознакомление обучающихся с заданием кейса в бумажном и электронном виде (в школьных компьютерах через локальную сеть).

Затем идет распределение обучающихся на подгруппы (3-5 человек) и организуется работа в подгруппах.

Первый этап дискуссии - организация дискуссии в подгруппах:

- обсуждение решения проблемы по заданию кейса, выявление и формулировка проблемы, поиск аргументов и решений (обучающийся, познакомившись с заданием, самостоятельно анализирует ситуацию, представляют свои решения в дискуссии с другими членами подгруппы);

- выбор лучшего решения в рамках подгруппы и организация презентаций решений в подгруппах.

Второй этап дискуссии - организация общей дискуссии в классе для принятия окончательных решений:

- выступления капитанов подгрупп, каждая группа предлагает свою версию выполненного задания (публичная, устная презентация решений);

- участие в обсуждении обучающихся других подгрупп;

- участие в обсуждении преподавателя.

Итоговая стадия работы над кейсом - заключительная презентация результатов решения задания (сравнение нескольких вариантов решения). Затем идет обобщающее выступление преподавателя - анализ ситуаций и оценивание работы каждой подгруппы преподавателем.

СОДЕРЖАНИЕ КЕЙСА:

Решение логических задач

Что нужно знать:

• таблицы истинности логических операций «И», «ИЛИ», «НЕ», «ЕСЛИ…, ТО…», «ТОГДА И ТОЛЬКО ТОГДА»

• логическое произведение A∙B∙C∙… равно 1 (выражение истинно) только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0);

• логическая сумма A+B+C+… равна 0 (выражение ложно) только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1);

• правила преобразования логических выражений.

Законы алгебры логики

Задача 1:

Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: «Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша». Саша сказал: «Это был мой первый прогул этого предмета». Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». (Пример: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ)

Решение (вариант 1, метод рассуждений):

1. во-первых, есть «точная» информация, которая не подвергается сомнению:

все трое прогуляли урок астрономии в первый раз

1. запишем высказывания мальчиков:

Коля: 1. Я всегда прогуливаю астрономию. 2. Саша врет.

Саша: 1. Я в первый раз прогулял астрономию.

Миша: 1. Коля говорит правду.

1. известно, что один из них все время лжет, второй ­– говорит правду, а третий говорит правду через раз (то есть, из двух его высказываний одно истинно, а второе – ложно; если у нас есть только одно высказывание «полу-лжеца», оно может быть как истинным, так и ложным)

2. сопоставив первое высказывание Коли и высказывание Саши с «точной» информацией, сразу определяем, то тут Коля соврал, а Саша сказал правду; это значит, что второе высказывание Коли – тоже неверно, поэтому мальчик Коля всегда лжет

3. тогда один из оставшихся, Саша или Миша, говорит правду всегда, а второй – через раз

4. Мишино высказывание неверно, поскольку мы уже определили, что Коля лжет; это значит, что Миша не всегда говорит правду, он – «полу-лжец»

5. тогда получается, что Саша всегда правдив, и действительно, его высказывание верно

6. таким образом, верный ответ – СКМ (Саша – правдив, Коля – лжец, Миша – «полу-лжец» ).

Задача 2.

Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Встретив однажды всех троих в коридоре, директор решил поговорить с мальчиками. Коля сказал: «Саша всегда лжет». Саша сказал: «Коля прав». Директору стало все понятно. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». Например: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ.

Решение (вариант 1, метод рассуждений):

1. в отличие от предыдущей задачи, здесь нет точной информации

2. у нас всего два высказывания мальчиков:

Коля: Саша всегда лжет

Саша: Коля прав

1. в отличие от предыдущей задачи, второе высказывание связано с первым: Сашино утверждение относится к данному конкретному высказыванию Коли, а не к честности Коли вообще

2. в такой ситуации нужно предположить, что истинно одно из высказываний и проверить, не приводит ли это к противоречию

3. предположим, что Коля сказал правду; тогда получается, что Саша (который всегда лжет) солгал и на этот раз; однако если Саша солгал, то получается, что Коля сказал неправду, то есть, мы пришли к противоречию, и Коля в самом деле солгал

4. если Коля солгал, то получается, что Саша тоже солгал, то есть, оба мальчика сказали неправду; отсюда следует, что один из них – лжец, а второй «полу-лжец», тогда как Миша (ничего не сказавший) говорит всегда правду

5. остается определить, кто из двоих (Коля или Саша) лжец, а кто – «полу-лжец»

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

7. мы уже выяснили, что Коля солгал, то есть Саша не всегда лжет, он – «полу-лжец»; тогда сразу получается, что Коля – лжец

8. таким образом, верный ответ – МКС (Миша – правдив, Коля – лжец, Саша – «полу-лжец»).

Задача 3.

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

– Кто это сделал? – спросила мама.

– Коля не бил по мячу, – сказал Саша. – Это сделал Ваня.

Ваня ответил: – Разбил Коля, Саша не играл в футбол дома.

– Так я и знала, что вы друг на дружку сваливать будете, рассердилась мама. Ну, а ты что скажешь? – спросила она Колю.

– Не сердись, мамочка! Я знаю, что Ваня не мог этого сделать. А я сегодня еще не сделал уроки, – сказал Коля.

Оказалось, что один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду. Кто разбил вазу?

Решение (вариант 1, метод рассуждений):

1. запишем высказывания трех мальчиков в краткой форме:

Саша: 1. это не Коля 2. это Ваня

Ваня: 1. это Коля 2. это не Саша

Коля: 1. это не Ваня

обратите внимание, что у Коли всего одно высказывание, которое «относится к делу»; то, что он сделал или не сделал уроки, никак не проясняет ситуацию с разбитой вазой

1. итак, двое мальчиков сказали правду;

- это не могут быть Саша и Ваня, потому что их первые высказывания противоречат одно другому

- это не могут быть Саша и Коля, поскольку высказывание Коли противоречит второму высказыванию Саши

- поэтому правду сказали Ваня и Коля, а Саша – соврал

1. таким образом, вазу разбил Коля

Решение (вариант 2, преобразование логических выражений):

1. применим к этой задаче формальный аппарат математической логики; введем высказывания:

С: вазу разбил Саша

В: вазу разбил Ваня

К: вазу разбил Коля

1. запишем с помощью этих обозначений утверждения мальчиков:

Саша: 1. 2.

Ваня: 1. 2.

Коля: 1.

1. читаем условие: «один из мальчиков оба раза солгал, а двое в каждом из своих заявлений говорили правду»;

2. как записать «Саша два раза солгал»? в этом случае оба его утверждения неверны, поэтому и , что равносильно

3. как записать «Саша два раза сказал правду»? в этом случае оба его утверждения неверны, поэтому и , что равносильно

4. если Коля солгал, а Саша и Ваня сказали правду, то

и и

заменив «И» на умножение, получаем ; учитывая, что , получаем в левой части равенства ноль; так как в правой части – единица, этого не может быть (равенство ложно при любых значениях )

1. если Ваня солгал, а Саша и Коля сказали правду, то

и и

заменив «И» на умножение, получаем ; учитывая, что , получаем, что это равенство ложно при любых значениях (этого не может быть)

1. остается последний возможный вариант: если Саша оба раза солгал, а Ваня и Коля сказали правду, то

и и

заменив «И» на умножение, получаем ; упростив это выражение с учетом равенств и , получим ; то есть, при этом предположении вазу разбил Коля, а не Ваня и не Саша;

1. таким образом, вазу разбил Коля

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

Решение (вариант 3, метод подбора):

1. запишем высказывания трех мальчиков в краткой форме:

Саша: 1. Коля не разбивал 2. Ваня разбил

Ваня: 1. Коля разбил 2. Саша не разбивал

Коля: 1. Ваня не разбивал

1. оформим эти данные в виде таблицы, где в строках записаны высказывания мальчиков, а в столбцах – информация, которая в них содержится:

	Саша разбил	Ваня разбил	Коля разбил
Саша		1	0
Ваня	0		1
Коля		0

Например, из первой строки следует, что Саша сказал, что вазу разбил Ваня, а Коля не разбивал. Пустые клетки означают, что информации нет: например, Коля ничего не говорил о Саше (последняя строка).

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

2. мы знаем, что один мальчик соврал, а двое остальных сказали оба раза правду; по таблице видим, что соврал Саша или Ваня, потому что в их строчках единицы стоят в разных столбцах

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

4. инверсия первой строчки дает такое решение (во последнем столбце все единицы, в остальных – все нули):

   	Саша разбил	Ваня разбил	Коля разбил
   Саша		1 0	0 1
   Ваня	0		1
   Коля		0

5. таким образом, вазу разбил Коля

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

Задача 4.

На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Василий, Семен, Геннадий и Иван. Известно, что все они имеют разные профессии: скрипач, столяр, охотник и врач. Известно, что

(1) Столяр живет правее охотника.

(2) Врач живет левее охотника.

(3) Скрипач живет с краю.

(4) Скрипач живет рядом с врачом.

(5) Семен не скрипач и не живет рядом со скрипачом.

(6) Иван живет рядом с охотником.

(7) Василий живет правее врача.

(8) Василий живет через дом от Ивана.

Определите, кто где живет, и запишите начальные буквы имен жильцов всех домов слева направо. Например, если бы в домах жили (слева направо) Кирилл, Олег, Мефодий и Пафнутий, ответ был бы КОМП.

Решение (вариант 1, метод рассуждений с таблицами):

1. из условий (1) и (2) следует, что охотник живет не с краю, потому что справа от него живет столяр, а слева – врач;

2. скрипач по условию (3) живет с краю, он может жить как слева, так и справа от них:

   скрипач?	врач	охотник	столяр	скрипач?

3. по условию (4) скрипач живет рядом с врачом, поэтому он занимает крайний дом слева:

   1	2	3	4
   скрипач	врач	охотник	столяр

4. профессии жильцов определили, остается разобраться с именами

5. из условия (5) «Семен не скрипач и не живет рядом со скрипачом» следует, что Семен – охотник или столяр:

   1	2	3	4
   скрипач	врач	охотник	столяр
   		Семен?	Семен?

6. из условия (6) «Иван живет рядом с охотником» следует, что он – врач или столяр:

   1	2	3	4
   скрипач	врач	охотник	столяр
   		Семен?	Семен?
   	Иван?		Иван?

7. из условия (7) «Василий живет правее врача» определяем, что Василий – охотник или столяр

   1	2	3	4
   скрипач	врач	охотник	столяр
   		Семен?	Семен?
   	Иван?		Иван?
   		Василий?	Василий?

8. из условия (8) «Василий живет через дом от Ивана» находим, что Иван – врач, а Василий –столяр:

   1	2	3	4
   скрипач	врач	охотник	столяр
   	Иван	Семен?	Василий

9. тогда сразу получается, что Семен – охотник, а Геннадий должен занять оставшееся свободное место, он ­– скрипач:

   1	2	3	4
   скрипач	врач	охотник	столяр
   Геннадий	Иван	Семен	Василий

10. таким образом, ответ ГИСВ

Решение (вариант 2, метод рассуждений с таблицами):

1. пронумеруем дома слева направо (от 1 до 4);

2. находим наиболее точное условие: это условие (3) ­«Скрипач живет с краю»; таким образом, скрипач может жить в доме 1 или в доме 4

   1	2	3	4
   скрипач?	?	?	скрипач?

3. по условию (4) скрипач живет рядом с врачом, но врач живет левее охотника (условие (2)), поэтому скрипач не может жить в доме (4), так как тогда получается врач, живущий с ним рядом, живет правее охотника, что противоречит условию (2); таким образом, скрипач живет в доме 1, а врач – рядом с ним

   1	2	3	4
   скрипач	врач	?	?

4. из условий (1) и (2) следует, что в домах 3 и 4 живут соответственно охотник и столяр

   1	2	3	4
   скрипач	врач	охотник	столяр

5. далее можно рассуждать так же, как и в предыдущем варианте решения

6. таким образом, ответ ГИСВ

Задача 5.

Восемь школьников оставались в классе на перемене, и один из них разбил окно. На вопрос директора, кто это сделал, были получены следующие ответы:

Егор: «Разбил Андрей»!

Света: «Вика разбила»!

Оля: «Разбила Света».

Миша: «Это кто-то с улицы»!

Надя: «Да, Оля права».

Коля: «Это либо Вика, либо Света»!

Андрей: «Ни Вика, ни Света этого не делали»!

Вика: «Андрей не бил»!

Кто разбил окно, если известно, что из этих высказываний истинно ровно три. Ответ запишите в виде первой буквы имени.

Решение (табличный метод):

1. заметим, что по условию высказывание Миши («Это кто-то с улицы») заведомо ложно, поскольку окно разбил кто-то из перечисленных детей, поэтому его можно вообще не учитывать

2. проще всего решить эту задачу с помощью таблицы; в первом столбце запишем все высказывания, а в остальных будем отмечать, истинно высказывание или ложно (1 или 0), если окно разбил ученик, имя которого записано в заголовке столбца

3. например, если предположить что окно разбил Егор, получается так:

	Егор
Разбил Андрей	0
Разбила Вика	0
Разбила Света	0
Оля права = Разбила Света	0
Разбила Вика или Света	0
Это не Вика и не Света	1
Это не Андрей	1

видим, что истинны только два высказывания, а не три (как нужно по условию); следовательно, это не Егор

1. строим таблицу для случаев, предполагая, что окно разбила Света, затем – Оля и т.д.:

   	Егор	Света	Оля	Миша	Надя	Коля	Андрей	Вика
   Разбил Андрей	0	0	0	0	0	0	1	0
   Разбила Вика	0	0	0	0	0	0	0	1
   Разбила Света	0	1	0	0	0	0	0	0
   Оля права = Разбила Света	0	1	0	0	0	0	0	0
   Разбила Вика или Света	0	1	0	0	0	0	0	1
   Это не Вика и не Света	1	0	1	1	1	1	1	0
   Это не Андрей	1	1	1	1	1	1	0	1

2. только в последнем столбце ровно три единицы (три высказывания истинны), поэтому окно разбила Вика

3. таким образом, ответ – В.

Задача 6.

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

(1) Ни Дима, ни Юра не знают японского

(2) Переводчик со шведского старше переводчика с немецкого

(3) Переводчик с китайского, переводчик с французского и Саша родом из одного города

(4) Переводчик с греческого, переводчик с немецкого и Юра учились втроем в одном
институте

(5) Дима – самый молодой из всех троих, и он не знает греческого

(6) Юра знает два европейских языка

В ответе запишите первую букву имени переводчика со шведского языка и, через запятую, первую букву имени переводчика с китайского языка.

Решение (табличный метод):

1. составим таблицу, где каждая строка соответствует переводчику, а столбец – языку

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима
   Юра
   Саша

2. знание языка будем отмечать в таблице единицей, а незнание – нулем

3. по условию каждый переводчик знает ровно 2 языка, поэтому в каждой строке должно быть две единицы;

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

5. из (1) следует, что японский знает Саша

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима			0
   Юра			0
   Саша			1

6. из (2) и (5) следует, что Дима не знает ни шведского, ни греческого:

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима		0	0			0
   Юра			0
   Саша			1

7. из (3) следует, что Саша не знает ни китайского, ни французского:

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима		0	0			0
   Юра			0
   Саша			1	0	0

8. из (4) следует, что Юра не знает ни греческого, ни немецкого; отсюда сразу следует, что греческий знает Саша; поскольку он знает всего два языка, немецкий и шведский он не знает:

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима		0	0			0
   Юра	0		0			0
   Саша	0	0	1	0	0	1

9. далее сразу получаем, что Дима знает немецкий, а Юра – шведский:

   	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
   Дима	1	0	0			0
   Юра	0	1	0			0
   Саша	0	0	1	0	0	1

10. из (6) находим, что второй (европейский!) язык Юры – французский; тогда Диме остается китайский:

    	Немецкий	Шведский	Японский	Китайский	Французский	Греческий
    Дима	1	0	0	1	0	0
    Юра	0	1	0	0	1	0
    Саша	0	0	1	0	0	1

11. таким образом, ответ Ю,Д

Творческая практическая работа

Ф.И._________________________ группа________

Задание 1. Самостоятельно изучите задания с решениями в лекции по теме «Решение логических задач».

Задание 2. Составьте свой пример аналогично заданным в лекции и запишите его решение (одним способом).

Задание 3. Решите задачи:

1. Три ученика, Саша, Коля и Вова, прогуляли информатику. Когда их спросили, кому пришла в голову эта идея, они ответили следующее:

Саша: «Я никогда не призывал к прогулу, это была идея Коли».

Коля: «Я никогда не предложил бы это первым, во всем виноват Вова».

Вова: «Эта идея пришла в голову Коле. Я просто пошел за компанию».

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

1. В симфонический оркестр приняли на работу трех музыкантов – Брауна, Смита и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. Известно, что:

(1) Смит – самый высокий

(2) играющий на скрипке меньше ростом играющего на флейте

(3) играющие на скрипке и флейте и Браун любят пиццу

(4) когда между альтистом и трубачем возникает ссора, Смит мирит их

(5) Браун не умеет играть ни на трубе, ни на гобое.

Выясните, на каких инструментах играет каждый из музыкантов, если каждый владеет двумя инструментами.

Задание 4. Сохраните практическую работу под Вашей фамилией и отправьте учителю по адресу [email protected]