Il est maintenant temps d’examiner une autre des propriétés fréquemment utilisées dans la 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 et même 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. Formellement, elles s’expriment 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 la nécessité 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 avec les 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 aux deux côtés de cette expression, nous avons 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 deuxième, nous pouvons continuer à jouer avec l’expression que nous avions avant de faire le remplacement en ajoutant à nouveau une négation aux deux côtés, obtenant

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

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

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

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

\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 deuxième équivalence de DeMorgan

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

De plus, de manière tout à fait analogue, nous pouvons obtenir certaines formes supplémentaires, qui ne sont que des variations de celles que nous venons de revoir

\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 les disjonctions dans une expression. Ces lois se résument dans les deux équivalences suivantes :

Comme nous l’avons déjà vu jusqu’à présent, bien qu’il s’agisse d’un résultat connu, sa démonstration n’a rien de trivial. Bien que, pour compléter cette démonstration, il faille raisonner dans les deux sens, cette fois, je ne donnerai la démonstration que dans un seul sens, la démonstration dans le sens inverse restera comme un exercice pour le lecteur.

∧ – Distributivité

Pour démontrer que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)), le raisonnement suivant est utilisé :

Avec cela, il est démontré que \{(\alpha \wedge(\beta \vee\gamma))\}\vdash((\alpha \wedge \beta)\vee(\alpha \wedge \gamma)). Maintenant, c’est à vous de mettre à l’épreuve ce que vous avez appris et de vous aventurer à 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)) est obtenue à partir du raisonnement suivant :

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

Considérations Finales

Avec cette révision que nous avons faite 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 dans 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 rendre cela 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 noté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 car, personnellement, je l’ai trouvé plus simple de cette manière. Un bon exercice pour améliorer vos compétences dans ces domaines est de vous poser la question « Pourrai-je construire 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, car même si vous n’y parvenez pas, la pratique qui découle de la tentative vous apportera une meilleure compréhension des démonstrations et des méthodes utilisées en logique.