Преобразование по законам де Моргана

Законы де Моргана помогают раскрывать отрицание выражений, содержащих конъюнкцию «И» и дизъюнкцию «ИЛИ». На этой странице разберём формулы, порядок действий и типичные приёмы, которые нужны при преобразовании логических выражений и подготовке к заданиям ege-15 и ege-23.

Что выражают законы де Моргана

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

Здесь \(\land\) обозначает конъюнкцию, или «И», \(\lor\) — дизъюнкцию, или «ИЛИ», а \(\neg\) — отрицание. Знак \(\equiv\) означает логическое равенство: левая и правая части имеют одинаковые значения при любых значениях переменных.

Пошаговый алгоритм преобразования

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

1. Найдите выражение в скобках, перед которым стоит отрицание.
2. Определите операцию внутри скобок: «И» или «ИЛИ».
3. Поставьте отрицание перед каждым элементом внутри скобок.
4. Замените операцию по законам де Моргана.
5. Если отрицание оказалось перед скобками меньшего уровня, повторите действия.
6. Устраните двойные отрицания и примените другие известные законы, если это требуется.

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

Работа с отдельными элементами

Элементом может быть не только переменная, но и целое составное выражение. Например, в формуле \(\neg(A \lor (B \land C))\) сначала раскрывается внешнее отрицание, а затем — отрицание перед внутренней скобкой.

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

Разобранный пример со вложенными скобками

Преобразуем формулу \(F=\neg((A \lor B) \land \neg C)\) так, чтобы отрицания стояли только перед переменными. Важно раскрывать внешнюю скобку первой, а затем работать с каждой частью отдельно.

Итоговая формула содержит только отрицания переменных: \(F\equiv(\neg A\land\neg B)\lor C\). Дополнительное раскрытие скобок здесь не нужно: операция между блоками уже записана явно, а закон ассоциативности или закон коммутативности понадобились бы только при изменении группировки или порядка элементов.

Как проверять преобразование

Есть два надёжных способа проверки. Первый — подставить несколько наборов значений переменных и сравнить исходную и преобразованную формулы. Второй — построить таблицу истинности. Если результаты совпадают во всех строках, формулы логически равносильны.

Таблица показывает, что столбцы для обеих частей совпадают. Значит, первый закон де Моргана верен для всех значений \(A\) и \(B\). Аналогично проверяется второй закон.

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

Приём для экзаменационных заданий

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

• Отрицание перед «И» превращено в «ИЛИ».
• Отрицание перед «ИЛИ» превращено в «И».
• Каждый элемент внутри области действия получил отрицание.
• Двойные отрицания устранены.
• Скобки сохранены до тех пор, пока порядок операций однозначен.

При построении СКНФ отрицания также раскрываются по этим правилам: цель состоит в том, чтобы привести формулу к конъюнкции дизъюнкций, где отрицания стоят непосредственно перед переменными. Для проверки равносильности можно использовать логическое тождество и таблицу истинности.