Логические приёмы решения задач
Логические задачи решают не угадыванием, а последовательным преобразованием условий. Основные приёмы: перевод текста в формулы, упрощение выражений, разбор случаев, поиск противоречий и проверка найденного решения. Перед изучением темы полезно повторить формулы логики, законы логики и метод перебора.
1. Перевод условия на язык логики
Сначала выделяют простые высказывания и обозначают их буквами. Например, \(A\) — «число делится на 2», \(B\) — «число делится на 3». Затем словесные связки заменяют логическими операциями: «не» — отрицанием, «и» — конъюнкцией, «или» — дизъюнкцией, «если..., то...» — импликацией, «тогда и только тогда» — эквивалентностью.
Высказывание — предложение, которое имеет ровно одно значение истинности: истина или ложь. Логическая формула строится из высказываний с помощью связок. Например, \(A\land\neg B\) означает: \(A\) истинно, а \(B\) ложно.
Важно различать «или» в обычной логике и в разговорной речи. Логическое «или» означает, что истинно хотя бы одно из высказываний, в том числе оба. Условие «ровно одно из \(A\) и \(B\)» записывают отдельно: \((A\lor B)\land\neg(A\land B)\).
Импликация ложна только в одном случае: \(A\) истинно, а \(B\) ложно. Поэтому условие «если \(A\), то \(B\)» не запрещает ситуацию, когда \(A\) ложно.
2. Упрощение логических выражений
Упрощение уменьшает число операций и помогает увидеть структуру задачи. Сначала убирают импликации и эквивалентности, затем применяют законы логики, раскрывают скобки и собирают одинаковые части. Если выражение содержит много переменных, полезно временно обозначить повторяющиеся фрагменты одной буквой.
Двойное отрицание не меняет значение: \(\neg\neg A=A\). При отрицании составного высказывания связка меняется на противоположную: «не (\(A\) и \(B\))» превращается в «не \(A\) или не \(B\)», а «не (\(A\) или \(B\))» — в «не \(A\) и не \(B\)».
При работе со скобками сохраняйте приоритет операций: сначала выполняется отрицание, затем конъюнкция, затем дизъюнкция, после неё импликация и эквивалентность. Если порядок может быть неясен, ставьте скобки явно.
Для выражений вида \((A\land B)\lor(A\land C)\) вынесите \(A\): \((A\land B)\lor(A\land C)=A\land(B\lor C)\). Этот приём часто превращает длинное условие в короткое и показывает, какое требование является обязательным.
3. Поиск противоречий
Противоречие возникает, когда из условий следует одновременно некоторое высказывание и его отрицание. Тогда рассматриваемая ветвь невозможна. В задачах на перебор это позволяет сразу отбросить большую часть вариантов.
Удобный алгоритм: выберите предположение, последовательно подставьте его в условия, упростите полученные формулы и проверьте, не получилось ли \(0\). Если получен ноль, предположение ложно. Если получена единица, ветвь удовлетворяет проверенным условиям, но остальные условия всё равно нужно проверить.
Какое выражение эквивалентно формуле \(\neg(A\lor B)\)?
Ещё один вариант — доказательство от противного. Предполагают, что искомое утверждение неверно, и показывают, что это приводит к несовместимым требованиям. Такой подход особенно полезен для задач с формулировками «невозможно», «обязательно» и «единственный вариант».
Нельзя считать всю задачу противоречивой только потому, что \(A\land\neg A\) встретилось внутри одной проверяемой ветви. Это означает невозможность именно этой ветви. В других ветвях значение \(A\) может быть другим.
4. Разбор случаев и таблица истинности
Если неизвестно значение ключевого высказывания, рассмотрите два случая: \(A=0\) и \(A=1\). После подстановки каждая ветвь обычно упрощается. Если переменных немного, можно использовать таблицу истинности; если их много, выбирают переменную, которая встречается чаще или влияет на самое строгое условие.
| \(A\) | \(B\) | \(A\Rightarrow B\) | \(A\land B\) |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Для любой формулы \(F(A,\ldots)\) справедливо: \(F=(\neg A\land F|_{A=0})\lor(A\land F|_{A=1})\). Практически это означает: достаточно разобрать оба значения выбранной переменной, не пропуская ни одной ветви.
5. Разобранный пример
Пусть \(A\), \(B\) и \(C\) — высказывания. Требуется найти все наборы значений, при которых истинно условие \(F=(A\Rightarrow B)\land(B\Rightarrow C)\land A\land\neg C\).
В формуле есть цепочка импликаций и одновременно требования \(A=1\), \(C=0\). Проверим, остаётся ли хотя бы один набор.
Следовательно, подходящих наборов нет. Содержательно причина такова: из \(A\) следует \(B\), из \(B\) следует \(C\), но условие одновременно требует \(\neg C\).
6. Логика множеств и практический алгоритм
В задачах с объектами, свойствами и группами удобно перейти от высказываний к множествам. Принадлежность объекту множеству записывают через принадлежность множеству, пересечение соответствует «и», объединение — «или», дополнение — отрицанию. Для наглядного анализа помогают диаграммы Венна и круги Эйлера и операции множеств.
Если требуется посчитать объекты, применяют подсчёт по диаграмме Венна. Условия «принадлежит ровно одному из множеств» связаны с симметрической разностью множеств. При сопоставлении групп удобно составить таблицу соответствия множеств.
- Выпишите простые высказывания и обозначьте их буквами.
- Переведите все словесные связки в формулу, расставьте скобки.
- Уберите импликации, эквивалентности и лишние отрицания.
- Упростите выражение законами логики или разбейте решение на случаи.
- Отбросьте ветви с противоречиями.
- Проверьте оставшиеся наборы подстановкой в исходное условие.
Не путайте импликацию с равенством: \(A\Rightarrow B\) не означает \(B\Rightarrow A\). Не заменяйте «или» на «ровно одно». При отрицании скобок меняйте связку по законам де Моргана. После упрощения обязательно проверяйте результат в исходной, а не только в преобразованной формуле.
Проверь себя
Главное
- Переводите текст в формулу, заранее определив простые высказывания и смысл связок.
- Убирайте импликации, применяйте законы логики и следите за приоритетом операций.
- Противоречие \(A\land\neg A\) делает невозможной текущую ветвь, но не обязательно всю задачу.
- При неизвестной переменной разбирайте случаи \(0\) и \(1\); после решения проверяйте его в исходном условии.
- Для задач о группах и свойствах используйте операции множеств, диаграммы и таблицы соответствия.