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

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

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

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

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

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

В рамках данного урока мы будем рассматривать подобные задачи, решение которых требует логических рассуждений. Следует отметить, что некоторые логические задачи мы можем решать в уме или на бумаге. Но не лучше ли доверить их решение компьютеру в случае большого объёма входных данных, когда решение в уме невозможно, а на бумаге уйдёт много времени?

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

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

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

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

Умение выстраивать логические цепочки очень важно для человека. Каждый знает литературного героя Шерлока Холмса, который умел в совершенстве выстраивать логические цепочки, которые приводили к поимке преступника.

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

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

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

Ещё один пример рассуждения, когда легко ошибиться, — так называемая ошибка выжившего. Венгерский математик Абрахам Вальд во время Второй мировой войны исследовал повреждения американских самолётов, вернувшихся на базу с боевого задания. Он увидел, что у большинства вернувшихся самолётов повреждения расположены на фюзеляже, а на двигателе и топливных баках повреждений было значительно меньше. Какой вывод напрашивается в первую очередь? Наверное, логично было бы предположить, что укреплять бронёй нужно корпус самолёта в тех местах, где пробоин больше.

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

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

История космонавтики, например, помнит множество трагедий, вызванных неверными расчётами или неверными рассуждениями. В 1986 году шаттл «Челенджер» Американского аэрокосмического агентства NASA потерпел катастрофу из-за того, что инженеры не учли некоторые свойства материалов, влияющие на работу систем в холодную погоду. Было принято решение о старте шаттла, которое погубило 7 астронавтов.

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

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

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

• метод рассуждений;

• метод таблиц;

• метод графов;

• метод блок-схем;

• метод бильярда;

• метод кругов Эйлера;

• использование алгебры\nлогики.

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

Метод рассуждения. Кто из нас не любит иногда порассуждать? Мы стараемся строить причинно-следственные связи исходя из того, что знаем. В принципе, это и является основной идеей данного метода — последовательные рассуждения и выводы из утверждений, содержащихся в условиях задач. Суть метода проста, и мы усваиваем его ещё в детстве, решая простейшие логические задачи. Но вот реализация и сами рассуждения могут быть довольно сложными.

Задача 1.

Альберт и Бернард только что познакомились с Шерил. Они хотят знать, когда у неё день рождения. Шерил предложила им десять возможных дат:

• 15 мая, 16 мая, 19 мая;

• 17 июня, 18 июня;

• 14 июля, 16 июля;

• 14 августа, 15 августа и 17 августа.

Затем Шерил сказала Альберту месяц своего рождения, а Бернарду — день.

После этого состоялся диалог.

Альберт: «Я не знаю, когда у Шерил день рождения, но я знаю, что Бернард тоже не знает».

Бернард: «Поначалу я не знал, когда у Шерил день рождения, но знаю теперь».

Альберт: «Теперь я тоже знаю, когда у Шерил день рождения».

Вопрос простой: когда у Шерил день рождения?

Теперь порассуждаем.

Числа 19 и 18 встречаются только один раз: 19 мая и 18 июня. Если бы это были нужные нам даты, тогда Бернард по названному ему числу сразу отгадал дату рождения Шерил. Бернард утверждает, что поначалу не знал этой даты. Исключаем 19 мая и 18 июня из списка.

Почему Альберт утверждает, что Бернард не знает ответа? Всё просто. Альберт уверен, что месяц рождения не май и не июнь, иначе бы это могли быть даты 19 мая и 18 июня, и тогда Бернард бы мог знать дату рождения. Поэтому уверенность Альберта в незнании Бернарда говорит о том, что это точно не эти месяцы. Остаются только июль или август.

Перейдём к третьей фразе: Альберт сначала не знал дату, но после фразы Бернарда узнал.

Как Бернард мог узнать точную дату? Из первой фразы Альберта он, как и мы, понял, что речь про июль или август. Если бы Шерил сказала ему 14, то он не смог бы сделать однозначный вывод — 14 июля или 14 августа. Значит, Альберт точно знает, что Бернард услышал другое число. Остаются варианты 15, 16 и 17.

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

Ответ: день рождения Шерил — 16 июля.

Эту задачу мы решали путём рассуждения. Решение представляли в произвольной форме на естественном языке. Но можно ли подобным образом поручать их решение компьютеру? Поймёт ли он условие задачи? Сможет ли разобрать наши рассуждения по поводу дат и месяцев?

Не сможет, ведь для этого нужно формулировать и записывать подобные задачи на языке, понятном компьютеру. И для этого у нас есть мощный инструмент — алгебра\nлогики.

Используем её для решения подобных задач.

Задача 2.

Учащиеся принимали участие в соревнованиях по лёгкой атлетике. В дисциплине «бег на 100 метров» определилась тройка победителей: Иванов, Петров, Сидоров. Нам известно два факта:

1. если Иванов занял первое место, то Сидоров не занял первое место;

2. неверно, что если Сидоров занял первое место, то Петров занял первое место.

Кто же всё-таки занял первое место в этом соревновании?

Приступим к решению данной задачи.

Обозначим выражения (потенциальные ответы) следующим образом:

• «Иванов занял первое место» —;

• «Петров занял первое место» —;

• «Сидоров занял первое место» —.

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

Если Иванов занял первое место, то Сидоров не занял первое место .

Неверно, что если Сидоров занял первое место, то Петров занял первое место — .

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

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

Используем правило преобразования импликации: .

Выражение  преобразуем по правилу де Моргана: .

Используя распределительный закон, раскроем скобки:

.

Так как , то .

Получаем: .

Конъюнкция , если , , .

Ответ: Сидоров занял первое место.

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

1-е утверждение: если Иванов занял первое место, то Сидоров не занял первое место.

2-е утверждение: неверно, что если Сидоров занял первое место, то Петров занял первое место.

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

Только в 3-м предположении оба утверждения истинны. Значит, 1-е место в соревновании занял Сидоров.

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

Представьте, что входных параметров, или в нашем случае — спортсменов, значительно больше —Легко ли будет решать задачу в уме или словесными рассуждениями в этом случае? А для компьютера и рассмотренного метода принципиально ничего и не поменяется, разве что «думать» машина будет на несколько микро- или миллисекунд больше.

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

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

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

Задача 3.

Ученики 8-го класса любят активный отдых. Известно, что 15 учеников любят ходить в поход, а 11 — кататься на велосипедах, из них 6 любят как походы, так и катание на велосипедах. Сколько человек предпочитают только велосипед?

Для решения нарисуем 2 круга следующим образом:

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

Выполним действия вычитания согласно условию:

1. — количество детей, кто только ходит в поход;

2. — количество детей, кто только катается на велосипедах.

Визуализируем наш результат:

Ответ: пятеро ребят являются фанатами только велосипедов.

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

Мы должны представить каждое переливание как движение бильярдного шара по игровому столу с учётом принципа «угол удара в борт стола равен углу отскока шара».

Покажем этот метод на примере задачи 4.

У нас есть два ведра — на 11 и на 7 литров. С помощью этих вёдер нужно отмерить 2 литра воды. Рисуем четырёхугольник согласно условию задачи.

У соседних сторон отмеряем такую длину, которая соответствует объёму сосудов. Так как у нас разные сосуды, то получится параллелограмм (рис. 5). Ставим шар в левую нижнюю вершину в точке 0 и как будто делаем удар кием по этому шару в правую сторону.

Шар будет катиться вправо вдоль нижнего основания параллелограмма до тех пор, пока не достигнет правой боковой стороны в точке 11. Это означает, что мы заполнили 11-литровый сосуд, а 7-литровый пока не трогали, и он пуст.

Мы помним, что угол удара равен углу отражения, поэтому, отразившись от правого борта, шар покатится вверх и влево и ударится в верхний борт стола в точке с координатами 4 по горизонтали и 7 по вертикали. Это означает, что мы перелили часть воды из 11-литрового сосуда в 7-литровый, и теперь в 11-литровом сосуде осталось всего 4 литра воды, а 7 литров из него перелили в меньший сосуд.

В итоге на получение двух литров воды нужно сделать 18 таких переливаний.

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

Попробуйте самостоятельно реализовать этот метод для задачи, в которой вам даны сосуды объёмом 8 и 3 литра, а получить нужно 4.

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

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

Для демонстрации способа решения задач методом кругов Эйлера была рассмотрена другая не менее интересная и жизненная задача.

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

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

Полезные ссылки

1. Список рекомендованных учебников

Проверьте себя

1. Какие методы могут использоваться при решении логических задач?

2. Какой из рассмотренных методов подойдёт для решения логических задач на компьютере?

3. В семье Ани все книголюбы: пятеро с удовольствием читают детективы, четверо — фантастику, трое любят читать и то, и другое. Сколько человек в семье Ани? Решите задачу методом кругов Эйлера.

4. Из трёх друзей, пытавшихся решить олимпиадную задачу по информатике, это удалось двоим. Назовите их имена, если известно:

• если Артём не решил задачу, то Борис её решил;

• неверно, что если Борис не решил задачу, то и Виктор её не решил.

Решите задачу, используя алгебру логики.

Список использованных источников:

Иллюстратор Бумастрова А. В.
Источник: wikipedia.org / название: Damaged tail of B-17 / атрибуция: public domain, автор: U.S. Air Force photo
Источник: wikipedia.org / название: 51-L Challenger Crew in White Room - GPN-2000-001867/ атрибуция: public domain, автор: NASA