Информатика. 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. На вопрос, кто из трёх учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

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

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

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

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

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

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

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

Логические задачи по математике
учебно-методический материал

Методика обучения учеников решению логических задач.

Скачать:

Вложение	Размер
logicheskie_zadachi.ppt	2.43 МБ

Предварительный просмотр:

Подписи к слайдам:

Их зовут . Известно, что все они имеют На одной улице стоят в ряд , в каждом из них живет по одному человеку. Метод рассуждений (1) Столяр живет правее охотника. (2) Врач живет левее охотника. (3) Скрипач живет с краю. (4) Скрипач живет рядом с врачом. (5) Семен не скрипач и не живет рядом со скрипачом. (6) Иван живет рядом с охотником. (7) Василий живет правее врача. (8) Василий живет через дом от Ивана. Определите, где, кто живет. 4 дома Василий, Семен, Геннадий и Иван разные профессии: . Известно, что скрипач, столяр, охотник и врач скрипач? скрипач? врач охотник столяр врач охотник столяр скрипач врач охотник столяр Семен? Иван? Василий? Геннадий Семен? Иван? Василий? Иван Василий Семен Метод кругов Эйлера В ясельной группе манная перловая гречневая 11 7 13 6+1+2+2+0+4+5 = 20 (ребят) Четверо любят и манную, и гречневую, Сколько детей в этой группе, если в ней нет ни одного ребёнка, 3 – манную и перловую, 6- гречневую и перловую, а двое любят все три вида каши. 11 деток любят манную кашу, 13 – гречневую и 7 малышей – перловую. вовсе не любящего кашу. 4 3 2 6 6 1 4 2 0 5 2 Ответ:

Графический метод В кафе встретились друга : , и . «Замечательно , что у одного из нас , у другого , а у третьего волосы , » ,- заметил черноволосый . Какого цвета волосы у художника? три скульптор Белов скрипач Чернов художник Рыжов белые черные скрипач Чернов рыжие скульптор Белов художник Рыжов белый черный рыжий но ни у кого цвет волос не соответствует фамилии «Ты прав» ,- сказал Белов . друзья цвет волос Ложное утверждение — Истинное утверждение — друзья цвет волос белый черный рыжий скульптор Белов скрипач Чернов художник Рыжов Ложное утверждение — Истинное утверждение — 1 0 0 0 0 0 1 0 1 0 1 Табличный метод

Табличный метод и Вессона, умеющих играть на скрипке, флейте, альте, кларнете, гобое и трубе. В симфонический оркестр приняли на работу трёх музыкантов: Брауна, Смита Известно, что: 1. Смит самый высокий; 2. играющий на скрипке меньше ростом играющего на флейте; 3. играющие на скрипке и флейте и Браун любят пиццу; 4. когда между альтистом и трубачом возникает ссора, Смит мирит их; 5. Браун не умеет играть ни на трубе, ни на гобое. На каких инструментах играет каждый из музыкантов, инструмент музыкант скрипка флейта альт кларнет гобой труба Смит Вессон Браун 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 Для заполнения таблицы будем использовать «1», «0» — , . «играет» «не играет» 1 — «истина» , 0 — «ложь». если каждый владеет двумя инструментами?

Перед соревнованиями по плаванию каждого из четырех участников А, Б, В, Г спросили, на какое место он рассчитывает. А сказал: «Я буду первым», Б сказал: «Я не буду последним», В сказал: «Я не буду ни первым, ни последним» и Г сказал: «Я буду последним». После заплыва оказалось, что только один из них ошибочно предсказал результат. Кто из пловцов ошибся? Пловец Места 1 2 3 4 А + Б + + + В + + Г + а) А – 2, Б – 1, В – 3, Г – 4; б) А – 3, Б – 1, В – 2, Г – 4.

В летний лагерь приехали отдыхать три друга: Миша, Володя и Петя. Известно, что каждый из них имеет одну из следующих фамилий: Иванов, Семенов, Герасимов. Миша – не Герасимов. Отец Володи – инженер. Володя учится в 6 классе, Герасимов учится в 5 классе. Отец Иванова – учитель. Какая фамилия у каждого из трех друзей? Имя Фамилия Иванов Семенов Герасимов Миша + — — Володя — + — Петя — — +

После традиционного вечера встречи с выпускниками школы в стенгазете появилась заметка о трех наших бывших учениках. В ней было сказано, что Иван, Андрей и Борис стали учителями. Теперь они преподают разные дисциплины: один из них — математику, второй – физику, а третий – химию. Живут они тоже в разных городах: Минске, Витебске, Харькове. В заметке было также написано, что их первоначальные планы осуществились не полностью: 1) Иван живет не в Минске; 2) Андрей – не в Витебске; 3) житель Минска преподает не математику; 4) Андрей преподает не физику; 5) повезло только жителю Витебска: он преподает любимую им химию. Можно ли по этим данным определить, кто где живет и что преподает? Имя Город Дисциплина Минск Витебск Харьков Математ Физика Химия Иван – + – – – + Андрей – – + + – – Борис + – – – + –

Три товарища – Иван, Дмитрий и Степан преподают различные предметы (химию, биологию и физику) в школах Москвы, Тулы и Новгорода. О них известно следующее: 1) Иван работает не в Москве, а Дмитрий – не в Новгороде; 2) москвич преподает физику; 3) тот, кто работает в Новгороде, преподает химию; 4) Дмитрий и Степан преподают не биологию. Какой предмет, и в каком городе преподает каждый?

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

5 школьников приехали из 5 различных городов в Архангельск на областную математическую олимпиаду. «Откуда вы, ребята?» — спросили их хозяева. Вот что ответил каждый из них. Андреев: «Я приехал из Онеги, а Григорьев живет в Каргополе». Борисов: «В Каргополе живет Васильев. Я же прибыл из Коряжмы». Васильев: «Я прибыл из Онеги, а Борисов – из Котласа». Григорьев: «Я прибыл из Каргополя, а Данилов из Вельска». Данилов: «Да, я действительно из Вельска, Андреев же живет в Коряжме». Хозяева очень удивились противоречивости ответов приехавших гостей. Ребята объяснили им, что каждый из них высказал одно утверждение правильное, а другое ложное. Но по их ответам вполне можно установить, кто откуда приехал.

В классе 36 человек. Ученики этого класса посещают математический, физический и химический кружки, причем математический кружок посещают 18 человек, физический – 14, химический – 10. Кроме того, известно, что 2 человека посещают все три кружка, 8 человек – и математический и физический, 5 – и математический и химический, 3 – и физический и химический. Сколько учеников класса не посещают никаких кружков?

. Среди 150 школьников марки собирают только мальчики. 67 человек собирают марки СССР, 48 человек – Африки и 32 человека – Америки, 11 человек – только СССР, 7 человек – только Африки, 4 человека – только Америки и только Иванов собирал марки СССР, Африки, Америки. Найдите максимальное число девочек.

2 ( x + y + z ) = 122, т.е. x + y + z = 61. 61 + 11 + 7 + 4 + 1 = 84 150 – 84 = 66

После зимних каникул классный руководитель спросил, кто из ребят ходил в театр, кино или цирк. Оказалось, что из 36 учеников класса двое не были ни в кино, ни в театре, ни в цирке. В кино побывало 25 человек, в театре – 11, в цирке – 17; и в кино, и в театре – 6; и в кино, и в цирке – 10; и в театре, и в цирке – 4. Сколько человек побывало и в кино, и в театре, и в цирке

25 – (х + 6 – х + 10 – х) = 9 + х 11 – (х + 6 – х + 4 – х) = 1 + х 17 – (х + 10 – х + 4 – х) = 3 + х. (9+х)+(6-х)+(1+х)+(10-х)+х+(4-х)+(3+х)=33+х. 33 + х = 34 х = 1

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

Спасибо за внимание

По теме: методические разработки, презентации и конспекты

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

Задача для будущих бизнесмепов.

В соответствии с действующим Федеральным государственным образовательным стандартом профессионального образования по специальностям СПО очной формы обучения 49.02.01 Физическая культура, 44.02.0.

Данный тест составлен по теме «Логические задачи» и предназначен для учащихся 5-6 классов. Он может быть использован на уроках для того, чтобы повысить уровень математического развития и расшири.

Урок является частью логически завершенного дня «Математика на службе человека», который был проведен в 11 классе. Информатика изучается в этом классе на профильном уровне по программе Семакина.

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