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).
En logique classique, 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 identique à « (non A) et (non B) ».
Toujours en Logique classique, la négation de la conjonction de deux propositions est équivalente à la disjonction des négations des deux propositions, ce qui signifie que « non(A et B) » est identique à « (non A) ou (non B) ».
Sachant que la conjonction s'exprime par le signe : , la disjonction s'exprime par le signe : et la négation d'une formule s'écrit .
De ces quatre implications valides en logique classique, trois sont valides en logique intuitionniste, mais pas : .
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é.
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 |
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 |
Les énoncés de De Morgan se généralisent à propositions par récurrence, en utilisant l'associativité des lois et 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.
Et de ces quatre implications classiques, seule n'est pas valide en logique intuitionniste.
En logique intuitionniste, on n'a qu'une forme affaiblie des lois de De Morgan. Il n'y a que les implications
Démontrons la première implication. Il nous faut pour cela démontrer qu'en admettant on a . Il faut donc montrer que de on tire et que de on tire . Démontrons le premier. Cela revient à démontrer que de et de , on a . Or . Il suffit donc d'appliquer deux fois le modus ponens (élimination de l'implication).
(en) Eric W. Weisstein, « de Morgan's Laws », sur MathWorld
This article uses material from the Wikipedia Français article Lois de De Morgan, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Le contenu est disponible sous licence CC BY-SA 4.0 sauf mention contraire. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Français (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.