"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Логическая задача — это задача, ответ на которую находят рассуждением, связывая между собой условия. Чтобы не запутаться в вариантах, нужно выделить объекты и ограничения, а затем выбрать удобный способ представления: таблицу, граф или проверку предположений. Главная цель — найти вариант, который удовлетворяет всем условиям, и убедиться, что другие варианты исключены или тоже подходят.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Логическая задача — задача, в которой ответ находят рассуждением на основе условий и связей между ними. В отличие от вычислительной задачи, здесь часто нужно не получить число по формуле, а установить, какой вариант возможен. Такое определение помогает сразу искать в условии отношения между объектами.
Логическое высказывание — утверждение, которое можно оценить как истинное или ложное. Например, фраза «Аня заняла первое место» в задаче о соревновании может оказаться истинной или ложной. Точное понимание высказываний нужно, чтобы не смешивать факты условия, предположения и выводы.
Табличный метод — способ решения, при котором возможные варианты и их соответствие условиям записывают в таблицу. В клетках можно отмечать, подходит ли сочетание объекта и признака или пока ничего о нём не известно. Таблица нужна, чтобы видеть сразу все варианты и не полагаться на память.
Графический метод — способ представить объекты и отношения между ними вершинами и линиями. Вершины обозначают объекты, а линии — связи между ними; например, города можно изобразить вершинами, а дороги — линиями. Такое представление помогает заметить устройство связей и проверить, какие варианты допустимы.
Решение начинают с выделения объектов, возможных значений и всех ограничений, заданных в условии. Если оставить условие обычным текстом, отдельное ограничение легко упустить или понять не так, как задумано. Перечень объектов и значений превращает рассказ в чёткую систему отношений, с которой уже можно работать последовательно.
Таблица помогает не пропустить варианты, потому что каждый объект и возможное значение получают своё место. По мере проверки условий несовместимые сочетания отмечают как невозможные, а неизвестные пока оставляют открытыми. Так ограничения сужают поиск шаг за шагом, и решение не зависит от случайного выбора первого пришедшего в голову варианта.
Если в задаче описаны связи между несколькими объектами, их удобно представить графом. Граф — это набор вершин и линий между ними: вершинами становятся объекты, а линиями — заданные отношения. Визуальная структура позволяет увидеть, где связи есть, какие объекты изолированы и какие условия могут исключить предполагаемый маршрут или сочетание.
В задачах на правдивые и ложные высказывания полезно проверять предположения по очереди. Сначала принимают один возможный вариант, например что говорящий всегда лжёт, затем выясняют, к чему приводит его фраза. Если следствия противоречат принятому варианту или другим условиям задачи, предположение нужно отбросить; оставшиеся варианты проверяют тем же способом.
Полученный вариант необходимо проверить по всем исходным условиям, а не только по тому, которое помогло его найти. Это нужно потому, что отдельное ограничение может исключить многие варианты, но не гарантирует правильность последнего оставшегося. После проверки сформулируйте ответ и покажите, почему другие варианты невозможны; если их не удалось исключить, решений может быть несколько.
| Способ | Что записывают | Когда удобен | Что помогает сделать |
|---|---|---|---|
| Таблица | Объекты, варианты и отметки о совместимости | Когда нужно сопоставить несколько групп объектов и признаков | Последовательно исключать невозможные сочетания |
| Граф | Объекты как вершины, отношения как линии | Когда условие описывает связи между объектами | Увидеть структуру связей и проверить допустимые варианты |
| Проверка предположений | Предположение и его следствия | Когда условие содержит высказывания, которые могут противоречить друг другу | Найти противоречие и отбросить неверный вариант |
Выбирайте способ по тому, что именно требуется сравнить: таблица подходит для сочетаний признаков, граф — для отношений между объектами. Если ключевую роль играют истинность или ложность фраз, удобнее разбирать предположения и их следствия. В любой записи отдельно отмечайте невозможное и пока неизвестное.
Три ученика заняли первое, второе и третье места. Аня не первая, Боря не второй, а Вика заняла место выше Бори. Нужно установить порядок. Начнём с Бори: он не может быть вторым, поэтому возможны первое или третье места.
Ответ: первое место — Вика, второе — Аня, третье — Боря. Таблица возможных мест помогла бы увидеть, что после исключения Бори на первом месте остальные позиции определяются однозначно.
На острове живут правдивцы, которые всегда говорят правду, и лжецы, которые всегда лгут. Житель произносит: «Я лжец». Проверим оба типа говорящего, потому что принятие одного варианта должно согласоваться с произнесённой фразой.
Ответ: в описанных условиях такое высказывание невозможно. Проверка обоих предположений показывает, что ни один тип говорящего не согласуется с правилом острова.
Пять городов соединены дорогами, и требуется выяснить, можно ли пройти по каждой дороге ровно один раз и вернуться в исходный город. Конкретный ответ зависит от того, какие именно пары городов соединены, поэтому сначала строят граф: города становятся вершинами, а дороги — рёбрами. Для проверки подсчитывают число дорог, выходящих из каждого города.
Ответ зависит от заданного списка дорог: без него нельзя сказать «да» или «нет». Граф даёт точный критерий проверки и позволяет обосновать вывод по структуре связей.
Начинать перебирать варианты, не выписав все условия, — значит рисковать забыть ограничение. Так происходит, когда решающий сразу держит весь текст в памяти и сосредоточивается на первом заметном факте. Проверьте себя: перед исключением варианта перечислите условия и отметьте, какое именно из них он нарушает.
Отсутствие сведений о связи не доказывает, что связи нет. Неизвестное значение иногда по ошибке принимают за запрещённое, особенно если в таблице пустую клетку мысленно считают ответом «нет». Разделяйте эти случаи отдельными пометками и объявляйте связь невозможной только при наличии основания в условии или выводе.
Вариант нельзя объявлять невозможным после проверки только одного условия, если остальные ещё не учтены. Эту ошибку допускают, когда найдено первое несоответствие и затем без проверки переносят вывод на похожие сочетания. Проверяйте каждый оставшийся вариант по всем условиям и записывайте причину каждого исключения.
Остановиться на первом найденном ответе — не значит доказать, что он единственный. Задача может допускать несколько решений, а иногда — не иметь ни одного. Чтобы проверить себя, продолжите анализ после первого подходящего варианта и выясните, остаются ли другие сочетания, удовлетворяющие всем ограничениям.
Для решения полезно различать истинные и ложные высказывания, понимать логические связки и аккуратно извлекать условия из текста. Табличное и графическое представления применяются при изучении алгоритмов, структур данных и компьютерного моделирования. Проверка вариантов связана с перебором и поиском решений в программировании: компьютер также получает ограничения и последовательно отбрасывает неподходящие варианты.
С чего начать решение логической задачи?
Выпишите объекты, возможные значения и каждое ограничение из условия. Затем выберите удобное представление и проверяйте варианты по всем ограничениям.
Когда удобнее составлять таблицу, а когда — граф?
Таблица удобна, когда нужно сопоставить несколько групп объектов и признаков. Граф выбирают, если условие описывает связи между объектами, например дороги между городами.
Как отличить неизвестную связь от запрещённой?
Связь запрещена только тогда, когда это следует из условия или уже доказано. Если данных о ней нет, отметьте её как неизвестную, а не как отсутствующую.
Что делать, если перебор вариантов становится слишком большим?
Сначала применяйте ограничения, чтобы отсечь невозможные варианты ещё до полного перебора. Можно также выбрать таблицу или граф и проверять следствия наиболее строгих условий.
Как проверить, что найденный ответ единственный?
Проверьте все варианты, которые не исключены условиями, или покажите, что каждый другой вариант приводит к противоречию. Если остаётся больше одного допустимого варианта, решение не единственное.
§ 25. Логические задачи
