§ 20. Преобразование логических выражений

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

Логическое выражение — запись из логических переменных, значений «истина» и «ложь» и логических операций, например отрицания ¬, конъюнкции ∧ и дизъюнкции ∨. Когда значения переменных заданы, выражение тоже получает одно из двух значений: истина или ложь. Например, если A истинно, то ¬A ложно. Это понятие нужно, чтобы описывать и вычислять логические условия.

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

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

Закон де Моргана связывает отрицание выражения в скобках с отрицаниями его частей: ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B. При переносе отрицания внутрь скобок меняется операция между частями, а отрицание относится к каждой из них. Скобки показывают, к какому целому выражению относилось исходное отрицание. Закон полезен, когда нужно раскрыть отрицание или привести формулу к удобному виду.

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

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

Переместительный закон разрешает менять местами части, соединённые одной операцией: A ∧ B = B ∧ A и A ∨ B = B ∨ A. Сочетательный закон меняет группировку одинаковых операций, например (A ∨ B) ∨ C = A ∨ (B ∨ C). Распределительный закон позволяет раскрывать скобки или выносить общий множитель: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C). Эти законы можно проверить таблицами истинности: в каждой строке левые и правые части дают одинаковое значение. При этом правила для ∧ и ∨ нельзя произвольно смешивать.

Двойное отрицание устраняется по правилу ¬¬A = A: два последовательных отрицания возвращают исходное значение. Закон поглощения, например A ∨ (A ∧ B) = A, позволяет убрать часть, которая не меняет результат. Закон исключённого третьего A ∨ ¬A = 1 говорит, что одно из двух противоположных высказываний обязательно истинно; для конъюнкции A ∧ ¬A = 0 означает противоречие. Эти правила сокращают формулы, удаляя повторные или заведомо лишние условия.

По законам де Моргана отрицание сложного выражения раскрывают так, чтобы оно относилось к каждой части скобок. При этом ∧ заменяют на ∨, а ∨ — на ∧: например, ¬(A ∧ B) становится ¬A ∨ ¬B. Причина такой замены в том, что отрицание «оба истинны» означает «хотя бы одно ложно», а отрицание «хотя бы одно истинно» означает «оба ложны». Нельзя оставить прежнюю операцию или забыть отрицание у одной из частей.

Импликация заменяется формулой A → B = ¬A ∨ B, а эквивалентность — формулой A ↔ B = (A ∧ B) ∨ (¬A ∧ ¬B). Первая запись показывает, что импликация ложна только при истинном A и ложном B; вторая — что эквивалентность истинна, когда значения частей совпадают. После замены можно применять распределение, де Моргана и другие законы. Такой порядок переводит выражение к операциям, для которых проще выполнять преобразования.

Основные равносильности и их применение

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

Разбор задач

Задача 1. Преобразовать ¬(A ∧ B) в равносильное выражение. Отрицание относится ко всему выражению в скобках, поэтому подходит закон де Моргана. При его применении конъюнкция меняется на дизъюнкцию, а отрицание ставится перед каждым операндом. Здесь важно не оставить без отрицания ни A, ни B.

1. Запишем исходную формулу: ¬(A ∧ B).
2. Заменим конъюнкцию между A и B на дизъюнкцию.
3. Поставим отрицание перед обеими переменными: ¬A ∨ ¬B.

Ответ: ¬(A ∧ B) = ¬A ∨ ¬B.

Задача 2. Упростить (A ∨ B) ∧ (A ∨ ¬B). В обеих скобках есть общий операнд A, а остальные части соединены с ним дизъюнкцией. Распределительный закон позволяет вынести A, после чего выражение B ∨ ¬B превращается в истину. Тогда остаётся выражение вида A ∧ 1, которое упрощается до A.

1. Применим распределительный закон: (A ∨ B) ∧ (A ∨ ¬B) = A ∨ (B ∧ ¬B).
2. Проверим части в скобках: B ∧ ¬B = 0, поскольку переменная и её отрицание не могут быть истинными одновременно.
3. Получим A ∨ 0 = A, так как дизъюнкция с ложью сохраняет значение A.

Ответ: A. В исходном задании можно также сгруппировать формулу как (A ∨ B) ∧ (A ∨ ¬B): здесь при правильном применении распределения результат равен A ∨ (B ∧ ¬B), а не выражению с B ∨ ¬B. Следовательно, результат упрощения — A.

Задача 3. Упростить (A → B) ∧ (A → ¬B). Сначала заменим импликации, чтобы работать только с отрицанием, конъюнкцией и дизъюнкцией. Обе части содержат условие ¬A, а при истинном A требования B и ¬B одновременно выполнить нельзя. Распределение выделяет эти два случая и показывает, что остаётся только ¬A.

1. Заменим импликации: (¬A ∨ B) ∧ (¬A ∨ ¬B).
2. Применим распределительный закон: ¬A ∨ (B ∧ ¬B).
3. По закону противоречия B ∧ ¬B = 0, поэтому получаем ¬A ∨ 0.
4. Упростим дизъюнкцию: ¬A ∨ 0 = ¬A.

Ответ: ¬A. Если A ложно, обе импликации истинны; если A истинно, B и ¬B не могут быть истинны одновременно.

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

При применении закона де Моргана иногда меняют знак отрицания, но оставляют прежнюю операцию в скобках. Так происходит, когда правило запоминают как простое «раскрытие скобок» и упускают вторую часть. Нужно одновременно отрицать каждый операнд и менять ∧ на ∨ или ∨ на ∧. Для проверки подставьте, например, A = 1 и B = 1: левая и правая части должны совпасть.

Переместительный и сочетательный законы не разрешают произвольно менять операции. Они действуют отдельно для конъюнкции и отдельно для дизъюнкции, поэтому из A ∧ B нельзя получить A ∨ B перестановкой частей. Ошибку допускают, когда воспринимают символы операций как взаимозаменяемые. Проверяйте, что операция по обе стороны равносильности одна и та же.

При поглощении нельзя удалять произвольную часть выражения: для A ∨ (A ∧ B) результат равен A, а не B. Закон работает, потому что A уже делает дизъюнкцию истинной, а если A ложно, выражение A ∧ B тоже ложно. Ошибка возникает, когда замечают скобки, но не проверяют наличие повторяющегося операнда. Сверьте формулу с полной записью закона перед сокращением.

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

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

Для работы с логическими выражениями нужно знать переменные, значения «истина» и «ложь», а также операции отрицания, конъюнкции, дизъюнкции и импликации. Они образуют основу формул, которые затем можно преобразовывать. Если забыть смысл операции, легко неверно прочитать условие.

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

Преобразование логических выражений полезно при составлении условий в программах. Упрощённое условие легче читать, проверять и исправлять. При этом оно должно сохранять поведение программы для каждого возможного набора входных данных.

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

• Равносильные выражения дают одинаковый результат при любых значениях переменных.
• Преобразование не меняет значения выражения, а только его форму.
• При переносе отрицания через скобки по законам де Моргана конъюнкция и дизъюнкция меняются местами.
• Двойное отрицание устраняется: ¬¬A = A.
• Импликацию можно заменить выражением ¬A ∨ B.
• Результат преобразования можно проверить таблицей истинности.