Leis de De Morgan

Definição

Duas equivalências fundamentais:

\neg(P \wedge Q) \;\equiv\; \neg P \vee \neg Q

\neg(P \vee Q) \;\equiv\; \neg P \wedge \neg Q

Negar uma conjunção distribui sobre uma disjunção, e vice-versa. A negação "atravessa" os conectivos, trocando $\wedge$ por $\vee$ .

Nomeadas em homenagem ao lógico britânico Augustus De Morgan (1806–1871).

Idênticas com operadores booleanos.

(A \cap B)^c = A^c \cup B^c

(A \cup B)^c = A^c \cap B^c

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

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

Não é verdade que João estudou e João passou $\equiv$ João não estudou ou João não passou.