Преобразование логических выражений
Преобразование логических выражений — это замена формулы на более простую, но равносильную ей формулу. Такие логические приемы помогают уменьшить число операций, проверить условие задачи и получить выражение, удобное для дальнейшего решения заданий ege-15 и ege-23.
Перед началом полезно повторить законы логики и понятие равносильных логических выражений. Равносильные выражения принимают одинаковые значения при любых наборах значений входящих в них переменных.
Основные понятия и порядок действий
Логическое выражение — это запись, составленная из логических переменных, констант \(0\) и \(1\), скобок и логических операций. Значение выражения также равно \(0\) или \(1\).
Если две формулы имеют одинаковые значения на всех наборах переменных, их можно заменить друг на друга. При преобразовании нельзя менять порядок действий так, чтобы изменился смысл формулы.
В школьных задачах используются операции: отрицание \(\neg A\), конъюнкция \(A \land B\) («И»), дизъюнкция \(A \lor B\) («ИЛИ»), импликация \(A \to B\) и эквивалентность \(A \leftrightarrow B\). Сначала обычно устраняют импликации и эквивалентности, затем раскрывают отрицания, применяют законы логики и собирают одинаковые части.
- Выделите скобки и определите главную операцию выражения.
- Замените импликации и эквивалентности известными формулами.
- Примените законы де Моргана к отрицаниям сложных выражений.
- Уберите повторения, константы и противоположные части.
- Проверьте результат преобразованием или таблицей истинности.
Подробные приёмы для двух последних операций разобраны на страницах преобразования импликации и преобразования эквивалентности. Внутри текущей темы они нужны как первый этап упрощения.
Законы, которые чаще всего применяют
Законы логики позволяют заменять фрагменты формулы без построения полной таблицы истинности. Важно узнавать не только точное совпадение, но и выражение, записанное в другом порядке: конъюнкция и дизъюнкция обладают переместительным и сочетательным свойствами.
Конъюнкция распределяется относительно дизъюнкции: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\). Дизъюнкция также распределяется относительно конъюнкции: \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\).
Две последние формулы называются законами поглощения. Они особенно полезны, когда один фрагмент выражения содержится в другом. Законы нуля и единицы собраны также на странице законы нуля и единицы, а повторяющиеся части — на странице закон идемпотентности.
Фрагменты \(A \lor \neg A\) и \(A \land \neg A\) дают соответственно \(1\) и \(0\). Повторение \(A \lor A\) или \(A \land A\) сокращается до \(A\). Если выражение содержит скобку вида \(A \land (A \lor B)\) или \(A \lor (A \land B)\), применяйте поглощение.
Разобранный пример
Упростим выражение \(F=(A \to B) \land (A \to \neg B)\). Такой пример показывает, как последовательно устранить импликации и найти общий фрагмент.
Итак, \((A \to B) \land (A \to \neg B) \equiv \neg A\). Смысл результата: обе импликации одновременно истинны именно тогда, когда \(A\) ложно. При истинном \(A\) одна из частей \(B\) или \(\neg B\) обязательно окажется ложной.
Во что упрощается выражение \(A \lor (A \land B)\)?
Практические логические приёмы
- Вынесение общего множителя: \((A\land B)\lor(A\land C)\equiv A\land(B\lor C)\).
- Группировка противоположных частей: \(A\land B\lor A\land\neg B\equiv A\land(B\lor\neg B)\equiv A\).
- Добавление полезной единицы: иногда выражение удобно умножить на \(B\lor\neg B\), потому что эта скобка равна \(1\).
- Добавление полезного нуля: можно использовать \(B\land\neg B\equiv0\), если это помогает сгруппировать слагаемые.
- Смена порядка: переставляйте части конъюнкции или дизъюнкции, чтобы одинаковые множители оказались рядом.
Например, \(A\land B\lor A\land\neg B\) преобразуется так: \(A\land(B\lor\neg B)=A\land1=A\). Это аналог вынесения общего множителя в обычной алгебре. Однако знак \(\lor\) нельзя механически считать сложением, а знак \(\land\) — умножением: сначала нужно убедиться, что применяется настоящий закон логики.
Отметьте повторяющиеся блоки буквами \(X\), \(Y\), \(Z\). Сначала упростите крупные скобки, затем верните исходные выражения. Такой приём уменьшает риск потерять отрицание или перепутать границы скобок.
Как проверить результат
Быстрая проверка — снова применить законы и убедиться, что каждый переход равносилен. Если сомнение осталось, используйте таблицу истинности. Для \(n\) переменных потребуется \(2^n\) строк. В каждой строке вычисляют исходную и полученную формулы и сравнивают последние столбцы.
Таблица особенно полезна для небольшого числа переменных. Для четырёх и более переменных она становится длинной, поэтому сначала лучше максимально упростить выражение. Подробнее способ описан на странице проверка равносильности таблицей истинности.
| A | B | \(A\lor B\) | \(\neg(\neg A\land\neg B)\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
В таблице оба последних столбца совпадают во всех строках, поэтому \(A\lor B\equiv\neg(\neg A\land\neg B)\). Это один из законов де Моргана, записанный в обратную сторону. Отрицание сложного высказывания требует особой аккуратности: при переходе через скобки меняется операция и отрицается каждый элемент. См. отрицание сложного высказывания.
1. Нельзя раскрывать отрицание скобки только у первого элемента: \(\neg(A\lor B)\) — это не \(\neg A\lor B\), а \(\neg A\land\neg B\). 2. Нельзя сокращать разные переменные: \(A\lor B\) не равно \(A\). 3. Нельзя считать \(A\to B\) равной \(A\lor B\); правильная замена — \(\neg A\lor B\). 4. Нельзя забывать скобки при смешении операций. 5. Совпадение на одном наборе значений не доказывает равносильность.
От упрощения к минимальной формуле
После преобразований получают формулу с меньшим числом операций или переменных. Это не всегда единственная возможная запись: разные равносильные формулы могут иметь одинаковую сложность. Если требуется найти наиболее короткий вариант, переходите к странице минимальное логическое выражение.
В задачах на построение формулы по условию сначала переводят слова в логические операции, а уже потом упрощают. Для такого перевода полезна страница построение логического выражения по условию. Отдельно следите за законом исключённого третьего: \(A\lor\neg A\equiv1\).
Финальная проверка
Главное
- Сначала устраняйте импликации и эквивалентности, затем раскрывайте отрицания и применяйте законы логики.
- Запомните законы нуля и единицы, идемпотентности, двойного отрицания, де Моргана, поглощения и исключённого третьего.
- Ищите одинаковые фрагменты, противоположные пары и общий множитель; порядок частей можно менять по переместительному закону.
- Результат проверяют повторным преобразованием или таблицей истинности: последние столбцы должны совпасть во всех строках.