Lois de De Morgan

Un article de Wikipédia, l'encyclopédie libre.

Les lois de De Morgan font partie de la théorie logique du calcul des propositions. Elles ont été formulées par le mathématicien britannique Auguste De Morgan (1806-1871).

Sommaire

1 Énoncé en français
2 Énoncé mathématique
3 Preuve
4 Généralisation
5 Voir aussi

[modifier] Énoncé en français

La négation d'une conjonction de deux propositions est équivalente à la disjonction des négations des deux propositions.

La négation d'une disjonction de deux propositions est équivalente à la conjonction des négations des deux propositions.

[modifier] Énoncé mathématique

$\lnot(A \land B) \leftrightarrow (\lnot A)\lor (\lnot B)$

$\lnot(A \lor B) \leftrightarrow (\lnot A) \land (\lnot B)$

Notons que de ces quatre implications valides en logique classique trois sont valides en logique intuitionniste, mais pas : $\lnot(A \land B) \rightarrow (\lnot A)\lor (\lnot B)$

[modifier] Preuve

Pour le prouver, on peut par exemple, utiliser la méthode sémantique des tables de vérité. On rappelle que deux formules sont équivalentes si et seulement si elles ont la même table de vérité.

$\lnot (A \land B) \leftrightarrow (\lnot A) \lor (\lnot B)$
$A$	$B$	$A \land B$	$\lnot (A \land B)$	$\lnot A$	$\lnot B$	$(\lnot A) \lor (\lnot 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

$\lnot(A \lor B) \leftrightarrow (\lnot A) \land (\lnot B)$
$A$	$B$	$A \lor B$	$\lnot (A \lor B)$	$\lnot A$	$\lnot B$	$(\lnot A) \land (\lnot 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

[modifier] Généralisation

Les énoncés de De Morgan se généralisent à n propositions par récurrence, en utilisant l'associativité des lois $\land$ et $\lor$ ainsi que leur double distributivité. Comme les deux preuves sont symétriques (il suffit de remplacer une loi par l'autre), on ne donne ici que celle pour la première loi.

Vrai au rang n=2
Si vrai au rang n

$\lnot(A_1 \land A_2 \land ... \land A_n \land A_{n+1})$

$\leftrightarrow \lnot ( (A_1 \land A_2 \land ... \land A_n) \land A_{n+1})$

$\leftrightarrow (\lnot (A_1 \land A_2 \land ... \land A_n)) \lor (\lnot A_{n+1})$

$\leftrightarrow ((\lnot A_1) \lor (\lnot A_2) \lor ... \lor (\lnot A_n)) \lor (\lnot A_{n+1})$

$\leftrightarrow (\lnot A_1) \lor (\lnot A_2) \lor ... \lor (\lnot A_n) \lor (\lnot A_{n+1})$

La généralisation de ces règles au delà du fini donne les règles d'interdéfinissabilité des quantificateurs universel et existentiel du calcul des prédicats classique. Le quantificateur universel pouvant être vu comme une généralisation de la conjonction et le quantificateur existentiel pouvant être vu comme une généralisation de la disjonction (non exclusive).

$\lnot\forall x (Ax) \leftrightarrow \exists x (\lnot Ax)$