Коммутативность, ассоциативность, дистрибутивность, законы де Моргана, поглощение и склеивание
Зачем нужны законы алгебры логики
Алгебра логики (булева алгебра) изучает высказывания и логические операции над ними так же, как обычная алгебра изучает числа и арифметические операции. Любое сложное логическое выражение можно преобразовать в другое, равносильное ему (то есть принимающее те же значения истинности при тех же значениях переменных), но более простое по записи. Это умение критически важно при решении задач ЕГЭ на логические уравнения, на построение таблиц истинности и на анализ схем, а также при проектировании реальных цифровых устройств, где упрощение выражения уменьшает число логических элементов в схеме.
Базовыми операциями алгебры логики являются: отрицание НЕ (¬A, инверсия), конъюнкция И (A∧B, логическое умножение), дизъюнкция ИЛИ (A∨B, логическое сложение). На их основе строятся более сложные операции — импликация (A→B), эквивалентность (A↔B) и исключающее ИЛИ (A⊕B, XOR).
Переместительный (коммутативный) закон
Результат конъюнкции и дизъюнкции не зависит от порядка операндов:
Это прямая аналогия с переместительным законом сложения и умножения чисел (a+b=b+a, a·b=b·a). Важно помнить, что импликация НЕ коммутативна: A→B и B→A — разные высказывания.
Сочетательный (ассоциативный) закон
Порядок группировки операндов при выполнении однотипных операций не влияет на результат, поэтому скобки в цепочке из одной и той же операции можно опускать:
Распределительный (дистрибутивный) закон
Конъюнкция дистрибутивна относительно дизъюнкции, и, что необычно для обычной алгебры чисел, дизъюнкция также дистрибутивна относительно конъюнкции:
Второе равенство не имеет аналога в арифметике (там a+(b·c) ≠ (a+b)·(a+c) в общем случае), поэтому его нужно отдельно запомнить и проверить на таблице истинности при первом знакомстве.
Законы де Моргана
Законы де Моргана связывают отрицание с конъюнкцией и дизъюнкцией и чрезвычайно часто используются при упрощении выражений и при «снятии» инверсии со скобки:
Словесная формулировка: отрицание конъюнкции равно дизъюнкции отрицаний, а отрицание дизъюнкции — конъюнкции отрицаний. При переносе инверсии внутрь скобки знак операции меняется на противоположный (И на ИЛИ и наоборот), а над каждым операндом появляется своя инверсия.
Закон идемпотентности и законы с константами
Повторение одного и того же операнда в конъюнкции или дизъюнкции не меняет результата:
Операции с логическими константами (0 — ложь, 1 — истина) подчиняются простым правилам, которые удобно держать в памяти как таблицу:
| Выражение | Результат | Выражение | Результат |
|---|---|---|---|
A∧1 | A | A∨1 | 1 |
A∧0 | 0 | A∨0 | A |
A∧¬A | 0 | A∨¬A | 1 |
¬¬A | A | — | — |
Последнее равенство — закон двойного отрицания: две инверсии подряд взаимно уничтожаются.
Закон поглощения
Закон поглощения позволяет убрать из выражения «лишний» член, который не влияет на результат:
Идея в том, что если A уже истинно, то всё выражение истинно независимо от B (для дизъюнктивной формы), а если A ложно — выражение ложно независимо от B тоже. Значит, B «поглощается» и никак не влияет на итог.
Закон склеивания
Закон склеивания используется, когда два слагаемых отличаются только наличием инверсии у одной переменной:
Переменная B здесь принимает оба значения (и B, и ¬B), поэтому её влияние на результат исчезает, и остаётся только A.
Примеры пошагового упрощения выражений
Пример 1. Задача. Упростить логическое выражение F = ¬(A∨B)∨(A∧B)∨(¬A∧B).
Решение. Применим закон де Моргана к первому слагаемому:
Сгруппируем второе и третье слагаемые — оба содержат множитель, отличающийся инверсией у A при одинаковом B: (A∧B)∨(¬A∧B) = B по закону склеивания (роли A и B в формуле склеивания здесь поменялись местами, но суть та же — переменная A принимает оба значения при общем B):
Раскроем скобку по дистрибутивности и применим закон A∨¬A∧B = A∨B (частный случай поглощения с раскрытием), либо проще — применим дистрибутивность к дизъюнкции:
Ответ: F = ¬A∨B (это выражение равносильно импликации A→B, что легко проверить по таблице истинности). Итог: из громоздкого выражения из трёх операций дизъюнкции, трёх конъюнкций и двух инверсий над скобками получили выражение всего из одной инверсии и одной дизъюнкции.
Пример 2. Задача. Упростить выражение F = ¬(¬A∧B)∧(A∨B).
Решение. Раскроем инверсию конъюнкции по закону де Моргана:
Вынесем A за скобку по дистрибутивному закону (в форме, обратной раскрытию): A∨¬B и A∨B — это A∨(¬B∧B) по закону, обратному дистрибутивности дизъюнкции относительно конъюнкции:
Ответ: F = A. Проверка по таблице истинности (перебором всех 4 комбинаций A и B) подтверждает, что исходное громоздкое выражение действительно равносильно простому A.
Пример 3: упрощение выражения с тремя переменными
Задача. Упростить выражение F = (A∧B∧C)∨(A∧B∧¬C)∨(¬A∧B).
Решение. Первые два слагаемых отличаются только инверсией переменной C при общем множителе A∧B, значит к ним применим закон склеивания:
Выражение упростилось до F = (A∧B)∨(¬A∧B). Теперь оба слагаемых содержат общий множитель B, а второй множитель у них — A и ¬A, то есть снова применим закон склеивания (в форме A∧B∨¬A∧B=B, где роль «переменной, отличающейся инверсией» теперь играет A):
Ответ: F = B. Из выражения с тремя логическими переменными и тремя операциями конъюнкции двойным применением закона склеивания получена элементарная переменная B — результат, который было бы крайне трудоёмко заметить, ограничившись лишь построением таблицы истинности на 8 строк без предварительного алгебраического упрощения.
Приоритет операций и порядок применения законов
При упрощении важно помнить принятый приоритет логических операций (от высшего к низшему): инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность. Скобки всегда обрабатываются в первую очередь. Типовая стратегия упрощения: сначала законами де Моргана «протолкнуть» все инверсии внутрь, к отдельным переменным (получить так называемую нормальную форму без инверсий над скобками), затем раскрыть скобки по дистрибутивности, а после — искать возможности для поглощения, склеивания и удаления констант.
Типичные ошибки
Самая частая ошибка — неверное применение закона де Моргана: забывают, что при переносе отрицания через скобку операция внутри меняется (И↔ИЛИ), и пишут ¬(A∧B) = ¬A∧¬B вместо правильного ¬A∨¬B. Вторая распространённая ошибка — путать дистрибутивность дизъюнкции относительно конъюнкции с арифметикой и не пользоваться равенством A∨(B∧C) = (A∨B)∧(A∨C), хотя оно часто резко упрощает выкладки. Третья ошибка — забывать проверять итоговое упрощённое выражение построением таблицы истинности хотя бы на 2-3 переменных, что позволяет быстро обнаружить арифметическую ошибку в преобразованиях.
Краткий словарь терминов
Булева алгебра — раздел математики, изучающий логические операции над высказываниями, принимающими значения «истина» и «ложь».
Равносильные выражения — логические выражения, принимающие одинаковые значения истинности при любых одинаковых значениях входящих в них переменных.
Закон де Моргана — правило, связывающее отрицание конъюнкции/дизъюнкции с дизъюнкцией/конъюнкцией отрицаний.
Дистрибутивность — свойство одной операции распределяться относительно другой, например A∧(B∨C)=(A∧B)∨(A∧C).
Поглощение — закон, позволяющий убрать из выражения слагаемое, не влияющее на итоговый результат.
Склеивание — закон, объединяющий два похожих слагаемых, отличающихся инверсией одной переменной, в одно более короткое.
Идемпотентность — свойство, при котором повторение операнда в операции не меняет результата (A∧A=A).
Заключение
Законы алгебры логики — рабочий инструмент, позволяющий преобразовывать логические выражения к более простому и обозримому виду без построения громоздких таблиц истинности. Владение коммутативностью, ассоциативностью, дистрибутивностью, законами де Моргана, поглощения и склеивания необходимо для решения логических уравнений и задач на количество решений, к рассмотрению которых мы переходим в следующей теме.
