Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Информатика / Конспекты / Разработка урока в 11 классе по теме "Решение логических задач"

Разработка урока в 11 классе по теме "Решение логических задач"

  • Информатика

Поделитесь материалом с коллегами:

Урок в 11 классе

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

Цели:

- показать применение алгебры логики при решении логических задач;

- научить видеть и уметь применять законы логики;

- развивать логическое мышление.


Ход урока


1.Организационный момент.


2.Введение новых знаний.


Алгебра высказываний находит широкое применение при решении логических задач.

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

Существуют разные способы формализации, как условий задачи, так и процесс её решения:

- алгебраический

- табличный

- графический


Каждый из этих способов обладает своими достоинствами.

При применении алгебраического метода наиболее трудным является перевод текста задачи на язык формул.

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

Метод графов применяется тогда, когда между объектами, о которых идёт речь в задачи, существует много связей. Граф позволяет наглядно представить эти связи и определить, какие из них не противоречат условиям задачи.


Разберем все три метода решения логических задач на примерах.


Задача 1.

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


1 комната

2 комната

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

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


Решение:

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

П1 – в первой комнате находится принцесса

¬П1 – в первой комнате находится тигр

П2 – во второй комнате находится принцесса

¬П2 – во второй комнате находится тигр


А=П1˅П2

В=¬П1


(А˄В)˅(¬A˄¬B)=1


(А˄В)˅(¬A˄¬B)=((П1˅П2)˄¬П1)˅(¬(П1˅П2)˄¬¬П1)=(П1˄¬П1˅П2˄¬П1)˅(¬П1˄¬П2˄П1)=(0˅П2˄¬П1)˅(П1˄¬П1˄¬П2)=(0˅П2˄¬П1)˅(0˄П1)=П2˄¬П1


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


Задача 2.

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

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

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

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

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

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

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


В данной задачи рациональнее всего использовать табличный метод решения.


По условию задачи имеем:

Имя

Город

Минск

Витебск

Харьков

Иван

-

Х


Андрей

¬М¬Ф

-

¬Ф

Борис

¬М

Х



Если Андрей не живет в Витебске, то он не может преподавать химию по условию задачи и по условию задачи он не преподает физику. Следовательно. Он преподает математику. Но математику не может преподавать житель Минска. Таким образом, Андрей житель Харькова. Но тогда ни Иван, ни Борис в Харькове не живут.


Имя

Город

Минск

Витебск

Харьков

Иван

-

Х

-

Андрей

¬М¬Ф

-

¬Ф¬ХМ

Борис

¬М

Х

-


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


Имя

Город

Минск

Витебск

Харьков

Иван

-

Х

-

Андрей

¬М¬Ф

-

¬Ф¬ХМ

Борис

¬М

Х

-


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


Имя

Город

Минск

Витебск

Харьков

Иван

-

Х

-

Андрей

¬М¬Ф

-

¬Ф¬ХМ

Борис

¬МФ

Х

-


Ответ:

Андрей преподает математику и живет в Харькове;

Борис преподает физику и живет в Минске;

Иван преподает химию и живет в Витебске.


Задача 3.

На соревнованиях по легкой атлетике Андрей, Боря, Сережа и Володя заняли первые четыре места. Но когда девочки стали вспоминать, как распределились эти места между победителями, то мнения разделились:

Даша: Андрей был первым, а Володя вторым.

Галя: Андрей был вторым, а Борис – третьим.

Лена: Боря был четвертым, а Сережа – вторым.

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


В данной задачи применим метод графов.

Вершины графа – имена мальчиков и занятые ими места.

Ребра графа – высказывания девочек.


мнение Даши – красная линия

мнение Гали – синяя линия

мнение Лены – черная линия

hello_html_4d159a46.png







Ася сказала, что каждая девочка сделала только одно правильное заявление. Значит, надо оставить только по одной линии каждого цвета. Всего в графе должно остаться 3 линии разных цветов.

Предположим, что истинное высказывание обозначенное В-2, тогда на следует удалить из графа А-1 (Даша права только в одном из предположения), А-2, С-2 (только кто – то один может занять второе место)


C:\Users\rab\Desktop\Безымянный.jpg


В графе осталось по одной линии каждого цвета, а именно В-2, Б-3, Б-4. Но это невозможно, так как Борис не мог одновременно занять третье и четвертое место. Значит, предположение об истинности высказывания, обозначенного ребром В-2 было неверным.

Одно предположение Даши (В-2) неверно, значит верно её другое предположение (А-1). Следовательно ребро А-2 следует удалить, а из этого следует, что высказывание, обозначенное ребром Б-3, должно быть истинным. Тогда ребро Б-4 надо удалить. Отсюда следует, что С-2 надо оставить. В результате получим граф, который и даёт ответ задачи.


C:\Users\rab\Desktop\Безымянный.jpg


Ответ:

Первое место – Андрей

Второе место – Сережа

Третье место – Боря

Четвертое место – Володя



3.Закрепление.


Задача.

Три дочери писательницы Дорис Кей – Джуди, Айрис и Линда, тоже очень талантливы. Они приобрели известность в разных видах искусств – пении, балете и кино. Все они живут в разных городах, поэтому Дорис часто звонит им в Париж, Рим и Чикаго. Известно, что:

1). Джуди живет не в Париже, а Линда – не в Риме;

2). Парижанка не снимается в кино;

3). Та, что живет в Риме, певица;

4). Линда равнодушна к балету.

Где живет Айрис, и какова её профессия?


Решение:

Составим таблицу и отразим в ней условия 1 и 4, заполнив клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание:


Париж

Рим

Чикаго


Пение

Балет

Кино

0



Джуди







Айрис





0


Линда


0



Далее рассуждаем следующим образом. Так как Линда живет не в Риме, то, согласно условию 3, она не певица.


Париж

Рим

Чикаго


Пение

Балет

Кино

0



Джуди



0




Айрис



0


0


Линда

0

0

1


Согласно условию 2, парижанка не снимается в кино, следовательно, Линда, живет не в Париже. Но она живёт и не в Риме. Следовательно, Линда живёт в Чикаго. Так как Линда и Джуди живут не Париже, там живёт Айрис.

Париж

Рим

Чикаго


Пение

Балет

Кино

0



Джуди



0

1



Айрис



0

0

0

1

Линда

0

0

1


Джуди живёт в Риме, и согласно условию 3, является певицей. А так как Линда киноактриса, то Айрис балерина.

В результате постепенного заполнения получаем следующую таблицу.


Париж

Рим

Чикаго


Пение

Балет

Кино

0

1

0

Джуди

1

0

0

1

0

0

Айрис

0

1

0

0

0

1

Линда

0

0

1


Ответ: Айрис балерина, она живет в Париже.


4.Организация домашнего задания.


Решить логическую задачу.


Условие задачи:

В одном дворе живут четыре друга. Вадим и шофер старше Сергея; Николай и слесарь занимаются боксом; электрик — младший из друзей; по вечерам Антон и токарь играют в домино против Сергея и электрика. Определите профессию каждого из друзей.

Выберите курс повышения квалификации со скидкой 50%:

Краткое описание документа:

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

Автор
Дата добавления 08.02.2015
Раздел Информатика
Подраздел Конспекты
Просмотров681
Номер материала 372329
Получить свидетельство о публикации

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