Урок в 11 классе по теме «Решение логических задач» план-конспект урока по информатике и икт (11 класс) на тему

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

Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 10 классы | Планирование уроков на учебный год (ФГОС) | Логические задачи и способы их решения

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

22.1. Метод рассуждений 22.2. Задачи о рыцарях и лжецах 22.3. Задачи на сопоставление. Табличный метод. 22.4. Использование таблиц истинности для решения логических задач 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качать материалы урока

Решение логических задач

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

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

Познакомимся с ними поочередно.

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

1. изучается условие задачи;

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

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

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

Пример 1. Трое друзей, болельщиков автогонок «Формула-1», спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

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

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

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

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

Джон: ¬Ш/\Х

Ник: Ш/\¬А

Питер: ¬Х

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

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

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

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

Известно, что:

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

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

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

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

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

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

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

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

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

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

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

Решение. Имеется три утверждения:

1. Вадим изучает китайский;
2. Сергей не изучает китайский;
3. Михаил не изучает арабский.

Если верно первое утверждение, то верно и второе, так как юноши изучают разные языки. Это противоречит условию задачи, поэтому первое утверждение ложно.

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

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

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

Пример 4. Министры иностранных дел России, США и Китая обсудили за закрытыми дверями проекты соглашения о полном разоружении, представленные каждой из стран. Отвечая затем на вопрос журналистов: «Чей именно проект был принят?», министры дали такие ответы:

Россия — «Проект не наш, проект не США»; США — «Проект не России, проект Китая»; Китай — «Проект не наш, проект России».

Один из них (самый откровенный) оба раза говорил правду; второй (самый скрытный) оба раза говорил неправду, третий (осторожный) один раз сказал правду, а другой раз — неправду.

Определите, представителями каких стран являются откровенный, скрытный и осторожный министры.

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

Россия — «Проект не наш» (1), «Проект не США» (2); США — «Проект не России» (3), «Проект Китая» (4); Китай — «Проект не наш» (5), «Проект России» (6).

Узнаем, кто из министров самый откровенный.

Если это российский министр, то из справедливости (1) и (2) следует, что победил китайский проект. Но тогда оба утверждения министра США тоже справедливы, чего не может быть по условию.

Если самый откровенный — министр США, то тогда вновь получаем, что победил китайский проект, значит оба утверждения российского министра тоже верны, чего не может быть по условию.

Получается, что наиболее откровенным был китайский министр. Действительно, из того, что (5) и (6) справедливы, cледует, что победил российский проект. А тогда получается, что из двух утверждений российского министра первое ложно, а второе верно. Оба же утверждения министра США неверны.

Ответ: Откровеннее был китайский министр, осторожнее — российский, скрытнее — министр США.

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

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

Готовые работы на аналогичную тему

• Курсовая работа Решение логических задач 480 руб.
• Реферат Решение логических задач 230 руб.
• Контрольная работа Решение логических задач 250 руб.

Получить выполненную работу или консультацию специалиста по вашему учебному проекту Узнать стоимость
Пример 1

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

Решение:

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

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

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

Ответ: Семен изучает английский язык, Олег — французский, Владимир — немецкий.

Лень читать?

Задай вопрос специалистам и получи ответ уже через 15 минут!

Задать вопрос