§ 3. Равносильные преобразования. Законы алгебры логики

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

Логическое выражение — выражение из логических переменных, значений и операций, которому при каждом наборе значений переменных соответствует истинность или ложность. Переменная принимает значение 0 или 1, а операции НЕ, И и ИЛИ задают, как получить общий результат. Понятие нужно, чтобы точно записывать условия и рассуждать о них.

Равносильные логические выражения — выражения, принимающие одинаковые значения истинности при любых одинаковых значениях переменных. Например, для одних и тех же A и B их результаты должны совпадать при всех возможных сочетаниях 0 и 1. Это позволяет заменять одну запись другой без изменения смысла.

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

Законы алгебры логики — правила, позволяющие преобразовывать логические выражения и доказывать их равносильность. В формулах A и B обозначают логические переменные или целые выражения, а ¬ означает отрицание. Законы дают обоснование каждому шагу упрощения.

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

Чтобы проверить равносильность двух выражений, сравнивают их значения на всех наборах переменных. Для двух переменных существуют четыре набора: 00, 01, 10 и 11, поэтому достаточно вычислить результаты для каждого из них. Если хотя бы в одной строке результаты различаются, выражения не равносильны. Если совпадают во всех строках, проверка завершена для всех возможных случаев.

Коммутативность объясняет, почему в конъюнкции и дизъюнкции можно менять операнды местами: результат зависит от значений, а не от порядка записи. Ассоциативность позволяет иначе расставлять скобки в цепочке одинаковых операций, потому что способ группировки не влияет на итог. Например, при вычислении A ∧ B ∧ C можно сначала объединить A и B или B и C. Это удобно, когда нужно сгруппировать части формулы для дальнейшего преобразования.

Идемпотентность показывает, что повторение одного и того же операнда не меняет результат: A ∧ A = A и A ∨ A = A. Нейтральный элемент тоже не влияет на результат: для И это 1, а для ИЛИ — 0. Поглощающий элемент, напротив, сразу определяет итог: A ∧ 0 всегда равно 0, а A ∨ 1 всегда равно 1. Эти правила сокращают выражения, в которых встречаются повторы или константы.

Законы дополнения описывают два противоположных случая: A и ¬A не могут быть истинны одновременно, но одно из них обязательно истинно. Поэтому их конъюнкция равна 0, а дизъюнкция — 1. Закон двойного отрицания говорит, что два знака НЕ подряд возвращают исходное значение: ¬¬A = A. Он помогает убирать лишние отрицания, не изменяя смысл формулы.

Распределительные законы позволяют раскрыть скобки или, наоборот, собрать несколько частей выражения в общую группу. Законы де Моргана нужны, когда отрицание стоит перед скобками: отрицание распространяется на каждый операнд, а И и ИЛИ меняются местами. Это следует из смысла операций: чтобы отрицать условие «A и B», достаточно, чтобы не выполнялось хотя бы одно из них; чтобы отрицать «A или B», должны не выполняться оба. После любого такого шага новое выражение должно оставаться равносильным исходному.

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

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

Разбор задач

Задача 1. Упростите выражение A ∨ 0 ∨ A. Здесь есть нейтральный элемент дизъюнкции и два одинаковых операнда. Сначала удобно убрать константу, потому что она не влияет на дизъюнкцию. Затем можно сократить повторяющуюся переменную по закону идемпотентности.

1. В выражении A ∨ 0 ∨ A заменяем A ∨ 0 на A по закону нейтрального элемента: A ∨ A.
2. Применяем идемпотентность: A ∨ A = A.

Ответ: A. Выражение принимает то же значение, что и исходное, при любом значении переменной.

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

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

Ответ: A ∨ ¬B. Полученная запись равносильна исходной, так как каждый переход выполнен по закону алгебры логики.

Задача 3. Покажите, что выражения (A ∧ B) ∨ (A ∧ ¬B) и A равносильны. Чтобы доказать равносильность, преобразуем первое выражение и получим второе. В обоих слагаемых присутствует A, поэтому распределительный закон позволяет вынести его за скобки. Оставшуюся часть можно упростить с помощью закона дополнения.

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

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

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

Ошибка — раскрывать отрицание скобок, не меняя операцию между переменными. Так бывает, если запомнить только перенос знака ¬, но забыть вторую часть закона де Моргана. При отрицании конъюнкция становится дизъюнкцией, а дизъюнкция — конъюнкцией. Проверь преобразование на наборах значений или сверь сразу оба изменения: знак перед каждой переменной и операцию между ними.

Путаница с константами приводит к неверным упрощениям: ученик может считать, что для обеих операций нейтрально 0. Но конъюнкция с 0 всегда ложна, а дизъюнкция с 0 сохраняет значение второго операнда; нейтральный элемент для И — 1. Чтобы проверить себя, подставь A = 1 и отдельно A = 0 и сравни результат с предполагаемым упрощением.

Нельзя удалять переменную лишь потому, что она где-то повторяется в длинной формуле. Идемпотентность применяется к одинаковым операндам одной операции, например A ∨ A, а не к любым двум вхождениям A. Между ними могут стоять другие операции или отрицания, которые меняют смысл выражения. Перед сокращением проверь, что именно повторяется и образует ли оно подходящую пару.

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

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

Для работы с равносильными преобразованиями нужно знать значения операций НЕ, И и ИЛИ, а также отличать переменные от констант 0 и 1. Это связывает тему с таблицами истинности: с их помощью проверяют результат формулы на разных наборах значений. Законы алгебры логики позволяют упрощать выражения и подготавливать их к построению схем по заданным условиям. Законы де Моргана особенно полезны при преобразовании логических формул и анализе таблиц истинности.

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

• Равносильные выражения совпадают по результату на каждом наборе значений переменных.
• Коммутативный закон разрешает менять операнды местами, ассоциативный — перегруппировывать их.
• A ∧ A = A и A ∨ A = A.
• A ∧ 1 = A, а A ∨ 0 = A.
• A ∧ ¬A = 0, а A ∨ ¬A = 1.
• При применении закона де Моргана меняются и операция, и отрицания переменных.
• Каждый шаг преобразования должен сохранять равносильность выражения.