"Информатика (базовый уровень)", Гейн А.Г., Юнерман Н.А.
Законы алгебры высказываний — это правила преобразования логических выражений, которые сохраняют их истинность при любых значениях переменных. Они помогают проверять равносильность формул, упрощать записи, раскрывать скобки, переносить отрицания и преобразовывать логические схемы. Главные инструменты темы — конъюнкция, дизъюнкция, отрицание, таблицы истинности и законы де Моргана.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Высказывание — повествовательное предложение, которому можно однозначно приписать истинность или ложность. Вопросы, команды и предложения вроде «Это красивый фильм» высказываниями обычно не являются, потому что их нельзя однозначно оценить. Для краткости высказывания обозначают заглавными буквами: A, B, C.
Конъюнкция — логическая операция «И», обозначаемая A ∧ B. Результат истинен только тогда, когда истинны оба исходных высказывания. Эта операция нужна, когда условие требует одновременного выполнения нескольких требований.
Дизъюнкция — логическая операция «ИЛИ», обозначаемая A ∨ B. Она ложна лишь в случае, когда оба высказывания ложны, а во всех остальных случаях истинна. Дизъюнкция описывает ситуацию, в которой достаточно выполнения хотя бы одного условия.
Отрицание — операция, меняющая значение высказывания на противоположное; её обозначают ¬A. Если A истинно, то ¬A ложно, и наоборот. Отрицание позволяет формулировать противоположное условие и преобразовывать сложные выражения.
Закон алгебры высказываний — это равенство двух логических выражений, сохраняющее истинность при любых значениях входящих высказываний. Равенство означает не совпадение записи, а совпадение результата работы выражений. Поэтому такой закон можно использовать для замены одной формулы другой без изменения её смысла.
Равносильность проверяют с помощью таблиц истинности. В таблицу записывают все возможные наборы значений переменных, затем для каждой строки вычисляют оба выражения. Если итоговые столбцы полностью совпали, выражения равносильны; нескольких удачных примеров недостаточно, потому что пропущенный набор может дать другое значение.
Переместительные законы разрешают менять местами высказывания: A ∧ B = B ∧ A и A ∨ B = B ∨ A. Сочетательные законы разрешают менять расстановку скобок в цепочке одинаковых операций: (A ∧ B) ∧ C = A ∧ (B ∧ C), а аналогично для ∨. Это возможно потому, что результат зависит от набора высказываний и операции, но не от их порядка и способа группировки.
Распределительные законы помогают раскрывать скобки и выносить общий множитель: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), а A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C). Закон двойного отрицания возвращает исходное значение: ¬¬A = A. Законы де Моргана переносят отрицание внутрь скобок: ¬(A ∧ B) = ¬A ∨ ¬B и ¬(A ∨ B) = ¬A ∧ ¬B, поэтому операция внутри скобок при этом меняется.
Законы идемпотентности сокращают повторение: A ∧ A = A и A ∨ A = A. Законы поглощения убирают лишнюю часть: A ∧ (A ∨ B) = A и A ∨ (A ∧ B) = A. Наконец, константы 0 и 1 показывают абсолютную ложь и истину: A ∧ 1 = A, A ∨ 0 = A, A ∧ 0 = 0, A ∨ 1 = 1.
Таблица служит кратким справочником при преобразовании формул. Сначала определите структуру выражения, затем найдите подходящее равенство и замените только соответствующую часть. После преобразования полезно проверить, не появился ли новый закон для следующего шага.
| Название закона | Равенство | Как применять |
|---|---|---|
| Переместительный | A ∧ B = B ∧ A; A ∨ B = B ∨ A | Менять местами высказывания. |
| Сочетательный | (A ∧ B) ∧ C = A ∧ (B ∧ C); (A ∨ B) ∨ C = A ∨ (B ∨ C) | Переставлять скобки в цепочке одинаковых операций. |
| Распределительный | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C); A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) | Раскрывать скобки или выносить общий множитель. |
| Двойное отрицание | ¬¬A = A | Удалять два последовательных отрицания. |
| Законы де Моргана | ¬(A ∧ B) = ¬A ∨ ¬B; ¬(A ∨ B) = ¬A ∧ ¬B | Переносить отрицание внутрь скобок с заменой операции. |
| Идемпотентность | A ∧ A = A; A ∨ A = A | Удалять повторяющееся высказывание. |
| Поглощение | A ∧ (A ∨ B) = A; A ∨ (A ∧ B) = A | Убирать выражение, которое не влияет на результат. |
| Законы для констант | A ∧ 1 = A; A ∨ 0 = A; A ∧ 0 = 0; A ∨ 1 = 1 | Сразу заменять операции с истинностью и ложностью. |
Задача 1. Упростим выражение A ∧ A. Повторение одного и того же условия не добавляет новой информации. Значит, нужно найти закон, который удаляет дублирование.
Ответ: A ∧ A = A. Например, требование «число делится на 2 и число делится на 2» равносильно одному требованию «число делится на 2».
Задача 2. Преобразуем ¬(A ∨ B) так, чтобы отрицание не относилось ко всей скобке. Внешнее отрицание говорит, что неверно выполнение хотя бы одного из условий. Это означает одновременную истинность отрицаний обоих условий.
Ответ: ¬(A ∨ B) = ¬A ∧ ¬B. Нельзя оставить дизъюнкцию, потому что тогда смысл выражения изменится.
Задача 3. Упростим (A ∧ B) ∨ (A ∧ ¬B) до выражения с одной переменной. В обеих частях есть общий множитель A, поэтому сначала объединим части с помощью распределительного закона. Затем оставшееся выражение определим по значениям B.
Ответ: (A ∧ B) ∨ (A ∧ ¬B) = A. Каково бы ни было значение B, одно из высказываний B и ¬B истинно, поэтому результат определяется только A.
Первая ошибка — распределять отрицание по скобкам без изменения операции, например писать ¬(A ∧ B) = ¬A ∧ ¬B. Так поступают по аналогии с обычным знаком минус, но в логике работают законы де Моргана. Проверка: при переносе отрицания одновременно поменяйте ∧ и ∨.
Вторая ошибка — отрицать не каждый член внутри скобок. Запись ¬(A ∨ B) = ¬A ∧ B неверна, потому что B осталось без отрицания. Проверьте, что после раскрытия скобок знак ¬ появился у всех исходных частей.
Третья ошибка — путать два распределительных закона и переносить на них только арифметическое правило. В алгебре высказываний и ∧, и ∨ могут распределяться, но результат зависит от выбранной операции. Сверяйте преобразование с формулой, а не только с привычным видом скобок.
Четвёртая ошибка — объявлять равенство верным после проверки нескольких наборов значений. Закон должен работать при всех возможных наборах переменных, иначе это лишь случайное совпадение. Постройте полную таблицу истинности или примените уже доказанный закон.
Для понимания темы нужны значения истинности высказываний, таблицы истинности и операции отрицания, конъюнкции и дизъюнкции. Эти знания позволяют вычислять отдельные строки таблицы и видеть смысл преобразований. Без них формулы остаются набором символов.
Законы применяют при упрощении логических выражений, составлении и преобразовании логических схем, а также при проверке равносильности формул. Упрощённая формула содержит меньше операций и обычно требует более простой схемы. Те же приёмы помогают переводить условия задач в удобную логическую запись.
Как проверить, равносильны ли два логических выражения?
Нужно построить таблицы истинности для обоих выражений и сравнить результаты во всех строках. Если столбцы совпадают при каждом наборе значений переменных, выражения равносильны.
Почему при применении закона де Моргана меняется операция?
Отрицание конъюнкции означает, что неверно утверждение «истинны оба», то есть хотя бы одно высказывание ложно. Поэтому конъюнкция превращается в дизъюнкцию, а при отрицании дизъюнкции дизъюнкция превращается в конъюнкцию.
Можно ли менять местами высказывания в конъюнкции и дизъюнкции?
Да, это разрешают переместительные законы: A ∧ B = B ∧ A и A ∨ B = B ∨ A. Значение выражения от перестановки высказываний не меняется.
Чем распределительный закон в алгебре высказываний отличается от привычного раскрытия скобок?
В логике действуют два распределительных закона: конъюнкция распределяется относительно дизъюнкции и наоборот. Поэтому нельзя механически переносить только арифметическое правило раскрытия скобок.
Как понять, какой закон применить для упрощения выражения?
Сначала найдите знакомую структуру: повторяющийся член, двойное отрицание, скобки с отрицанием, константы 0 и 1 или общий множитель. Затем выберите закон, который убирает эту структуру, и после каждого шага проверяйте запись.
§ 31. Законы алгебры высказываний
