Упрощение логических выражений
Упрощение логических выражений — это преобразование формулы к более короткому или удобному виду без изменения её значения при любых наборах исходных переменных. Для этого используют законы логических операций, свойства равносильности и таблицы истинности; навык особенно полезен при решении заданий ege-4 и ege-11.
Что такое логическая формула
Логическое выражение, или формула, состоит из логических переменных, констант и операций. Переменные обычно обозначают латинскими буквами \(A\), \(B\), \(C\) и принимают только два значения: \(0\) — ложь и \(1\) — истина. Константы \(0\) и \(1\) можно использовать непосредственно.
Основные операции: отрицание \(\neg A\) («не \(A\)»), конъюнкция \(A \land B\) («\(A\) и \(B\)»), дизъюнкция \(A \lor B\) («\(A\) или \(B\)»), импликация \(A \to B\) («из \(A\) следует \(B\)») и эквиваленция \(A \leftrightarrow B\) («\(A\) равносильно \(B\)»). Подробнее о первых трёх операциях см. страницу отрицание, конъюнкция и дизъюнкция.
Логическая формула — запись, составленная из логических переменных, констант и знаков логических операций с соблюдением порядка действий и скобок.
Два выражения называются равносильными, если на каждом наборе значений переменных они принимают одинаковые значения. Запись: \(F \equiv G\).
Формулу в информатике удобно читать по порядку: сначала выполняется отрицание, затем конъюнкция, затем дизъюнкция, после этого импликация и эквиваленция. Скобки изменяют этот порядок, поэтому при преобразованиях их нельзя удалять без доказательства.
Основные законы алгебры логики
Законы алгебры логики позволяют заменять часть выражения равносильной частью. В отличие от обычной алгебры, здесь используются только значения \(0\) и \(1\), поэтому, например, повторение переменной не меняет результат.
Законы де Моргана: отрицание конъюнкции превращается в дизъюнкцию отрицаний, а отрицание дизъюнкции — в конъюнкцию отрицаний. При раскрытии отрицания меняется и знак операции, и отрицание каждой переменной.
Если одна часть выражения уже содержится в другой, более сложная часть можно удалить: \(A \lor (A \land B) \equiv A\) и \(A \land (A \lor B) \equiv A\).
Какое выражение равносильно \(\neg(A \lor B)\)?
Как упрощать выражение
Перед началом работы определите главную операцию и внимательно перепишите исходную формулу. Затем заменяйте самые простые фрагменты: двойное отрицание, сочетания с \(0\) и \(1\), переменную вместе с её отрицанием. После этого применяйте распределительный закон, поглощение и законы де Моргана.
- Расставьте скобки и установите порядок операций.
- Замените импликации и эквиваленции через отрицание, конъюнкцию и дизъюнкцию.
- Упростите фрагменты вида \(A \lor 0\), \(A \land 1\), \(A \lor \neg A\) и подобные.
- Соберите одинаковые слагаемые, используя вынесение общего множителя и поглощение.
- Проверьте результат таблицей истинности, если преобразование кажется нетривиальным.
Для длинной формулы удобно обозначать повторяющийся фрагмент буквой, например \(X=(A\lor B)\). Сначала преобразуйте выражение с \(X\), затем вернитесь к его определению. Это уменьшает количество скобок и ошибок.
Разобранный пример
Упростим формулу \(F=(A\land B)\lor(A\land\neg B)\). На первый взгляд в ней четыре вхождения переменных, но выражение можно свести к одной переменной.
Вынесем общий множитель \(A\), затем применим закон исключённого третьего: \(B\lor\neg B\equiv1\).
Итак, формула \(F\) принимает то же значение, что и \(A\). Если \(A=0\), оба исходных слагаемых ложны. Если \(A=1\), одно из значений \(B\) и \(\neg B\) обязательно равно \(1\), поэтому вся дизъюнкция истинна.
| A | B | \(A\land B\) | \(A\land\neg B\) | \(F\) | \(A\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 |
Проверка таблицей истинности
Если в формуле \(n\) независимых переменных, таблица содержит \(2^n\) строк. В каждой строке последовательно вычисляют значения промежуточных операций, а затем сравнивают столбцы двух выражений. Полное совпадение последних столбцов доказывает равносильность.
Таблица особенно полезна, когда формула короткая, переменных не больше трёх или нужно проверить ответ после преобразований. Для четырёх и более переменных таблица быстро становится большой, поэтому сначала применяйте законы логики.
Не путайте \(\lor\) и \(\land\): дизъюнкция ложна только при двух нулях, а конъюнкция истинна только при двух единицах. Не раскрывайте скобки по правилам обычного умножения без учёта закона. При использовании де Моргана меняйте знак операции. Нельзя сокращать одинаковые части в дизъюнкции или конъюнкции так, как сокращают множители в дроби.
Равносильные логические выражения описывают тот же результат разными формулами. Если неизвестные значения переменных нужно найти из условия, используется логическое уравнение. А зависимость результата от входных переменных изучает булева функция.
Как решать экзаменационные задания
В заданиях на формулу сначала выясните, требуется ли найти значение, количество наборов или упростить выражение. При подстановке значений начинайте с отрицаний и внутренних скобок. Если нужно сравнить несколько формул, ищите общий закон: часто встречаются импликация, де Морган и поглощение.
- Все переменные и операции переписаны без изменения исходной формулы.
- Для импликации использована замена \(A\to B\equiv\neg A\lor B\).
- В каждой строке таблицы проверено число значений: \(2^n\).
- Итоговая формула проверена хотя бы на одном-двух наборах.
Быстрая проверка
Главное
- Логическая формула состоит из переменных, констант и операций; её значение — \(0\) или \(1\).
- Упрощение сохраняет значение формулы на всех наборах переменных.
- Основные инструменты: нейтральные и поглощающие элементы, двойное отрицание, распределение, поглощение и законы де Моргана.
- Импликацию заменяют формулой \(A\to B\equiv\neg A\lor B\), а равносильность можно проверять таблицей истинности.
- Для \(n\) переменных таблица содержит \(2^n\) строк; итоговые столбцы равносильных формул совпадают.