Loi de De Morgan

Loi de De Morgan: Lois de De Morgan

Les lois de De Morgan sont des identités entre propositions logiques. Elles ont été formulées par le mathématicien britannique Augustus De Morgan (1806-1871).

Sommaire

1 Énoncé en français

2 Énoncé mathématique

3 Justification

4 Généralisation

5 Voir aussi

Énoncé en français

La négation de la conjonction de deux propositions est équivalente à la disjonction des négations des deux propositions, ce qui signifie non(A et B) est (non A) ou (non B).

La négation de la disjonction de deux propositions est équivalente à la conjonction des négations des deux propositions, ce qui signifie que non(A ou B) est (non A) et (non B).

Énoncé mathématique

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

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

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)$

Justification

Pour justifier ces formules, 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

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})$

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)$

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

Et de ces quatre implications classiques, seule $\lnot\forall x (Ax) \rightarrow \exists x (\lnot Ax)$ n'est pas valide en logique intuitionniste.

Voir aussi

Algèbre de Boole

Calcul des propositions

Portail de la logique

Portail des mathématiques

Ce document provient de « Lois de De Morgan ».

Catégories : Logique | Logique mathématique

Contenu soumis à la licence CC-BY-SA. Source : Article Loi de De Morgan de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

MORGAN (L. H.) — Considéré comme le «fondateur» de la science anthropologique, admiré par G. Bandelier, J. W. Powell, L. Fison, A. W. Howitt, pionniers à des titres divers de l’ethnographie américaine et australienne, loué par Marx et Engels pour avoir… … Encyclopédie Universelle
Morgan Tsvangirai — Morgan Tsvangirai, 2009. Mandats 2e Premier ministre zimbabwéen … Wikipédia en Français
Morgan Woodward — est un acteur et scénariste américain né le 16 septembre 1925 à Fort Worth, Texas (États Unis). Sommaire 1 Biographie 2 Filmographie 2.1 comme acteur … Wikipédia en Français
Loi De Morgan — Lois de De Morgan Les lois de De Morgan sont des identités entre propositions logiques. Elles ont été formulées par le mathématicien britannique Augustus De Morgan (1806 1871). Sommaire 1 Énoncé en français 2 Énoncé mathématique 3 Justification … Wikipédia en Français
loi De Morgan — De Morgano dėsnis statusas T sritis automatika atitikmenys: angl. law of De Morgan vok. De Morgansches Gesetz, n rus. закон де Моргана, m pranc. loi De Morgan, f ryšiai: sinonimas – Morgano dėsnis … Automatikos terminų žodynas
Loi de Peirce — La loi de Peirce est la proposition où désigne l implication. Elle a été proposée par le logicien et philosophe Charles Sanders Peirce. Cette formule, valide en logique classique, est invalide en logique intuitionniste. Cela signifie que, bien… … Wikipédia en Français
Loi du zéro-un de Borel — La loi du zéro un de Borel a été publiée en 1909 dans l article Les probabilités dénombrables et leurs applications arithmétiques[1], par Émile Borel, en vue de la démonstration du théorème des nombres normaux, et en vue d applications aux… … Wikipédia en Français
Morgan Shuster — W. Morgan Shuster, trésorier général de Perse et auteur de The Strangling of Persia. William Morgan Shuster (1877 1960), avocat américain, fonctionnaire et écrivain, qui est plus connu pour son rôle de Trésorier général de Perse pour lequel il a… … Wikipédia en Français
Auguste De Morgan — Pour les articles homonymes, voir Morgan. Auguste De Morgan Auguste De Morgan Naissance 27 … Wikipédia en Français
Augustus De Morgan — Auguste De Morgan Pour les articles homonymes, voir Morgan. Auguste De Morgan Auguste De Morgan (né le 27 juin& … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Loi de De Morgan

Lois de De Morgan

Sommaire

Énoncé en français

Énoncé mathématique

Justification

Généralisation

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

$\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

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Loi de De Morgan

Lois de De Morgan

Sommaire

Énoncé en français

Énoncé mathématique

Justification

Généralisation

Voir aussi

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link