Законы алгебры логики и упрощение выражений

В этой статье вы сможете узнать:

• какие основные законы алгебры логики используются для преобразования выражений;
• как заменить импликацию и эквивалентность через отрицание, конъюнкцию и дизъюнкцию;
• как пошагово упростить сложное логическое выражение.

Основные законы алгебры логики

Закон двойного отрицания:

$\overline{\overline{A}} = A$

Переместительный (коммутативный) закон:

$A \wedge B = B \wedge A, \qquad A \vee B = B \vee A$

Сочетательный (ассоциативный) закон:

$(A \wedge B) \wedge C = A \wedge (B \wedge C), \qquad (A \vee B) \vee C = A \vee (B \vee C)$

Распределительный (дистрибутивный) закон:

$A \wedge (B \vee C) = (A \wedge B) \vee (A \wedge C)$ $A \vee (B \wedge C) = (A \vee B) \wedge (A \vee C)$

Законы де Моргана:

$\overline{A \wedge B} = \overline{A} \vee \overline{B}$ $\overline{A \vee B} = \overline{A} \wedge \overline{B}$

Законы идемпотентности:

$A \wedge A = A, \qquad A \vee A = A$

Законы поглощения:

$A \wedge (A \vee B) = A, \qquad A \vee (A \wedge B) = A$

Законы исключённого третьего и противоречия:

$A \vee \overline{A} = 1, \qquad A \wedge \overline{A} = 0$

Действия с константами:

$A \wedge 1 = A, \quad A \wedge 0 = 0, \quad A \vee 1 = 1, \quad A \vee 0 = A$

Выражение импликации и эквивалентности через базовые операции

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

Импликация:

$A \rightarrow B = \overline{A} \vee B$

Эквивалентность:

$A \leftrightarrow B = (\overline{A} \vee B) \wedge (\overline{B} \vee A) = (A \wedge B) \vee (\overline{A} \wedge \overline{B})$

Эти тождества можно доказать, сравнив таблицы истинности обеих частей равенства — они совпадают для всех комбинаций значений $A$ и $B$.

Порядок упрощения логического выражения

Упрощение обычно происходит в несколько этапов: сначала избавляются от импликации и эквивалентности (заменяя их через отрицание, конъюнкцию и дизъюнкцию), затем применяют законы де Моргана, чтобы «занести» отрицание внутрь скобок, а затем применяют законы поглощения, дистрибутивности и другие тождества для сокращения выражения.

Примеры решения

Пример 1. Упростите выражение $\overline{A} \vee (A \wedge B)$.

По распределительному закону раскладываем дизъюнкцию:

$\overline{A} \vee (A \wedge B) = (\overline{A} \vee A) \wedge (\overline{A} \vee B) = 1 \wedge (\overline{A} \vee B) = \overline{A} \vee B$

Ответ: $\overline{A} \vee B$.

Пример 2. Упростите выражение $\overline{A \wedge B} \vee \overline{A \vee B}$.

Применяем законы де Моргана к каждому слагаемому:

$\overline{A \wedge B} = \overline{A} \vee \overline{B}, \qquad \overline{A \vee B} = \overline{A} \wedge \overline{B}$

Получаем:

$(\overline{A} \vee \overline{B}) \vee (\overline{A} \wedge \overline{B})$

По закону поглощения ($X \vee (X \wedge Y) = X$, где $X = \overline{A} \vee \overline{B}$ поглощает второе слагаемое, так как $\overline{A} \wedge \overline{B}$ влечёт $\overline{A} \vee \overline{B}$):

Ответ: $\overline{A} \vee \overline{B}$.

Пример 3. Упростите выражение $A \rightarrow (B \rightarrow A)$.

Заменяем импликации: $B \rightarrow A = \overline{B} \vee A$.

$A \rightarrow (\overline{B} \vee A) = \overline{A} \vee \overline{B} \vee A = (\overline{A} \vee A) \vee \overline{B} = 1 \vee \overline{B} = 1$

Ответ: выражение тождественно истинно (равно 1 при любых значениях $A$ и $B$).

Алгоритм упрощения логического выражения

1. Замените все импликации и эквивалентности через отрицание, конъюнкцию и дизъюнкцию по соответствующим тождествам.
2. Примените законы де Моргана, чтобы перенести отрицание внутрь скобок и получить отрицания только над отдельными переменными.
3. Раскройте скобки, используя распределительный закон, если это упрощает структуру выражения.
4. Найдите одинаковые или взаимно исключающие подвыражения и примените законы идемпотентности, поглощения, исключённого третьего или противоречия.
5. Упростите оставшиеся действия с константами (0 и 1), пока выражение не станет минимальным.

Часто задаваемые вопросы

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

Как запомнить законы де Моргана и не перепутать, куда меняется знак операции? Полезно запомнить правило: «отрицание конъюнкции — это дизъюнкция отрицаний, отрицание дизъюнкции — это конъюнкция отрицаний» — при переносе отрицания через скобку операция внутри меняется на противоположную (И на ИЛИ или ИЛИ на И).

Всегда ли нужно сначала избавляться от импликации, а потом уже упрощать выражение? Не обязательно строго в этом порядке, но обычно удобнее сначала выразить всё через отрицание, конъюнкцию и дизъюнкцию, потому что для этих трёх операций существует больше готовых законов упрощения (де Моргана, дистрибутивность, поглощение), чем для импликации и эквивалентности напрямую.

Как проверить правильность упрощения логического выражения? Нужно построить таблицы истинности для исходного и упрощённого выражений и сравнить их: если значения совпадают для всех комбинаций переменных, упрощение выполнено верно.

Похожие темы для изучения

• Логические операции и таблицы истинности
• Таблицы истинности и логические схемы
• Основы программирования на Python: переменные, ветвления, циклы
• Кодирование и измерение информации

Задачи для самостоятельного решения

1. Упростите выражение $A \vee (\overline{A} \wedge B)$.
2. Упростите выражение $\overline{A \vee B} \wedge \overline{A \vee \overline{B}}$.
3. Докажите с помощью законов алгебры логики, что $A \wedge (A \vee B) = A$.
4. Упростите выражение $(A \rightarrow B) \wedge (B \rightarrow A)$ и сравните результат с выражением эквивалентности.
5. Упростите выражение $\overline{A} \wedge \overline{B} \wedge \overline{C} \vee A$.
6. Определите, является ли выражение $A \wedge \overline{A} \vee B$ тождественно равным просто $B$.