Как упростить логическое выражение: решение по шагам

Дано: логическое выражение $F = \neg(\neg A \wedge \neg B) \wedge (A \vee \neg B) \wedge (\neg A \vee C)$ от трёх переменных. Найти: равносильное выражение как можно более короткой записи и проверить результат таблицей истинности.

Порядок действий при упрощении почти всегда один и тот же: сначала отрицания опускают к переменным, затем выносят общий множитель за скобку, а в конце добивают склеиванием и поглощением. Ответ: $F = A \wedge C$, и переменная $B$ из выражения исчезает совсем, хотя в условии встречалась дважды. Калькулятор сверху показывает всю цепочку разом: строки матрицы это шаги упрощения, и они совпадают между собой на всех восьми наборах значений.

Решение по шагам

Дано. $F = \neg(\neg A \wedge \neg B) \wedge (A \vee \neg B) \wedge (\neg A \vee C)$. В выражении три переменные, десять знаков операций и одно отрицание, стоящее над целой скобкой.

Шаг 1. Опускаем отрицание к переменным. Пока отрицание висит над скобкой, внутри неё ничего сделать нельзя: законы вроде склеивания работают с отдельными переменными, а не с целыми конструкциями под общим штрихом. Вносим отрицание внутрь по закону де Моргана, а он меняет конъюнкцию на дизъюнкцию:

$$\neg(\neg A \wedge \neg B) = \neg\neg A \vee \neg\neg B = A \vee B.$$

Двойные отрицания снимаются тут же. Первый множитель стал обычной скобкой, и выражение приняло вид

$$F = (A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee C).$$

Шаг 2. Склеиваем две первые скобки. В скобках $(A \vee B)$ и $(A \vee \neg B)$ есть общее слагаемое $A$. Выносим его распределительным законом, как выносят общий множитель в обычной алгебре:

$$(A \vee B) \wedge (A \vee \neg B) = A \vee (B \wedge \neg B).$$

Конъюнкция переменной с её отрицанием ложна при любом значении $B$: это закон противоречия, $B \wedge \neg B = 0$. Остаётся $A \vee 0$, а дизъюнкция с нулём ничего не добавляет, поэтому $A \vee 0 = A$. Две скобки схлопнулись в одну переменную:

$$F = A \wedge (\neg A \vee C).$$

Шаг 3. Раскрываем последнюю скобку. Теперь распределительный закон применяем в другую сторону, умножая $A$ на каждое слагаемое:

$$A \wedge (\neg A \vee C) = (A \wedge \neg A) \vee (A \wedge C) = 0 \vee (A \wedge C) = A \wedge C.$$

Первое слагаемое обнулилось по тому же закону противоречия, а дизъюнкция с нулём оставила второе как есть.

Ответ: $F = A \wedge C$. Из десяти знаков операций остался один, из шести вхождений переменных осталось два. Выражение истинно ровно тогда, когда одновременно истинны $A$ и $C$, а значение $B$ на результат не влияет.

Законы алгебры логики, которые здесь работают

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

Ключевая мысль: буквы $X$, $Y$, $Z$ в этих формулах означают не переменные, а любые выражения. Поэтому закон поглощения одинаково применим и к $A \vee (A \wedge B)$, и к $(A \vee C) \vee ((A \vee C) \wedge D)$. Именно эта подстановка целых кусков вместо букв и даёт большую часть сокращений в громоздких формулах. Приоритет операций при этом остаётся обычным: сначала отрицание, потом конъюнкция, потом дизъюнкция, и разбор этого порядка со скобками есть в отдельной статье про приоритет логических операций.

Проверка таблицей истинности

Упрощение считается выполненным правильно, если исходное и конечное выражения совпадают на всех наборах значений переменных. Переменных три, значит наборов $2^3 = 8$, и проверка занимает восемь строк.

Столбцы совпали полностью: оба выражения истинны на наборах $101$ и $111$ и ложны на остальных шести. Достаточно проверить один набор вручную, чтобы убедиться, что подстановка сделана верно. Возьми $A = 1$, $B = 0$, $C = 1$: первый множитель равен $\neg(0 \wedge 1) = \neg 0 = 1$, второй $1 \vee 1 = 1$, третий $0 \vee 1 = 1$, произведение равно $1$. Упрощённое выражение даёт $1 \wedge 1 = 1$, сходится.

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

В каком порядке упрощать любое выражение

Порядок шагов не произвольный, и если его не соблюдать, выражение начинает разрастаться вместо того, чтобы сжиматься. Рабочая последовательность такая.

1. Избавиться от импликации и эквивалентности: $X \to Y = \neg X \vee Y$, а $X \leftrightarrow Y = (X \wedge Y) \vee (\neg X \wedge \neg Y)$. Пока в формуле есть стрелки, законы алгебры логики к ней неприменимы.
2. Опустить все отрицания к переменным законом де Моргана и снять двойные отрицания. После этого штрих стоит только над отдельными буквами, и формула становится читаемой.
3. Раскрыть скобки или, наоборот, вынести общий множитель распределительным законом. Направление выбирают по цели: к дизъюнктивной форме раскрывают, к конъюнктивной выносят.
4. Применить склеивание, поглощение и законы констант столько раз, сколько получится. Обычно после каждого сокращения открывается следующее, поэтому проход делают повторно, пока формула перестанет меняться.
5. Проверить ответ на нескольких наборах значений или полной таблицей истинности.

Отдельно стоит запомнить, что второй шаг иногда временно удлиняет запись. В выражении $(A \to B) \wedge (A \to \neg B)$ знаков операций сначала четыре, после замены импликаций становится шесть, и только потом остаётся один: ответ равен $\neg A$. Пугаться промежуточного роста не нужно, это нормальная часть процесса, и в калькуляторе сверху этот случай вынесен отдельным примером.

Три типовых случая: склеивание, поглощение, импликация

Первый случай, склеивание, узнаётся по двум слагаемым, которые отличаются только одной переменной, входящей с отрицанием и без. В выражении $(A \wedge B) \vee (A \wedge \neg B) \vee (\neg A \wedge B)$ первые два слагаемых склеиваются в $A$, остаётся $A \vee (\neg A \wedge B)$, а это закон Блейка, дающий $A \vee B$. Семь знаков операций сокращаются до одного.

Второй случай, поглощение, узнаётся по слагаемому, целиком содержащему другое слагаемое. В $A \vee (A \wedge B) \vee (A \wedge B \wedge C)$ первое слагаемое поглощает оба остальных, и ответ равен просто $A$. Полезно помнить смысл: если $A$ уже истинно, добавка ничего не меняет, а если ложно, то ложны и все конъюнкции с ним.

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

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

Частые ошибки

• Отрицание вносят в скобку, не меняя знак операции: пишут $\neg(\neg A \wedge \neg B) = A \wedge B$ вместо $A \vee B$. Закон де Моргана обязательно переворачивает конъюнкцию в дизъюнкцию и наоборот.
• Раскрывают скобки по правилам обычной арифметики. В алгебре логики распределительный закон работает в обе стороны, поэтому $A \vee (B \wedge C)$ равно $(A \vee B) \wedge (A \vee C)$, чего с числами не бывает.
• Путают закон противоречия с идемпотентностью: $B \wedge \neg B = 0$, но $B \wedge B = B$. Ошибка на этом месте меняет ответ полностью.
• Пропускают замену импликации и пытаются применить склеивание прямо к стрелке. Пока в формуле есть $\to$ или $\leftrightarrow$, таблица законов к ней не относится.
• Останавливаются на первом сокращении. После каждого применённого закона формулу нужно просмотреть заново: обычно открывается ещё одно поглощение.
• Не проверяют результат. Ошибка в одном знаке даёт формулу, отличающуюся от исходной ровно на одном наборе, и без проверки её не видно.

FAQ

Как понять, что выражение упрощено до конца? Формальный признак один: ни один закон из таблицы больше не применяется. Практически проверяют так: нет отрицаний над скобками, нет повторяющихся слагаемых, нет пар вида $X$ и $X \wedge Y$ и нет двух конъюнкций, отличающихся одной переменной. Если ничего из этого не нашлось, запись минимальна.

Всегда ли ответ единственный? Нет. У одной функции бывает несколько минимальных форм одинаковой длины, например $(A \wedge B) \vee (\neg A \wedge C)$ и запись через другую пару переменных. Все они равносильны, и любая засчитывается, если проверка таблицей сходится.

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

Что делать, если после упрощения выражение стало константой? Это законный ответ. Если получилось $1$, выражение тождественно истинно, то есть является тавтологией; если $0$, оно тождественно ложно и никогда не выполняется. Проверить такой вывод стоит обязательно, полной таблицей истинности.

Коротко

1. Убери импликации и эквивалентности: $X \to Y = \neg X \vee Y$.
2. Опусти отрицания к переменным законом де Моргана и сними двойные отрицания.
3. Вынеси общий множитель или раскрой скобки распределительным законом.
4. Применяй склеивание, поглощение и законы констант, пока формула меняется.
5. В разобранном примере $\neg(\neg A \wedge \neg B) \wedge (A \vee \neg B) \wedge (\neg A \vee C) = A \wedge C$: десять знаков операций сократились до одного, проверка по восьми наборам совпала.