Технологическая карта урока по информатике по теме «Решение логических задач» для учащихся 8 класса

Урок 27§22. Логические задачи и способы их решения

Содержание урока:

22.1. Метод рассуждений 22.2. Задачи о рыцарях и лжецах 22.3. Задачи на сопоставление. Табличный метод. 22.4. Использование таблиц истинности для решения логических задач 22.5. Решение логических задач путём упрощения логических выражений САМОЕ ГЛАВНОЕ. Вопросы и задания Материалы к уроку

22.3. Задачи на сопоставление. Табличный метод. 22.4. Использование таблиц истинности для решения логических задач
22.2. Задачи о рыцарях и лжецах	22.5. Решение логических задач путём упрощения логических выражений

22.3. Задачи на сопоставление. Табличный метод

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

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

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

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

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

Рассмотрим условия:

1) фотограф старше Гриши; 2) Алёша старше Вити, а шахматист старше Алёши; 3) в воскресенье Алёша с фотографом играли в теннис, а Гриша в то же время проиграл авиамоделисту в городки.

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

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

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

Итак, Алёша занимается в математическом кружке, Боря — в фотокружке, Витя — в авиамодельном кружке, Гриша — в шахматном кружке.

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

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

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

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

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

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

1) если А получит максимальную прибыль, то максимальную прибыль получат B и С; 2) А и С получат или не получат максимальную прибыль одновременно; 3) необходимым условием получения максимальной прибыли подразделением С является получение максимальной прибыли подразделением B.

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

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

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

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

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

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

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

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

Cкачать материалы урока

Решение логических задач (конспект урока + презентация)

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

9 слайд – открывается задача. Бабушка знала, что один из её внуков, назовём его правдивым, оба раза сказал правду; второй, назовём его шутником, оба раза сказал неправду; третий, назовём его хитрецом, один раз сказал правду, а другой раз — неправду. Назовите имена правдивого, шутника и хитреца. Кто из внуком разбил вазу?

Серёжа: Я не разбивал. Вася не разбивал.

Вася: Серёжа не разбивал. Вазу разбил Коля.

Коля: Я не разбивал. Вазу разбил Серёжа. Получится ли у вас быстро решить эту задачу, не используя таблицы?

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

Давайте закрепим этот способ.

Открывается 10 слайд. Разбирается дело Джона, Брауна и Смита. известно что один из них нашел и утаил клад. на следствии каждый из подозреваемых сделала два заявления:

Смит

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

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

Но не всегда табличный способ решения задач применим. Посмотрите на следующую задачу. Открывается 11 слайд. В соревнованиях по гимнастике участвовали Алла, Валя, Сима, Даша. Были высказаны предположения:

1) Сима будет первой, Валя второй;

2) Сима будет второй, Даша третьей;

3) Алла будет второй, Даша четвёртой.

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

Сима будет первой – С1

Валя второй – В2

Сима будет второй – С2

Даша третьей –Д3

Алла будет четвертой – А4

Даша будет четвертой – Д4

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

С1+В2=1, С1*В2=0
С2+Д3=1, C2*Д3=0
А2+Д4=1, А2*Д4=0

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

(С1+В2)*( С2+Д3)*( А2+Д4)=1

Далее применяя законы и получая противоречия мы получим единственно верное решение.

С1*Д3*А2=1

А это означает, что Сима заняла первое место, Алла – второе, Даша третье. Следовательно Валя заняла четвертое место.

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

Урок по информатике ( 8 класс) на тему «Решение задач алгебры логики»

Тема:

Решение задач на тему «Алгебра логики»

Цели:

образовательная

– знакомство учащихся с методами решения логических задач;

развивающие

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

воспитательные

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

Ход урока

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

Пример 1Проверить равносильность выражений А ~ E и (Ā ∧ Ē) v (A ∧ E).

Решение. Для проверки следует создать таблицу истинности, содержащую столько строк, сколько возможно наборов значений переменных, входящих в выражение. Для двух переменных (А и E) количество наборов равно четырем. К двум столбцам для значений переменных (А и E) нужно присовокупить количество столбцов, равное количеству операций в выражении. Таким образом, необходимо создать таблицу, содержащую 4 строки и 7 столбцов.

Заполним первые 2 столбца (А и E) всеми сочетаниями значений переменных. Запишем в качестве заголовков столбцов все операции выражения в порядке их выполнения (в соответствии с приоритетами и скобками). Рассчитаем значения этих операций: сначала выражения в скобках, затем результат их сложения.

Последний столбец содержит результирующее значение выражения. Он совпадает с таблицей истинности для операции эквивалентности. Следовательно, выражения равносильны.

Основные законы алгебры логики

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

Нормальная форма выражения содержит только операции отрицания, конъюнкции и дизъюнкции и не содержит отрицания выражений и двойных отрицаний.

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

Тождественные преобразования логических выражений

Для всех тождественных преобразований выполняется закон двойственности: если в формуле преобразования заменить конъюнкцию на дизъюнкцию, дизъюнкцию — на конъюнкцию, значения 1 — на 0, 0 — на 1, то закон, сформулированный для конъюнкции, примет форму аналогичного закона для дизъюнкции, и наоборот.

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

Пример 2Выбрать выражение, которое равносильно выражению (A ∧ B) v (Ā ∧ B).

1) A 2) A ∧ B 3) Ā ∧ B 4) B

Решение. В соответствии с законом склеивания (A ∧ B) v (Ā ∧ B) = B, следовательно, исходное выражение равносильно выражению В. Ответ: 4) В.

ОПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ ЛОГИЧЕСКИХ ВЫРАЖЕНИЙ

Выражения, которые принимают логические значения (истина или ложь) в результате выполнения операций сравнения (больше >, меньше <, больше или равно ≥, меньше или равно ≤, равно =, не равно ≠), также являются логическими выражениями. Кроме операций сравнения и логических операций такие выражения могут включать функции и алгебраические операции. Приоритет выполнения этих операций таков:

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

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

Пример 3Для какого из приведенных ниже значений числа М истинно следующее выражение? ¬М ≥ 10 ∧ M > 3

1) 1 2) 2 3) 3 4) 4

Решение. В соответствии с приоритетами операций сначала следует выполнить операции сравнения, затем отрицания, а потом — конъюнкцию. Отрицанием высказывания М ≥ 10 является высказывание М < 10. Получим выражение М < 10 ∧ M > 3. Для того чтобы это выражение (конъюнкция) было истинным, должны выполняться (т. е. быть истинными) оба неравенства. Следовательно, значение М должно быть больше 3, но меньше 10. Среди предложенных значений этому условию удовлетворяет только одно — число 4. Ответ: 4) 4.

Задачи, подобные предыдущему примеру, можно решать и с помощью таблиц истинности.

Пример 4Для какого из приведенных ниже значений числа М истинно следующее выражение? ¬М ≥ 10 ∧ M > 3

1) 1 2) 2 3) 3 4) 4

Решение. Составим таблицу истинности: все операции выражения укажем в столбцах таблицы, все предложенные значения М укажем в ее строках. Рассчитаем значения таблицы:

Последний столбец содержит результат всего выражения. Истинным оно будет только для значения числа М, равного 4. Ответ: 4) 4.

Пример 5В табличной форме представлены ежемесячные данные о продаже групп товаров за полгода. Сколько групп товаров демонстрировали рост продаж в весенние месяцы или вышли на уровень свыше 80 % в июне?

Решение. Переформулируем условие задачи: необходимо найти группы товаров, для которых (Март < Апрель) ∧ (Апрель < Май) v (Июнь > 80).

Введем обозначения: А = (Март < Апрель) В = (Апрель < Май) С = (Июнь > 80)

Тогда выражение можно записать как А ∧ В v С.

Логическое выражение состоит из одной конъюнкции и одной дизъюнкции. Значение выражения конъюнкции истинно только тогда, когда истинны оба составляющие его простых выражения ((Март < Апрель) и (Апрель < Май)). Значение выражения дизъюнкции будет истинным, если хотя бы одно из составляющих его простых высказываний будет истинным.

Составим таблицу истинности для исходных данных.

Логическому выражению удовлетворяют 3 записи — 4–я, 6–я и 7–я. Ответ: 3.

Домашнее задание:

повторить правила.