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