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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

not (P and Q) = (not P) or (not Q)
not (P or Q) = (not P) and (not Q)


Обычная запись этих законов в формальной логике:

\neg(P\wedge Q)=(\neg P)\vee(\neg Q),
\neg(P\vee Q)=(\neg P)\wedge(\neg Q),

или

\overline{ x \wedge y } = \overline x \vee \overline y,
\overline{ x\vee y } = \overline x \wedge \overline y.


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

\neg \forall x \, P(x) \equiv \exists x \, \neg P(x),
\neg \exists x \, P(x) \equiv \forall x \, \neg P(x).


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

(A\cap B)^C=A^C\cup B^C,
(A\cup B)^C=A^C\cap B^C.


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

Если существует операция логического умножения двух и более элементов, операция «и» — (A&B), то для того, чтобы найти обратное от всего суждения ~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (~A+~B). Закон работает аналогично в обратном направлении: ~(A+B) = (~A&~B)

История[править | править вики-текст]

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

Ссылки[править | править вики-текст]