Закон де Моргана
Закон де Моргана — это пара взаимосвязанных правил в математической логике и булевой алгебре, описывающих преобразование логических операций конъюнкции (логического «И») и дизъюнкции (логического «ИЛИ») через отрицание. Законы устанавливают, что отрицание конъюнкции эквивалентно дизъюнкции отрицаний, а отрицание дизъюнкции эквивалентно конъюнкции отрицаний. Эти законы являются фундаментальными для формальной логики, теории множеств, цифровой электроники и программирования.
Формулировка
В классической логике высказываний законы де Моргана записываются в виде двух эквивалентностей:
- Отрицание конъюнкции:
¬(A ∧ B) ≡ (¬A) ∨ (¬B) Словесно: «не (A и B)» равносильно «(не A) или (не B)».
- Отрицание дизъюнкции:
¬(A ∨ B) ≡ (¬A) ∧ (¬B) Словесно: «не (A или B)» равносильно «(не A) и (не B)».
Здесь A и B — произвольные высказывания (пропозициональные переменные), символ ¬ обозначает логическое отрицание, ∧ — конъюнкцию, ∨ — дизъюнкцию, а ≡ — логическую эквивалентность.
История
Законы названы в честь шотландского математика и логика Огастеса де Моргана (1806–1871). Де Морган сформулировал и систематически изложил эти правила в своей работе «Формальная логика» (1847 год). Однако отдельные случаи применения этих преобразований были известны ещё в Средние века (например, в трудах Уильяма Оккама) и в античной логике (стоиками). Де Морган первым придал им статус общих законов алгебры логики, связав с развитием булевой алгебры, предложенной Джорджем Булем.
Доказательство
Истинность законов де Моргана может быть установлена с помощью таблиц истинности, сравнивающих значения левой и правой частей для всех возможных комбинаций истинностных значений A и B (истина — 1, ложь — 0).
Таблица истинности для закона ¬(A ∧ B) ≡ (¬A) ∨ (¬B)
| A | B | A ∧ B | ¬(A ∧ B) | ¬A | ¬B | (¬A) ∨ (¬B) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Столбцы «¬(A ∧ B)» и «(¬A) ∨ (¬B)» совпадают, что доказывает эквивалентность.
Таблица истинности для закона ¬(A ∨ B) ≡ (¬A) ∧ (¬B)
| A | B | A ∨ B | ¬(A ∨ B) | ¬A | ¬B | (¬A) ∧ (¬B) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Столбцы «¬(A ∨ B)» и «(¬A) ∧ (¬B)» совпадают, что доказывает эквивалентность.
Обобщения
Законы де Моргана могут быть обобщены на произвольное количество переменных. Для n высказываний A₁, A₂, ..., Aₙ:
- ¬(A₁ ∧ A₂ ∧ ... ∧ Aₙ) ≡ (¬A₁) ∨ (¬A₂) ∨ ... ∨ (¬Aₙ)
- ¬(A₁ ∨ A₂ ∨ ... ∨ Aₙ) ≡ (¬A₁) ∧ (¬A₂) ∧ ... ∧ (¬Aₙ)
Эти обобщения справедливы для любого конечного числа операндов и могут быть доказаны методом математической индукции.
Применение в различных областях
Теория множеств
В теории множеств законы де Моргана формулируются для операций объединения (∪) и пересечения (∩) относительно дополнения (черта сверху или символ \(^c\)):
- Дополнение объединения равно пересечению дополнений:
\(\overline{A \cup B} = \overline{A} \cap \overline{B}\)
- Дополнение пересечения равно объединению дополнений:
\(\overline{A \cap B} = \overline{A} \cup \overline{B}\)
Эти правила используются при преобразовании выражений с множествами и доказательстве тождеств.
Булева алгебра и цифровая электроника
В булевой алгебре законы де Моргана позволяют заменять логические элементы «И» на «ИЛИ» с инверсными входами и наоборот. Это широко применяется при проектировании цифровых схем: например, элемент «И-НЕ» (NAND) может быть реализован как «ИЛИ-НЕ» (NOR) с инвертированными входами. Законы де Моргана лежат в основе минимизации логических функций и синтеза комбинационных схем.
Программирование
В программировании законы де Моргана используются для упрощения условных выражений. Например, сложное условие вида:
if not (a > 0 and b < 10)
может быть преобразовано в эквивалентное:
if (a <= 0) or (b >= 10)
Это часто улучшает читаемость кода и позволяет избежать избыточных отрицаний. Законы применяются в языках программирования, поддерживающих булеву логику (C, Java, Python, JavaScript и др.).
Логика и математика
В формальной логике законы де Моргана являются частью системы аксиом классического исчисления высказываний. Они используются при доказательстве теорем, преобразовании формул к нормальным формам (конъюнктивной и дизъюнктивной) и в автоматическом доказательстве теорем.
Критика и ограничения
Законы де Моргана справедливы в классической (бивалентной) логике, где каждое высказывание истинно или ложно. В неклассических логиках, таких как интуиционистская логика, эти законы выполняются не в полной мере. В интуиционистской логике, например, из ¬(A ∧ B) не следует (¬A) ∨ (¬B); справедливо только обратное направление. В многозначных логиках и паранепротиворечивых логиках действие законов может быть ограничено или модифицировано.
Интересные факты
- В честь Огастеса де Моргана назван кратер на Луне (де Морган, диаметр около 10 км).
- Законы де Моргана часто называют «правилами дополнения» или «правилами двойственности» в булевой алгебре.
- В русскоязычной литературе законы иногда формулируются мнемонически: «Отрицание конъюнкции есть дизъюнкция отрицаний; отрицание дизъюнкции есть конъюнкция отрицаний».
Источники
- Де Морган, Огастес. «Формальная логика» (1847).
- Булева алгебра и логические схемы / под ред. В. И. Левина. — М.: Наука, 1978.
- Клини, С. К. «Математическая логика». — М.: Мир, 1973.
- Мендельсон, Э. «Введение в математическую логику». — М.: Наука, 1984.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →