Открыть главное меню

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

(перенаправлено с «Правила де Моргана»)
Диаграммы Венна, описывающие законы де Моргана
Представление правил де Моргана через логические элементы

Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

Отрицание конъюнкции есть дизъюнкция отрицаний.
Отрицание дизъюнкции есть конъюнкция отрицаний.

ОпределениеПравить

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

не (a и b) = (не a) или (не b)
не (a или b) = (не a) и (не b)

В математике это выглядит так:

  000 или по-другому: 000  


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

  000 или по-другому: 000  

Эти правила также действительны для множества элементов (семейств):

  00000 и 00000  .

В исчислении предикатов:

 
 

Следствия:

Используя законы де Моргана, можно выразить конъюнкцию через дизъюнкцию и три отрицания. Аналогично можно выразить дизъюнкцию:

 
 

В виде теоремы:

Если существует суждение, выраженное операцией логического умножения двух или более элементов, т. е. операцией «и»:  , то для того, чтобы найти обратное   от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, т. е. операцией «или»:  . Закон работает аналогично в обратном направлении:  .

ПрименениеПравить

Законы де Моргана применяются в таких важных областях, как дискретная математика, электротехника, физика и информатика; например, используются для оптимизации цифровых схем посредством замены одних логических элементов другими.

ИсторияПравить

  • «Противоречащая противоположность дизъюнктивного суждения — конъюнктивное суждение, составленное из противоречащих противоположностей частей дизъюнктивного суждения (The contradictory opposite of a disjunctive proposition is a conjunctive proposition composed of the contradictories of the parts of the disjunctive proposition)» (Уильям Оккам, Summa Logicae).

См. такжеПравить

СсылкиПравить