Задачи алгебра логики 10 класс способы решения

Решение логических задач в 10-м профильном классе

Урок №1

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

Задачи урока:

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

Дополнительные материалы: задачник (приложение 1), презентации (приложение 2, приложение 3).

Ход урока

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

II. Проверка домашнего задания. Повторение (5мин).

Примечание: для повторения используется презентация (приложение 2).

III. Изучение нового материала (20мин).

Примечание: объяснение материала проходит с помощью презентации (приложение 3).

Давным-давно в одной из восточных стран был знаменитый оракул. В отличие от остальных оракулов, его устами вещало не одно божество, а целых три: бог Правды, бог Лжи и бог Дипломатии. Эти божества изображались совершенно одинаковыми фигурами, расположенными в ряд за алтарем, перед которым преклоняли колени люди, ищущие совета. Боги всегда охотно отвечали на вопросы. Но так как они были похожи друг на друга, никто не мог определить, то ли отвечает бог Правды, которому надо верить, то ли бог Лжи, который говорит всегда неправду, то ли бог Дипломатии, который может либо солгать, либо сказать правду. Такое положение было на руку жрецам, ибо любой ответ оракула можно было толковать как угодно.

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

Смельчак вошел в храм и спросил бога, стоящего слева:

– Кто стоит рядом с тобой?

– Бог Правды, – ответил тот.

Тогда смельчак спросил бога, стоящего в центре:

– Бог Дипломатии, – был ответ.

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

– Кто стоит рядом с тобой?

– Бог Лжи, – ответил бог.

– Теперь все понятно, – довольно сказал смельчак.

Что же он понял из ответов богов? (Вопрос к классу).

Эта задача принадлежит к классу логических задач, разнообразие которых очень велико. Способов их решения тоже немало. Сегодня на уроке мы с вами научимся решать логические задачи – станем смельчаками или Шерлоками Холмсами, которые могут распознавать лжецов, преступников и распутывать сложные ситуации.

Наибольшее распространение получили следующие четыре способа решения логических задач:

• с помощью рассуждений;
• средствами алгебры логики;
• табличный способ;
• с помощью графов.

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

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

Этим способом обычно решают несложные логические задачи.

Задача №1. Три девочки – Роза, Маргарита и Анюта представили на конкурсе корзины из выращенных ими роз, маргариток и анютиных глазок. Девочка, вырастившая маргаритки, обратила внимание Розы на то, что ни у одной из девочек имя не совпадает с названием любимых цветов. Какие цветы вырастила каждая из девочек?

Решение.

1. Девочка, вырастившая маргаритки, обратила внимание на то, что ни у одной из девочек имя не совпадает с названием выращенных цветов, поэтому можно записать следующие условия:
   а) Аня вырастила не анютины глазки.
   б) Маргарита вырастила не маргаритки.
   в) Роза вырастила не розы.
2. Из диалога Розы и девочки, вырастившей маргаритки, следует, что Роза вырастила не маргаритки. Поэтому она могла вырастить либо розы, либо анютины глазки. Учитывая условие в), получаем, что Роза вырастила анютины глазки.
3. В связи с условием б) и предыдущим выводом очевидно, что Маргарита вырастила розы.
4. Следовательно, Аня вырастила маргаритки.

Ответ. Роза вырастила анютины глазки, Маргарита – розы, Аня – маргаритки.

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

Решение.

1. Имеются три утверждения:
   а) Вадим изучает китайский;
   б) Сергей не изучает китайский;
   в) Михаил не изучает арабский.
2. Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.
3. Если верно второе утверждение, то первое и третье должны быть ложны. При этом получается, что никто не изучает китайский. Это противоречит условию, поэтому второе утверждение тоже ложно.
4. Остается считать верным третье утверждение, а первое и второе – ложными. Следовательно, Вадим не изучает китайский, изучает китайский Сергей.
5. Так как Михаил не изучает арабский, то он может изучать лишь японский. Тогда Вадим изучает арабский.

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

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

Обычно используется следующая схема решения:

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

Задача №3. Виновник ночного дорожно-транспортного происшествия скрылся с места аварии. Первый из опрошенных свидетелей сказал работникам ГИБДД, что это были «Жигули», первая цифра номера машины – единица. Второй свидетель сказал, что машина была марки «Москвич», а номер начинался с семерки. Третий свидетель заявил, что машина была иностранная, номер начинался не с единицы. При дальнейшем расследовании выяснилось, что каждый из свидетелей правильно указал либо только марку машины, либо только первую цифру номера. Какой марки была машина и с какой цифры начинался номер?

Решение.

Введем обозначения для логических высказываний: Ж – это «Жигули»; М – это «Москвич»; И – это иностранная машина; Е – номер машины начинается с единицы; С – номер машины начинается с семерки.

Запишем высказывания свидетелей в наших обозначениях:

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

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

Для решения задачи нужно определить, при каких значениях логических переменных Ж, М, И, Е, С это высказывание истинно.

Упростим выражение, учитывая те обстоятельства, что машина не может быть одновременно и марки «Жигули», и марки «Москвич», и иностранного происхождения, а также то, что номер машины не может одновременно начинаться с единицы и с семерки:

При выводе мы также использовали закон противоречия и закон исключения констант.Высказывание истинно только при Ж=1, М=0, И=0, Е=0, С=1. Таким образом, мы установили, что виновником дорожно-транспортного происшествия была машина марки «Жигули», номер которой начинался с цифры семь.

Ответ. Машина марки «Жигули», номер которой начинался с цифры семь.

Задача №4. В клуб служебного собаководства на очередную тренировку пришли со своими собаками Антон, Борис, Петр, Виктор и Олег. Желая подшутить над новым инструктором, на вопрос: «Кто же хозяин каждой из собак?» каждый юноша дал один правильный и один неправильный ответ. Антон сказал: «Моя собака – Рекс, а собака Петра – Лайма». Борис сказал: «Рекс – моя собака, а собака Виктора – Джек». Петр сказал: «Собака Виктора – Зевс, а моя собака – Рекс». Виктор сказал: «Моя собака – Джек, а собака Олега – Бичо». Олег сказал: «Да, моя собака – Бичо, а собака Бориса – Зевс». Кто же на самом деле хозяин каждой собаки?

Решение.

Обозначим высказывательную форму «Юноша X – хозяин собаки Y» как и запишем получившиеся логические выражения. Из высказываний молодых людей и того факта, что одно из высказываний истинно, а другое ложно, следуют истинные составные высказывания:

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

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

В результате преобразований получим следующее равносильное высказывание:

которое истинно только при .

Ответ. Петр – хозяин Лаймы, Борис – Рекса, Виктор – Зевса, Олег – Бичо, Антон – Джека.

IV. Закрепление материала (10мин).

Примечание: у доски решает один учащийся, остальные оформляют решение задач в тетради. Вторую задачу может решить другой учащийся.

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

Примечание: способ решения определяет сам учащийся.

Ответ. Слева – бог Дипломатии, в центре – бог Лжи, справа – бог Правды.

2) Решите логическую задачу №16 из задачника (приложение 1).

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 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₃ один оказался ложным, а два других — истинным. Эта ситуация соответствует четвёртой строке таблицы.

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

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

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

1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
2. Записать условие задачи на языке алгебры логики, соединив простые высказывания в составные с помощью логических операций.
3. Составить единое логическое выражение, учитывающее все требования задачи.
4. Используя законы алгебры логики, упростить полученное выражение и вычислить его значение.
5. Выбрать решение – набор логических переменных (элементарных высказываний), при котором построенное логическое выражение является истинным.
6. Убедиться, что полученное решение удовлетворяет условиям задачи.

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

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

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

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

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

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

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

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

Источник