Определите кто из двух учеников пришел в школу если следующие два высказывания истинны

Обновлено: 02.07.2024

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

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

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

Научить учащихся решать логические задачи средствами алгебры логики ;

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

Ожидаемые результаты обучения:

Учащиеся должны знать:

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

методы решения логических задач.

Учащиеся должны уметь:

применять законы логики;

упрощать сложные логические выражения:

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

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

III. Изложение нового материала.

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

средствами алгебры логики;

с помощью рассуждений.

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

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

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

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

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

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

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

Задача. Представим такую ситуацию: по телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее:

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

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

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

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

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

Запишем сложные высказывания через введенные переменные:

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

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

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

Запишем произведение указанных функций:

Упростим формулу (используем законы де Морга, переместительный закон, закон противоречия):

Приравняем результат единице, т.е. наше выражение должно быть истинным:

Логическое произведение равно 1, если каждый множитель равен 1.

Значит: А=0; В=0; С=0

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

IV. Закрепление изученного материала.

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

Отрицания этих высказываний:

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

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

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

Подставим вместо Х и Y соответствующие формулы:

Упростим сначала первое слагаемое. В соответствии с законом дистрибутивности умножения относительно сложения:

В соответствии с законом непротиворечия:

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

В соответствии с законом непротиворечия:

В результате получим:

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

Ответ. В первой аудитории находится кабинет физики, а во второй - кабинет информатики.

Решение. Обозначим буквами высказывания:

А — логику изучал Андрей; В — логику изучал Борис; С — логику изучал Семен.

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

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

Теперь представляем импликацию через базовые операции и применяем закон де Моргана:

3. Решение истинностных задач

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

А) Макс победит, Билл – второй;

В) Билл – третий, Ник – первый;

С) Макс – последний, а первый – Джон.

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

1. Макс победит, Билл – второй;
2. Билл – третий, Ник – первый;
3. Макс – последний, а первый – Джон.

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

5) Пусть первый болельщик угадал, что Билл занял второе место, тогда второй болельщик предсказал первое место Нику, следовательно, по предположению третьего, Макс занял последнее место, а Джон – оставшееся третье место.

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

1) Запишем высказывания трех болельщиков в форме таблицы (заголовок строки обозначает место в турнирной таблице):

Решение (способ 3, логические выражения):

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

Отрицания этих высказываний:

Х = А ˅ В.

Высказывание на второй двери:

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

Подставим вместо X и Y соответствующие формулы:

В соответствии закона непротиворечия:

Далее упростим второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

В соответствии с законом непротиворечия:

В результате получаем:

Построим таблицу истинности для полученного выражения:

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

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

будет выведено: 1234

Другие вопросы по Информатике

Сколько различных слов в племени тамбо-мамбо, если нужно всего 6 бит, чтобы закодировать каждое из этих слов?

Паскаль абс. 1)дано целое число n> 0. с клавиатуры вводится n любых чисел , найти сумму только четных из этих чисел. вывести полученное значение на экран.

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

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

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Информатика. 10 класса. Босова Л.Л. Оглавление

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

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

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

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

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

1) столяр живёт правее охотника;
2) врач живёт левее охотника;
3) скрипач живёт с краю;
4) скрипач живёт рядом с врачом;
5) Семён не скрипач и не живёт рядом со скрипачом;
6) Иван живёт рядом с охотником;
7) Василий живёт правее врача;
8) Василий живёт через дом от Ивана.

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

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

Известно, что скрипач живёт с краю (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 — Семён.

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

22.2. Задачи о рыцарях и лжецах

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

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

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

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

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

Пример 3. Рядом стоят два города: город Лжецов (Л) и город Правдивых (П). В городе Лжецов живут лжецы, а в городе Правдивых — правдивые люди. Лжецы всегда лгут, а правдивые — всегда говорят правду. Лжецы и правдивые ходят друг к другу в гости.

Самостоятельно разберитесь с решением задачи, рассмотрев блок-схему на рис. 4.12.

Пример 4. Перед нами три человека: А, В и С. Один из них рыцарь, другой — лжец, третий — нормальный человек. При этом неизвестно, кто есть кто. Эти люди утверждают следующее:

1) А: я нормальный человек;
2) В: это правда;
3) С: я не нормальный человек.

Кто такие А, В и С?

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

Начнём с А. Он может быть рыцарем (Р), лжецом (Л) или нормальным человеком (Н). Если А — рыцарь, то В может быть лжецом или нормальным человеком и т. д. Представим все варианты распределения ролей в таблице:

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

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

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

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.

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

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

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

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

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

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

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

22.5. Решение логических задач путём упрощения логических выражений

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

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

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

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

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

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

САМОЕ ГЛАВНОЕ

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

К ним относятся методы:

1) построения таблицы истинности по условию задачи и её анализ;
2) составления и упрощения логического выражения.

Вопросы и задания

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

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

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

1) преподаватель немецкого языка и преподаватель математики в студенческие годы занимались художественной гимнастикой;
2) Ильин старше Флёрова, но стаж работы у него меньше, чем у преподавателя экономической географии;
3) будучи студентками, Аркадьева и Бабанова учились вместе в одном университете. Все остальные окончили педагогический институт;
4) Флёров — сын преподавателя французского языка, но студентом у него не был;
5) преподаватель французского языка — самый старший из всех по возрасту и у него самый большой стаж работы. Он работает в педагогическом институте с тех пор, как окончил его. Преподаватели математики и истории — его бывшие студенты;
6) Аркадьева старше преподавателя немецкого языка.

Кто какой предмет преподаёт?

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

1) ни Дима, ни Юра не знают японского;
2) переводчик с шведского старше переводчика с немецкого;
3) переводчик с китайского, переводчик с французского и Саша родом из одного города;
4) переводчик с греческого, переводчик с немецкого и Юра учились втроём в одном институте;
5) Дима — самый молодой из всех троих, и он не знает греческого;
6) Юра знает два европейских языка.

Укажите имена переводчика с шведского языка и переводчика с китайского языка.

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

1) у Вали день рождения зимой, а у Кати — летом;
2) у Кати день рождения осенью, а у Маши — весной;
3) весной празднует день рождения Наташа, а Валя отмечает его летом.

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

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

1) если А нарушил, то и B нарушил правила обмена валюты;
2) если В нарушил, то и С нарушил или А не нарушал;
3) если D не нарушал, то А нарушил, а С не нарушал;
4) если D нарушил, то и А нарушил.

Кто из подозреваемых нарушил правила обмена валюты?

Дополнительные материалы к главе смотрите в авторской мастерской.

Читайте также: