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

«Исследование и сравнение способов решения логических задач»

Выполнила

Торосян Надежда

Научный руководитель: Пяткина Г.А.

Москва 2013 г.

Введение

Вся наша жизнь - это непрерывное решение разнообразных логических проблем. Логические задачи отличаются от математических тем, что для их решения необходима сообразительность, а не какие-то особые знания, и, чаще всего, решающий логические задачи должен иметь в виду некоторые очевидные истины, такие как: отец старше своего сына; генерал старше майора по званию и т.п. Иначе говоря, решающий задачу использует исключительно логику. «Логика (от греч. logos - слово, понятие, рассуждение, разум) - наука о законах и формах рационального мышления, методах формализации содержательных теорий.» См.: Логика в информатике /В.Ю. Лыскова, Е.А. Ракитина Чтобы научиться логически мыслить, необходимо уметь анализировать, сравнивать, обобщать, систематизировать полученную информацию, а также доказывать и опровергать, определять и объяснять понятия. Во многих ситуациях человек действует интуитивно, или опираясь на жизненный опыт, не нуждаясь в пояснении своих решений, но при логическом подходе к проблеме всегда необходимо пояснение принятых решений и выводов. Решение логических задач в некоторой степени напоминает решение научной проблемы, так как исследователь сначала сталкивается с массой данных, и часто не имеет возможности сразу сделать какие-либо заключения. Поэтому ему приходится выдвигать одну или несколько гипотез, а затем сопоставлять полученные из исследования гипотез результаты с исходными данными. Если обнаруживается несоответствие теоретических данных фактам, гипотеза отвергается и заменяется новой, после чего проверятся так же, как предыдущая. И так до тех пор, пока результаты не совпадут с изначальными данными. Такой же принцип используется и при решении логических задач.

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

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

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

Задачами моего исследования являются:

- изучить теоретически способы решения логических задач;

- сравнить между собой эффективность применения этих способов по отношении к разным типам задач;

- создать сайт, содержащий рекомендации по использованию разных способов в решении задач;

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

- написать отчет о проделанной работе.

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

В процессе работы над дипломом были использованы задачник по моделированию «Информатика и ИКТ» Н.В. Макаровой, справочник «Логика в информатике» В. Ю. Лысковой и Е. А. Ракитиной. При выполнении следующей части работы будут использованы учебник для 9 класса «Информатика и ИКТ. Базовый курс Н. Д. Угриновича и самоучитель «Программирование в среде Delphi 7» Галисеева Г.В.

Глава I. Теоретическая часть. Методы решения логических задач

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

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

Рассмотрим этот способ на примере некоторых задач.

Задача 1. В поездке пятеро друзей - Антон, Борис, Вадим, Дима и Гриша знакомились с попутчицей. Они предложили ей отгадать их фамилии, и каждый из них высказал одно истинное и одно ложное утверждение. Вот что они сказали:

Дима: моя фамилия - Мишин, а фамилия Бориса - Хохлов.

Антон: Мишин - это моя фамилия, а фамилия Вадима - Белкин.

Борис: фамилия Вадима - Тихонов, а моя фамилия - Мишин.

Вадим: моя фамилия - Белкин, а фамилия Гриши - Чехов.

Гриша: да, моя фамилия Чехов, а фамилия Антона - Тихонов.

Какую фамилию носит каждый из друзей?

Решение. Обозначим высказывательную форму «юноша по имени А носит фамилию Б» как АБ, где буквы А и Б соответствуют первым буквам имени и фамилии. Далее, зафиксируем высказывания каждого мальчика. Получается:

ДМ и БХ; АМ и ВБ; ВТ и БМ; ВБ и ГЧ; ГЧ и АТ.

Сначала, допустим, что истинно ДМ. Следовательно, АМ и БМ ложно, так как у Антона и Бориса должны быть другие фамилии. Но если АМ и БМ ложны, то должны быть верны другие два высказывания из пар, то есть ВБ и ВТ, но они не могут быть истинными одновременно. Вернемся к началу: из первой пары высказываний ДМ не верно, значит, верно БХ. А значит, те случаи, в которых первая буква Б, а вторая не Х ложны. Таковым является второе высказывание из третьей пары - БМ, а значит из этой пары верно второе высказывание, то есть ВТ. С ним можно поступить также как и с предыдущим верным, в результате чего получаем, что из четвертой пары верно ГЧ, а из второй - АМ. Следовательно, получаем такие верные высказывания: БХ, ВТ, ГЧ, АМ. Остается одна свободная буква имени и одна буква фамилии - ДБ. Получаем ответ: Фамилия Бориса - Хохлов, Вадима - Тихонов, Гриши - Чехов, Антона - Мишин, а Димы - Белкин.

Задача 2. В первом туре школьного конкурса «Эрудит» в четверку лучших вошли: Дима, Катя, Миша и Нина. И конечно, болельщики высказывали свои предположения о распределении мест во втором, финальном туре. Один считал, что первым будет Дима, а Миша будет вторым. Другой болельщик выразил надежду на то, что Катя займет четвертое место, а второе место достанется Нине. Третий же был уверен в том, что Катя займет третье место, а на втором месте будет Дима. В результате оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какие места заняли Дима, Катя, Миша, Нина?

Решение. Мы имеем три пары высказываний болельщиков, в каждой из которых одно высказывание истинно, а второе ложно: Дима-1 и Миша-2; Катя-4 и Нина-2; Катя-3 и Дима-2. Предположим, что из первой пары верно второе высказывание, то есть то, что Миша-2. Из этого следует, что больше никто не может быть вторым, то есть вторые высказывания во второй и третьей парах ложны. Остается считать истинными первые высказывания в этих парах, то есть Катя-4 и Катя-3, что, очевидно, невозможно. Значит, изначальное предположение было неверно. Значит, из первой пары верно первое высказывание, что Дима-1. Значит, последнее высказывание третьей пары, что Дима-2 ложно, а следовательно верно то, что Катя-3. Если Катя-3, то первое высказывание второй пары, что Катя-4 ложно, а значит второе, что Нина-2 верно. Получаем, что Дима-1, Нина-2, Катя-3, а следовательно Миша-4.

1.2 Метод таблиц

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

Рассмотрим данный метод на примере нескольких задач.

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

Смит самый высокий;

Играющий на скрипке ниже ростом играющего на флейте;

Играющие на скрипке и флейте и Браун любят пиццу;

Когда между альтистом и трубачом возникает ссора, Смит мирит их;

Браун не умеет играть ни на трубе, ни на гобое.

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

Решение. Составим таблицу, в которой в строках будут фамилии музыкантов, а в столбцах названия музыкальных инструментов. Отразим в ней условия задачи, заполнив соответствующие клетки + и - в зависимости от того, возможен такой вариант или нет. Так, если сопоставить 1 и 2 утверждения, можно сделать вывод, что Смит не играет на скрипке. Из условия 4 следует, что Смит не играет ни на альте, ни на трубе и из условий 3 и 5, что Браун не играет ни на скрипке, ни на флейте, ни на трубе, ни на гобое. Итак, получаем таблицу со знаками «-» в соответствующих клетках:

Теперь, мы видим, что в столбцах «скрипка» и «труба» стоят минусы в двух строках из трех, значит остается только один вариант - поставить в оставшийся строке «+». Получается, что Вессон играет на трубе и на скрипке. Тогда, в строке «Вессон» можно поставить минусы во всех остальных клеточках. Вот что мы получим:

Теперь, в столбцах «флейта», «альт» и «гобой» тоже стоит по два минуса. Значит, в оставшихся клеточках этих столбцов тоже можно поставить знак «+».

Итак, остается недозаполненным только один столбец - «кларнет». А именно, клеточки на пересечении этого столбца со строками «Браун» и «Смит». В этом случае, смотрим на количество знаков «+» в этих строках. В строке «Смит» их два, значит, в соответствующей клеточке мы ставим «-», так как в строке не может быть три «+», потому что каждый музыкант играет только на двух музыкальных инструментах. Значит, в клеточке на пересечении строки «Браун» и столбца «кларнет» ставим «+». Получается полностью заполненная таблица:

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

Задача 4. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой брюнет, а третий - рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей?

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

Далее, следует обратить внимание на то, что в разговоре брюнет обращается к Белокурову, а значит, это не может быть один и тот же человек. Ставим «-» в соответствующей клеточке:

Из таблицы видно, что брюнетом не может быть ни Белокуров, ни Чернов, а значит, брюнет - Рыжов. Ставим в клеточке на пересечении его фамилии с соответствующим столбцом знак «+». Но так как Рыжов не может быть одновременно и брюнетом, и блондином, то на пересечении со столбцом «блондин» тоже ставим знак «-».