Логические задачи и способы их решения

Конспект урока

Информатика, 10 класс.

Тема — Логические задачи и способы их решения

Цель:

— познакомить учащихся со способами решения логических задач.

Задачи:

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

Узнаем, научимся, сможем

На уроке мы узнаем:

• основные способы решения логических задач;

мы научимся:

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

мы сможем:

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

Перечень вопросов, рассматриваемых в теме: метод рассуждений, табличный метод, метод упрощения логических выражений.

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

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

http://lbz.ru/metodist/authors/informatika/3/eor10.php

http://kpolyakov.spb.ru/school/ege.htm

Ход урока

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

II. Актуализация знаний

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

На вопрос, какая завтра будет погода, синоптик ответил:

1. Если не будет ветра, то будет пасмурная погода без дождя;

2. Если будет дождь, то будет пасмурно и без ветра;

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

Так какая же погода будет завтра? Соберите отчет из предложенных элементов.

БУДЕТ ВЕТЕР

БУДЕТ ПАСМУРНО

И

ВЕТЕР НЕ БУДЕТ

не пасмурно

БУДЕТ ДОЖДЬ

ИЛИ

ДОЖДЯ НЕ БУДЕТ

III. Сообщение темы и целей урока

Теоретический материал для самостоятельного изучения

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

Метод рассуждений

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

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

— столяр живёт правее охотника;

— врач живёт левее охотника;

— скрипач живёт с краю;

— скрипач живёт рядом с врачом;

— Семён не скрипач и не живёт рядом со скрипачом;

— Иван живёт рядом с охотником;

— Василий живёт правее врача;

— Василий живёт через дом от Ивана.

Определим, кто где живёт.

Изобразим дома прямоугольниками и пронумеруем их:

Известно, что скрипач живёт с краю (3). Следовательно, он может жить в доме 1 или в доме 4.

Скрипач живёт рядом с врачом (4), т. е. врач может жить правее (дом 2) или левее (дом 3) скрипача.

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

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

Так как Семён не скрипач и не живёт рядом со скрипачом (5), то он может жить в доме 3 или в доме 4.

Так как Иван живёт рядом с охотником (6), то он может жить в доме 2 или 4.

Так как Василий живёт правее врача (7), то он может жить в доме 3 или 4.

По условию (8) Василий живет через дом от Ивана, значит, в доме 1 может жить только Геннадий, в доме 2 — Иван, в доме 4 — Василий, в доме 3 — Семён.

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

Задачи о рыцарях и лжецах — это такой класс логических задач, в которых фигурируют персонажи:

- рыцарь — человек, всегда говорящий правду;

- лжец — человек, всегда говорящий ложь;

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

Решение подобных задач сводится к перебору вариантов и исключению тех из них, которые противоречат условию.

Пример 2. Двое жителей острова А и В разговаривали между собой в саду. Проходивший мимо незнакомец спросил у А: «Вы рыцарь или лжец?». Тот ответил, но так неразборчиво, что незнакомец не смог ничего понять. Тогда незнакомец спросил у В: «Что сказал А?».

«А сказал, что он лжец», — ответил В. Может ли незнакомец доверять ответу В? Мог ли А сказать, что он лжец?

Если А — рыцарь, то он скажет правду и сообщит, что он рыцарь.

Если А — лжец, то он скроет правду и сообщит, что он рыцарь.

Это значит, что В, утверждающий, что «А сказал, что он лжец» заведомо лжёт; он – лжец.

Определить, кем является А, в данной ситуации невозможно.

Табличный метод

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

Пример 3. В летнем лагере в одной палатке жили Алёша, Боря, Витя и Гриша. Все они разного возраста, учатся в разных классах (с 7-го по 10-й) и занимаются в разных кружках: математическом, авиамодельном, шахматном и фотокружке. Выяснилось, что

— фотограф старше Гриши;

— Алеша старше Вити, а шахматист старше Алёши;

— в воскресенье Алёша с фотографом играли в теннис, а Гриша в то же время проиграл авиамоделисту в городки.

Определим, кто в каком кружке занимается.

В этой задаче речь идёт о высказывательной форме (предикате) вида «Ученик х занимается в кружке у». Требуется определить такие значения х и у, чтобы высказывательная форма превратилась в истинное высказывание.

Составим таблицу:

Рассмотрим условия (1)-(3) и сделаем выводы: Гриша — не фотограф (1); шахматист — не Алёша и не Витя (2); Алёша — не фотограф и не авиамоделист, Гриша — не фотограф и не авиамоделист (3). Отметим это в таблице:

Мы можем сделать вывод, что Алёша занимается математикой, а Гриша — шахматами:

Из того, что Гриша — шахматист и условий (1) и (2) можем расположить учеников по возрасту (в порядке возрастания): Витя — Алёша — Гриша — фотограф. Следовательно, Боря — фотограф.

Ответ: Витя (7 класс) занимается в авиамодельном кружке, Алёша (8 класс) — в математическом, Гриша (9 класс) — в шахматном, Боря (10 класс) — в фотокружке.

Использование таблиц истинности для решения логических задач

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

Одним из таких методов является построение таблицы истинности по условию задачи и её анализ. Для этого следует:

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

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

3. Построить таблицу истинности для полученных логических выражений.

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

5. Убедиться, что полученное решение удовлетворяет условиям задачи.

Пример 4. Три подразделения А, В, С торговой фирмы стремились получить по итогам года максимальную прибыль. Экономисты высказали следующие предположения:

1. Если А получит максимальную прибыль, то максимальную прибыль получат В и С.

2. А и С получат или не получат максимальную прибыль одновременно.

3. Необходимым условием получения максимальной прибыли подразделением С является получение максимальной прибыли подразделением В.

По завершении года оказалось, что одно из трёх предположений ложно, а остальные два истинны.

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

Рассмотрим элементарные высказывания:

А — «А получит максимальную прибыль»;

В — «В получит максимальную прибыль»;

С — «С получит максимальную прибыль».

Запишем на языке алгебры логики прогнозы, высказанные экономистами:

Составим таблицу истинности для F₁, F₂, F₃.

Вспомним, что из трёх прогнозов F₁, F₂, F₃ один оказался ложным, а два других — истинным. Эта ситуация соответствует четвёртой строке таблицы.

Ответ: максимальную прибыль получили подразделения В и С.

Метод упрощения логических выражений

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

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

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

3. Составить единое логическое выражение, учитывающее все требования задачи.

4. Используя законы алгебры логики, упростить полученное выражение и вычислить его значение.

5. Выбрать решение – набор логических переменных (элементарных высказываний), при котором построенное логическое выражение является истинным.

6. Убедиться, что полученное решение удовлетворяет условиям задачи.

Пример 5. На вопрос, кто из трёх учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

Обозначим через А, В, С простые высказывания:

А — «Первый ученик изучал логику»;

В — «Второй ученик изучал логику»;

С — «Третий ученик изучал логику».

Из условия задачи следует истинность высказывания:  .

Упростим получившееся высказывание:

Получившееся высказывание будет истинным только в случае, если С — истина, а А и В — ложь.

Ответ: логику изучал только третий ученик.

Алгебра логики

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

Логические уравнения

Есть четыре друга: Антон, Виктор, Андрей и Дмитрий. Относительно их умения играть в шахматы, справедливы следующие высказывания:

Андрей играет в шахматы.

Если Виктор не играет в шахматы, то играют Андрей и Дмитрий.

Если Антон или Виктор играет, то Андрей не играет.

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

Логические уравнения. Эквивалентные преобразования

Иванов, Петров, Сидоров стали свидетелями ограбления банка. Во время расследования Иванов сказал, что взломщики приехали на синей «Тойоте». Петров считает, что это был красный «BMW», а Сидоров утверждает, что это был «Форд-Фокус», но не синий. Выяснилось, что каждый из них назвал неправильно либо марку, либо цвет машины. На каком автомобиле приехали преступники? Укажите его цвет и марку.

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

На кольцевой трассе автогонок расположены 4 препятствия: болото, трамплин, крутой поворот, скользкая дорога. В судейском протоколе 4 этапа обозначены буквами А, Б, В, Г. Известно, что этап Б расположен между этапом А и «крутым поворотом». Этап В — это не «крутой поворот» и не «скользкая дорога». Он расположен между этапами «трамплин» и Г. Установите соответствие между обозначениями этапов и препятствиями.

скользкая дорога Б

трамплин В

крутой поворот А

болото Г

Высказывания в логических задачах

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

Метод рассуждений

Кто из учеников идёт на олимпиаду по физике, если известно следующее:

Если Миша идёт, то идёт Аня, но не идёт Маша.

Если Маша не идёт на олимпиаду, то идёт Аня, но не идёт Миша.

Если Аня идёт, то идёт Миша, но не идёт Маша.

Ответ: _______________________

Элементы комбинаторики

Три школьника — Миша, Коля и Сергей, оставшиеся в классе на перемене, были вызваны к директору по поводу разбитого в это время окна в кабинете. На вопрос директора о том, кто это сделал, мальчики ответили следующее:

Миша: «Я не разбивал окно, и Коля тоже».

Коля: «Миша не разбивал окно, это Сергей его разбил».

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

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

Кто разбил стекло?

Ответ: ______________________

VI Закрепление

Задача №1

Ирина любит мороженое с фруктами. В кафе предлагают:

а) пломбир с орехами;

б) пломбир с бананами;

в) пломбир с черникой;

г) шоколадное с черникой;

д) шоколадное с клубникой.

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

Какое мороженое и с какими фруктами любит Ирина?

Задача №2

Для полярной экспедиции из восьми претендентов А, B, C, D, E, F, G и H надо отобрать шесть специалистов: биолога, гидролога, синоптика, радиста, механика и врача. Обязанности биолога могут выполнять E и G, гидролога B и F, синоптика F и G, радиста C и D, механика C и H, врача А и D. Хотя некоторые претенденты владеют двумя специальностями, в экспедиции каждый может выполнять только одну обязанность. Кого и кем следует взять в экспедицию, если F не может ехать без В, D – без H и без С, С не может ехать одновременно с G, а А не может ехать вместе с В.

E – биолог, B – гидролог, С – радист, D – врач, F – синоптик, H – механик

VII. Итог урока

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

1. Определить размеры таблицы и начертить ее.

2. Заполнить названия столбцов и строк.

3. С помощью 0 и 1 отразить условие задачи.

4. Путем умозаключений найти решение.

- Какие операции алгебры логики вы встречали в задачах?

- Как вы думаете, нужно ли уметь решать такие задачи?

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

Решить задачу

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

(1) Фермер живет правее пчеловода.

(2) Рыбак живет правее фермера.

(3) Ветеринар живет рядом с рыбаком.

(4) Рыбак живет через дом от пчеловода.

(5) Алексей живет правее фермера.

(6) Виктор – не пчеловод.

(7) Егор живет рядом с рыбаком.

(8) Виктор живет правее Алексея.

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