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é.
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.
Vrai au rang
Si vrai au rang :
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).
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 .
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Lieu dédié au corps et à l'esprit, le programme est déterminé par des objectifs multiples propices à l'exercice physique et à la flânerie. Bains, piscines et équipements sportifs se regroupent pour former une nouvelle condition, sorte d'exutoire au sein d' ...
2016
Métropoles et métropolisation semblent être les maîtres mots pour comprendre les phénomènes d’urbanisation du XXIème siècle globalisé. Mais, si on les considère sous l’angle de la planification territoriale et qu’on s’en saisit comme un objet d’urbanisme, ...
Ce projet consiste en la modélisation, la simulation et l’optimisation de l’échangeur de chaleur interne à la chambre de compression/détente pour le stockage d’énergie. Au cours de l’étude deux types d’analyses vont être présentées : une analyse numérique ...