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

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

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

Формальный способ решения логических задач

1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

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

3. Составить единое логическое выражение для всех тре­бований задачи.

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

1. Выбрать решение — набор значений простых выска­зываний, при котором построенное логическое выра­жение является истинным.

5. Проверить, удовлетворяет ли полученное решение условию задачи.

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

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

Задача «Уроки логики». На вопрос, кто из трех учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и вто­рой, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

Решение. Введём обозначения:

• Р₁ – первый учащийся изучал логику;

• Р₂ – второй учащийся изучал логику;

• Р₃ – третий учащийся изучал логику.

Из условия задачи следует истинность высказывания . Воспользуемся соотношением (20) и упростим исходное высказывание:

.

Высказывание (согласно (11)), а, следовательно, ложно и высказывание . Поэтому должно быть истинным высказывание .

Ответ. Логику изучал третий учащийся, а первый и второй не изучали.

Задача «Прогноз». Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

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

Решение. Введем обозначения для логических высказываний:

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

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

Зафиксируем высказывания каждого из друзей:

Джон: ,Ник: , Питер: .

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

=1.

Упростим это выражение. Используя (11), установим, что первые два слагаемые тождественно-ложные. Тогда, с учётом формул де Моргана для третьего слагаемого:

Произведение будет истинным только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.