Nous allons maintenant examiner une autre propriété fréquemment utilisée en logique propositionnelle, à savoir les démonstrations des lois de DeMorgan de Distribution de la conjonction et de la disjonction. L’utilisation de ces lois est courante en ce qui concerne la théorie des ensembles et, par extension, elles imprègnent toute la mathématique : de la théorie des probabilités à la topologie, elles sont même présentes dans l’électronique et la programmation. Comme d’habitude, nous examinerons les démonstrations de ces lois en utilisant les techniques de déduction que nous avons obtenues jusqu’à présent.

Lois de DeMorgan

Les lois de DeMorgan sont un ensemble d’équivalences qui formalisent la distribution des négations avec la conjonction et la disjonction. Elles s’expriment formellement par les équivalences suivantes :

\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)

\neg(\alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg \beta)

Ces équivalences prouvées peuvent être obtenues sans avoir besoin de faire une démonstration comme celle que nous avons faite jusqu’à présent, car nous pouvons nous appuyer sur les définitions qui relient les conjonctions aux disjonctions et un peu de jeu avec l’équivalence de la double négation et les substitutions. De la définition de la conjonction, il s’ensuit que :

(A \wedge B):= \neg(\neg A \vee \neg B)

En appliquant une négation des deux côtés de cette expression, nous obtenons que

\neg(A \wedge B):= \neg\neg(\neg A \vee \neg B)

Ensuite, par l’équivalence de la double négation, nous obtenons

\neg(A \wedge B)\dashv \vdash (\neg A \vee \neg B)

Enfin, en remplaçant A=\alpha et B=\beta, nous obtenons la première équivalence de DeMorgan

\boxed{\neg(\alpha \wedge \beta) \dashv \vdash (\neg\alpha \vee \neg \beta)}

Pour obtenir la seconde, nous pouvons continuer à jouer avec l’expression que nous avions avant de faire le remplacement en ajoutant à nouveau une négation des deux côtés, obtenant

\neg\neg(A \wedge B)\dashv \vdash \neg(\neg A \vee \neg B)

Et ensuite, par la double négation, nous obtenons que

\neg(\neg A \vee \neg B) \dashv \vdash (A \wedge B)

Si, dans cette dernière expression, nous remplaçons A=\neg\alpha et B=\neg\beta, nous obtenons que

\neg(\neg \neg\alpha \vee \neg \neg\beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)

Ce qui, en raison de l’équivalence de la double négation, conduira à la seconde équivalence de DeMorgan

\boxed{\neg( \alpha \vee \beta) \dashv \vdash (\neg\alpha \wedge \neg\beta)}

De plus, de manière complètement analogue, nous pouvons obtenir quelques formes supplémentaires, qui ne sont que des variations de celles que nous venons de passer en revue

\neg(\neg\alpha \wedge \beta) \dashv \vdash (\alpha \vee \neg \beta)

\neg(\neg\alpha \vee \beta) \dashv \vdash (\alpha \wedge \neg \beta)

\neg(\alpha \wedge \neg\beta) \ dashv \vdash (\neg\alpha \vee \beta)

\neg(\alpha \vee \neg\beta) \ dashv \vdash (\neg\alpha \wedge \beta)

Règles de Distributivité entre la Conjonction et la Disjonction

Comme son nom l’indique, ces règles nous permettent de distribuer les ensembles et disjoints dans une expression. Ces lois se résument par les deux équivalences suivantes :

Comme nous l’avons vu jusqu’à présent, bien que ce soit un résultat connu, sa démonstration n’est pas triviale. Pour compléter cette démonstration, il faut raisonner dans les deux sens. Dans ce cas, je ne donnerai la démonstration que dans un seul sens ; la démonstration dans le sens inverse est laissée comme exercice pour le lecteur.

∧ — Distributivité

Pour démontrer que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)), on a le raisonnement suivant.

Cela démontre que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Il est maintenant de votre ressort de mettre à l’épreuve ce que vous avez appris et de démontrer par vous-même que \{((\alpha \wedge \beta)\vee(\alpha \wedge \gamma))\}\vdash (\alpha \wedge(\beta \vee\gamma)).

∨ — Distributivité

La démonstration de \{(\alpha \vee(\beta \wedge\gamma))\}\vdash((\alpha \vee \beta)\wedge(\alpha \vee \gamma)) se fait à partir du raisonnement suivant :

Ceci est la moitié de la démonstration, il reste maintenant à la faire en sens inverse, mais cela est laissé comme exercice pour le lecteur :3

Considérations Finales

Avec cette révision des démonstrations des lois de De Morgan de distribution de la conjonction et de la disjonction, nous pouvons conclure notre étude sur les techniques de déduction de la logique propositionnelle et comment elles convergent vers la démonstration des lois de la logique classique, ou du moins les plus importantes.

Il est important de compléter toutes les démonstrations proposées pour renforcer les connaissances sur ces techniques. Pour le rendre un peu moins compliqué, il est très utile de comparer les démonstrations à la recherche de similitudes, car il est possible que la stratégie qui a fonctionné dans une démonstration fonctionne avec quelques variations pour en réaliser une autre.

Une dernière chose qui vaut la peine d’être soulignée est l’ordre que j’ai choisi pour développer ces démonstrations. Vous devez noter que chaque démonstration a utilisé les résultats de certaines des démonstrations précédentes. J’ai choisi cet ordre parce qu’il me semblait plus simple de cette manière. Un bon exercice pour améliorer vos compétences dans ces domaines est de vous poser la question «Puis-je organiser ces démonstrations dans un ordre différent en suivant cette même méthodologie ?». Je vous recommande vivement d’essayer d’obtenir ces démonstrations dans un ordre différent et d’utiliser chaque démonstration pour obtenir les suivantes parce que, même si vous n’y parvenez pas, la pratique qui découle de l’essai vous apportera une meilleure compréhension des démonstrations et des méthodes utilisées en logique.