§ 33. Решение логических задач средствами математической логики

Определения и обозначения

Логическое высказывание — повествовательное предложение, которому можно однозначно присвоить значение «истина» или «ложь». Например, фраза «Снег белый» является высказыванием, а вопрос высказыванием не считается. Это понятие позволяет заменить длинное условие задачи коротким обозначением.

Логическая переменная — переменная, принимающая только два значения: 1 («истина») или 0 («ложь»). Обычно её обозначают заглавной буквой: A, B, C. Переменная нужна, чтобы описывать неизвестные обстоятельства и перебирать все возможные варианты.

Логическая формула — выражение, составленное из логических переменных, операций и скобок; его значение зависит от значений переменных. Например, A ∧ ¬B означает «A и не B». Формула переводит словесное условие на точный язык, с которым можно выполнять вычисления.

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

Как это устроено

Сначала из текста выделяют простые высказывания, которые нельзя дальше разделить без потери смысла. Каждому присваивают свою переменную: например, A — «Анна дежурила», B — «Борис дежурил». Затем находят слова, связывающие эти высказывания, и переводят их в логические операции.

Слова «и», «или», «не», «если… то…» и «тогда и только тогда» задают разные отношения между высказываниями. «И» требует одновременной истинности, «или» допускает истинность хотя бы одного условия, а «не» меняет значение на противоположное. Импликация A → B выражает условную связь, а эквиваленция A ↔ B требует совпадения двух значений.

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

Таблица истинности перечисляет все наборы значений переменных и вычисляет формулу для каждого набора. Для n переменных будет 2ⁿ строк, поскольку каждая переменная может быть равна 0 или 1. Строки, в которых итог равен 1, соответствуют допустимым решениям задачи.

Иногда формулу быстрее упростить равносильными преобразованиями, например раскрыть импликацию: A → B равносильно ¬A ∨ B. После упрощения находят значения переменных, при которых формула истинна. Последний шаг — подставить их в исходное условие и убедиться, что смысл задачи не был искажён.

Основные логические операции и их использование при составлении формул

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

Разбор задач

Рыцари и лжецы

Обозначим A — «А рыцарь», B — «Б рыцарь». Высказывание А имеет вид A ∧ B, а высказывание Б — ¬A. Слова рыцарь говорит правду, лжец говорит неправду, поэтому проверим все значения A и B.

1. При A = 1, B = 1 реплика А истинна, но реплика Б «А — лжец» ложна, поэтому Б не может быть рыцарем.
2. При A = 1, B = 0 реплика А ложна, хотя А — рыцарь, что невозможно.
3. При A = 0, B = 1 реплика А ложна, а реплика Б истинна, что соответствует типам говорящих.
4. При A = 0, B = 0 реплика А истинна, хотя А — лжец, что невозможно.

Ответ: А — лжец, Б — рыцарь. Проверка показывает, что обе реплики при этом согласуются с правилами острова.

Кто дежурил

Пусть A, B и C означают, что дежурили соответственно Анна, Борис и Виктор. По условию ровно одно из A, B, C истинно. Реплики имеют значения B, ¬B и ¬A, причём истинным должно быть ровно одно из этих трёх высказываний.

1. Если дежурила Анна, то B = 0, поэтому реплика Анны ложна, реплика Бориса истинна, а реплика Виктора ложна.
2. Если дежурил Борис, то B = 1: реплика Анны истинна, реплика Бориса ложна, но реплика Виктора тоже истинна, так как A = 0.
3. Если дежурил Виктор, то B = 0 и A = 0: реплики Бориса и Виктора истинны, поэтому условие единственности нарушается.

Ответ: дежурила Анна. Только в этом случае ровно одна реплика оказывается истинной.

Отношения между объектами

Пусть A означает «A слева от B», B — «B слева от C», а C — «C справа от D». Тогда условия записываются как A → C, A ↔ B и ¬C. Нужно найти значения переменных, при которых истинны все ограничения одновременно.

1. Из ¬C следует C = 0, то есть C находится не справа от D.
2. Импликация A → C при C = 0 может быть истинной только при A = 0, потому что случай A = 1, C = 0 запрещён.
3. Из A ↔ B и A = 0 получаем B = 0.
4. Итак, согласованный набор: A = 0, B = 0, C = 0.

Ответ: A не находится слева от B, B не находится слева от C, а C не находится справа от D. Другие сочетания нарушают хотя бы одно исходное ограничение.

Типичные ошибки

Ошибка — считать высказыванием любое предложение. Вопросы, команды и фразы с неизвестной истинностью нельзя сразу обозначать переменными. Проверьте, можно ли для предложения однозначно выбрать 0 или 1.

Ошибка — понимать «или» только как исключающее «либо… либо». В математической логике A ∨ B истинно и при A = 1, B = 1, потому что достаточно хотя бы одного истинного условия. Сверяйтесь с таблицей дизъюнкции.

Ошибка — заменять A → B требованием истинности A и B. Импликация утверждает связь: она ложна лишь при истинном A и ложном B. Для самопроверки переберите четыре пары значений.

Ошибка — записывать длинную формулу без скобок или нарушать порядок операций. Тогда программа или таблица может вычислить уже другое условие. Разделите формулу на смысловые части и проговорите каждую скобочную группу словами.

Связь с другими темами

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

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

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

Что запомнить

• Каждое простое высказывание обозначают отдельной логической переменной.
• Условия «и» соединяются конъюнкцией, а альтернативные варианты — дизъюнкцией.
• Скобки в логической формуле задают структуру и порядок рассуждения.
• Решение задачи — это набор значений переменных, при котором формула истинна.
• Таблица истинности позволяет проверить формулу при всех возможных наборах значений.
• Равносильные преобразования не изменяют множество решений задачи.
• Полученный ответ необходимо проверить по исходному условию, а не только по преобразованной формуле.