Законы де Моргана

Законы де Моргана — это пара логических правил, устанавливающих взаимосвязь между операциями отрицания, конъюнкции (логического «И») и дизъюнкции (логического «ИЛИ») в булевой алгебре и математической логике. Законы позволяют выражать отрицание сложных высказываний через отрицания их составных частей, меняя при этом тип логической связки. В классической логике законы формулируются следующим образом: отрицание конъюнкции эквивалентно дизъюнкции отрицаний, а отрицание дизъюнкции эквивалентно конъюнкции отрицаний.

История

Законы названы в честь шотландского математика и логика Огастеса де Моргана (1806–1871), который впервые сформулировал их в современном символическом виде в середине XIX века. Однако сами по себе эти соотношения были известны ещё в античной логике. Аристотель в своих «Первых аналитиках» и «Об истолковании» рассматривал эквивалентности, близкие к законам де Моргана, хотя и не в формализованном виде. В средневековой логике, в частности в трудах Петра Испанского и Уильяма Оккама, также встречались рассуждения о превращении отрицания сложных суждений.

Де Морган, работая над формализацией логики высказываний и созданием алгебры логики, независимо от Джорджа Буля, пришёл к этим правилам. Он опубликовал их в своей книге «Формальная логика» (1847) и в более поздних работах. Впоследствии законы стали фундаментальным элементом булевой алгебры, теории множеств и цифровой схемотехники.

Формулировка

В математической логике законы де Моргана записываются в виде двух эквивалентностей:

1. Отрицание конъюнкции:

¬(A ∧ B) ≡ (¬A) ∨ (¬B) Словесно: «не (A и B)» равносильно «(не A) или (не B)».

1. Отрицание дизъюнкции:

¬(A ∨ B) ≡ (¬A) ∧ (¬B) Словесно: «не (A или B)» равносильно «(не A) и (не B)».

Здесь символ «¬» обозначает логическое отрицание, «∧» — конъюнкцию, «∨» — дизъюнкцию, а «≡» — логическую эквивалентность.

В теории множеств

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

1. Дополнение пересечения:

(A ∩ B)^c = A^c ∪ B^c Дополнение пересечения двух множеств равно объединению их дополнений.

1. Дополнение объединения:

(A ∪ B)^c = A^c ∩ B^c Дополнение объединения двух множеств равно пересечению их дополнений.

Здесь символ «^c» обозначает дополнение множества.

В булевой алгебре

В булевой алгебре, где переменные принимают значения 0 (ложь) или 1 (истина), законы де Моргана записываются с использованием операций логического сложения (ИЛИ, «+») и умножения (И, «·»), а также инверсии (черта над переменной):

1. ¬(x · y) = ¬x + ¬y
2. ¬(x + y) = ¬x · ¬y

Доказательство

Справедливость законов де Моргана может быть доказана несколькими способами.

Табличный метод

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

Для первого закона ¬(A ∧ B) ≡ (¬A) ∨ (¬B):

Столбцы «¬(A ∧ B)» и «(¬A) ∨ (¬B)» идентичны, что доказывает первый закон. Аналогично доказывается второй закон.

Аксиоматический метод

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

Обобщение

Законы де Моргана могут быть обобщены на произвольное количество переменных. Для любого конечного набора высказываний A₁, A₂, ..., Aₙ справедливо:

1. ¬(A₁ ∧ A₂ ∧ ... ∧ Aₙ) ≡ (¬A₁) ∨ (¬A₂) ∨ ... ∨ (¬Aₙ)
2. ¬(A₁ ∨ A₂ ∨ ... ∨ Aₙ) ≡ (¬A₁) ∧ (¬A₂) ∧ ... ∧ (¬Aₙ)

В кванторной логике законы де Моргана также имеют аналоги, связывающие кванторы всеобщности и существования с отрицанием:

1. ¬(∀x P(x)) ≡ ∃x ¬P(x) — «неверно, что все x обладают свойством P» равносильно «существует x, не обладающий свойством P».
2. ¬(∃x P(x)) ≡ ∀x ¬P(x) — «неверно, что существует x, обладающий свойством P» равносильно «все x не обладают свойством P».

Применение

В математике и логике

Законы де Моргана являются инструментом для преобразования и упрощения логических выражений. Они позволяют:

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

В программировании

В программировании законы де Моргана используются для упрощения условных конструкций и улучшения читаемости кода. Например, условие if not (a > 0 and b < 10) может быть заменено на if not (a > 0) or not (b < 10), что часто более понятно. Многие компиляторы и интерпретаторы автоматически применяют эти преобразования при оптимизации кода.

В цифровой схемотехнике

В электронике и цифровой схемотехнике законы де Моргана лежат в основе проектирования логических схем. Они позволяют заменять элементы И-НЕ (NAND) и ИЛИ-НЕ (NOR) друг на друга, что важно при реализации схем на определённых типах логических микросхем (например, на элементах ТТЛ- или КМОП-логики). Законы де Моргана также используются для минимизации булевых функций и синтеза комбинационных схем.

В повседневном языке

В повседневной речи законы де Моргана проявляются в виде логических конструкций, хотя и не всегда осознанно. Например, утверждение «неверно, что он умный и красивый» означает, что «он не умный или не красивый». Аналогично, «неверно, что я пойду в кино или в театр» означает «я не пойду в кино и не пойду в театр».

Интересные факты

• Законы де Моргана часто называют «правилами двойственности» в булевой алгебре, так как они показывают симметрию между операциями конъюнкции и дизъюнкции.
• В квантовой логике, которая отличается от классической, законы де Моргана могут не выполняться в полном объёме.
• Огастес де Морган также известен своим вкладом в теорию отношений, математическую индукцию и введением термина «математическая индукция».

Источники

• Де Морган, Огастес. «Формальная логика» (1847).
• Мендельсон, Э. «Введение в математическую логику». — М.: Наука, 1976.
• Гиндикин, С. Г. «Алгебра логики в задачах». — М.: Наука, 1972.
• Толковый словарь по математике и логике. — М.: Мир, 1990.