Цикл дополнительных занятий «Решение логических задач» (7–11 класс)

Это цикл занятий, разработанных мною для работы с учащимися, которым интересны мои предметы – математика и информатика, и которым для понимания некоторых тем нужно больше времени и объяснений. Задачи обычные, брала из учебников и научно-популярных книг, а вот дальнейшее наше взаимодействие считаю важной «изюминкой». После разбора каждого метода решения учащиеся составляли дома свою задачу на логику, записывали её решение, и на следующем занятии решали задачки друг друга, оценивая и сравнивая рассуждения товарищей. В итоге получился цикл из пяти получасовых занятий, который предлагаю вашему вниманию.

 

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

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

 

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

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

Пример 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. Каждый из 10 гномов либо всегда говорит правду, либо всегда лжет. Известно, что каждый из них любит ровно один сорт мороженого: сливочное, шоколадное или фруктовое. Сначала Белоснежка попросила поднять руки тех, кто любит сливочное мороженое, и все подняли руки, потом тех, кто любит шоколадное мороженое – и половина гномов подняли руки, потом тех, кто любит фруктовое мороженое – и руку поднял только один гном. Сколько среди гномов правдивых?(7 баллов)

Решение:Из условия задачи ясно, что правдивые гномы могут любить только сливочное мороженое, а лживые — только шоколадное или фруктовое. Именно поэтому все гномы сказали, что любят сливочное. Заполним табличку — отметим, что должны говорить правдивые и лживые гномы, в зависимости от того, какой сорт им нравится. Правдивый — любит только сливочное, признает это, а про остальные сорта говорит, что не любит. Лживый гном, который любит шоколадное мороженое, скажет «нет» в ответ на второй вопрос, и «да» — в ответ на третий. Если же лживый гном любит фруктовое, то он ответит «да» на вопрос про шоколадное, и «нет» — про фруктовое.

Из третьего столбца мы видим, что в любви к фруктовому мог признаться только лжец, который любит шоколадное мороженое. Причем такой среди гномов — всего один. А из второго столбца мы видим, что отрицают любовь к шоколадному мороженому все правдивые гномы и лжецы, которые любят шоколад. Но таких лжецов, как мы уже узнали, всего один. Поэтому на второй вопрос ответили «нет» все правдивые гномы и один лжец. То есть правдивых гномов — половина минус один.

Ответ: 4 (это задача из нашей муниципальной олимпиады по математике, школьный этап).

 

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

 

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

Составим таблицу истинности для F1, F2, F3.

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

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Пример 6

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

 

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

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

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

Так какая же погода будет завтра? 

 

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

       A – «Ветра нет»
       B – «Пасмурно»
   С – «Дождь»

   2.          Запишем логические функции (сложные высказывания) через введенные переменные:

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

     A → B ˄¬C  
     Если будет дождь, то будет пасмурно и без ветра:
     С → B ˄ A 
     Если будет пасмурная погода, то будет дождь и не будет ветра
     B → C & A
     в) Запишем произведение указанных функций:
    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;

Ответ: погода будет ясная, без дождя, но ветреная.

 

Учитель математики и информатики Олейникова Галина Васильевна.

 

Литература:

 

Многоцветная логика. 175 логических задач
Дьердь Бизам, Янош Герцег, 1978

Л. М. Лихтарников, Т.Г. Сукачева Математическая Логика. Курс лекций. 3адачник-практикум и решения. Серия Учебники для вузов. - Санкт-Петербург, Издательство "Лань", 1999. - 288 с.