Урок «Решение логических задач». Автор: Садриев Вячеслав Эдуардович, учитель информатики I кв. кат. МОУ «Лицей №145»

Урок «Решение логических задач» Садриев Вячеслав Эдуардович, учитель информатики I кв. кат. МОУ «Лицей №145»

1. Повторение и актуализация знаний

1. Вызвать двух учащихся. Одному необходимо написать таблицы истинности для операций дизъюнкция, импликация, и-не, другому – конъюнкция, или-не, эквивалентность

2. Диктант на определение формул законов логики для всей аудитории. По названию закона записать сами формулы:

а)      идемпотентность
б)      законы Моргана
в)      исключение третьего
г)       сложение по модулю 2
д)      непротиворечив
е)      склеивание
ж)    поглощение
з)       дистрибутивность
и)     импликация
к)      эквивалентность

3. Даны простые высказывания: А: “Петя умеет плавать”, В: “Сергей умеет прыгать”, С: “Алеша умеет стрелять”. Даны формулы сложных высказываний, составленные из этих простых. По очереди вызвать с места учащихся и попросить прочитать их, используя смысл каждого простого высказывания:

1. А+В·  2.· В·  3. А· В·  4. А · · С 5. А· ·  6.

4. Дано высказывание: “Иванов является членом сборной команды “Алгоритм”. Какое из следующих высказываний есть логическим отрицанием данного?

 а) Не Иванов является членом сборной команды “Алгоритм”.
 б) Иванов является членом сборной команды не “Алгоритм”.
 в) Иванов не является членом сборной команды “Алгоритм”.
 г) Неверно, что Иванов является членом сборной команды “Алгоритм” 

1. Новый материал

1. Способы решения логических задач:

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

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

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.
— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

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

Высказывание  истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

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

Рассмотрим способ решения сразу на конкретной задаче

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

1. Смит самый высокий;
2. играющий на скрипке меньше ростом играющего на флейте;
3. играющие на скрипке и флейте и Браун любят пиццу;
4. когда между альтистом и трубачом возникает ссора, Смит мирит их;
5. Браун не умеет играть ни на трубе, ни на гобое.

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

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

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

Из условия 4 следует, что Смит не играет ни на альте, ни на трубе, а из условий 3 и 5, что Браун не умеет играть на скрипке, флейте, трубе и гобое. Следовательно, инструменты Брауна — альт и кларнет. Занесем это в таблицу, а оставшиеся клетки столбцов "альт" и "кларнет" заполним нулями:

Из таблицы видно, что на трубе может играть только Вессон. 

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

Из таблицы видно, что играть на флейте и на гобое может только Смит.

Ответ: Браун играет на альте и кларнете, Смит — на флейте и гобое, Вессон — на скрипке и трубе.

3. Решение логических задач с помощью рассуждений

Пример 7. В поездке пятеро друзей — Антон, Борис, Вадим, Дима и Гриша, знакомились с попутчицей. Они предложили ей отгадать их фамилии, причём каждый из них высказал одно истинное и одно ложное утверждение:

Дима сказал: "Моя фамилия — Мишин, а фамилия Бориса — Хохлов". Антон сказал: "Мишин — это моя фамилия, а фамилия Вадима — Белкин". Борис сказал: "Фамилия Вадима — Тихонов, а моя фамилия — Мишин". Вадим сказал: "Моя фамилия — Белкин, а фамилия Гриши — Чехов". Гриша сказал: "Да, моя фамилия Чехов, а фамилия Антона — Тихонов".

Какую фамилию носит каждый из друзей?

Решение. Обозначим высказывательную форму "юноша по имени А носит фамилию Б" как АБ, где буквы А и Б соответствуют начальным буквам имени и фамилии.

Зафиксируем высказывания каждого из друзей:

1. ДМ и   БХ;
2. АМ и   ВБ;
3. ВТ и   БМ;
4. ВБ и   ГЧ;
5. ГЧ и   АТ.

Допустим сначала, что истинно ДМ. Но, если истинно ДМ, то у Антона и у Бориса должны быть другие фамилии, значит АМ и БМ ложно. Но если АМ и БМ ложны, то должны быть истинны ВБ и ВТ, но ВБ и ВТ одновременно истинными быть не могут.

Значит остается другой случай: истинно БХ. Этот случай приводит к цепочке умозаключений: БХ истинно БМ ложно ВТ истинно АТ ложно ГЧ истинно ВБ ложно АМ истинно.

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

Решить задачи наиболее удобным способом

1. Три одноклассника — Влад, Тимур и Юра, встретились спустя 10 лет после окончания школы. Выяснилось, что один из них стал врачом, другой физиком, а третий юристом. Один полюбил туризм, другой бег, страсть третьего — регби. Юра сказал, что на туризм ему не хватает времени, хотя его сестра — единственный врач в семье, заядлый турист. Врач сказал, что он разделяет увлечение коллеги. Забавно, но у двоих из друзей в названиях их профессий и увлечений не встречается ни одна буква их имен. Определите, кто чем любит заниматься в свободное время и у кого какая профессия

2. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: "Чей именно проект был принят?", министры дали такие ответы: Россия — "Проект не наш, проект не США"; США — "Проект не России, проект Китая"; Китай — "Проект не наш, проект России". Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду. Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

IV.  Домашнее задание

Решить задачи наиболее удобным способом

1. В спортивных соревнованиях принимали участие пять команд: "Вымпел", "Метеор", "Нептун", "Старт" и "Чайка". Об их итогах соревнования имеется пять высказываний:
1). Второе место занял "Вымпел", a "Cтарт" оказался на третьем.
2). Хорошо выступала команда "Нептун", она стала победителем, а "Чайка" вышла на второе место.
3). Да нет же, "Чайка" заняла только третье место, а "Нептун"- был последним.
4). Первое место по праву завоевал "Cтарт", а "Метеор" был 4-м.
5). Да, "Метеор", действительно, был четвертым, а "Вымпел" был 2-м.

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

2. Обсуждался вопрос о включении в состав сборной команды пяти молодых игроков: Асеева, Валеева, Сватеева, Деева и Евтеева.

Выбор обусловлен следующими условиями:
1) В команду необходимо включить не менее чем одного из трех игроков: Асеева, Валеева, Евтеева, но не более чем одного из трех игроков: Асеева, Сватеева, Деева.
2) Сватеева можно включить в сборную без Валеева тогда и только тогда, когда Асеев будет включен, а Деев не будет включен.
3) Если Валеев будет включен в сборную, а Сватеев не будет включен, то сборную нужно пополнять и Деевым, и Евтеевым.
4) Если Асеев не будет включен в команду, то нужно в нее включить и Сватеева, и Евтеева.
Кого из игроков можно включить в сборную команду?