Алгебра логики. Обработка математических выражений
Теория к заданию 15 из ЕГЭ по информатике
Тождественные преобразования логических выражений
В алгебре логики выполняются основные законы, позволяющие производить тождественные преобразования логических выражений.
| Закон | Для ∨ | Для ∧ |
| Переместительный | A ∨ B = B ∨ A | A ∧ B = B ∧ A |
| Сочетательный | A ∨ (B ∨ C) = (B ∨ A) ∨ C | A ∧ (B ∧ C) = (A ∧ B) ∧ C |
| Распределительный | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C) | A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C) |
| Правила де Моргана | ${A ∨ B}↖{-}$ = $A↖{-} ∧ B↖{-}$ | ${A ∧ B}↖{-}$ = $A↖{-} ∨ B↖{-}$ |
| Идемпотенции | A ∨ A = A | A ∧ A = A |
| Поглощения | A ∨ A ∧ B = A | A ∧ (A ∨ B) = A |
| Склеивания | (A ∧ B) ∨ (A↖{-} ∧ B) = B | (A ∨ B) ∧ (A↖{-} ∨ B) = B |
| Операция переменной с ее инверсией | $A ∨ A↖{-}$ = 1 | $A ∧ A↖{-}$ = 0 |
| Операция с константами | A ∨ 0 = A A ∨ 1 = 1 |
A ∧ 1 = A A ∧ 0 = 0 |
| Двойного отрицания | $A↖{=}$ = A | |
Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.
Равносильные преобразования логических формул имеют то же назначение, что и преобразования формул в обычной алгебре. Они служат для упрощения формул или приведения их к определенному виду путем использования основных законов алгебры логики. Под упрощением формулы, не содержащей операций импликации и эквивалентности, понимают равносильное преобразование, приводящее к формуле, которая содержит либо меньшее по сравнению с исходной число операций, либо меньшее число переменных.
Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т. п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).
Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:
1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .
Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.
2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .
Здесь для упрощения применяется закон поглощения.
3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .
При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой
Примеры решения задач
Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .
Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .
Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .
Ответ: A ∧ B ∧ ¬C.
Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.
Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».
1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;
2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;
3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».
Ответ: А — истина, В — ложь, С — истина.
Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35 < X · X) → (X < (X - 3)) ?
Решение. Запишем таблицу истинности для операции импликации:
| A | B | A → B |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 1 |
Выражение X < (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.
Ответ: X = 5.
