Lois de Morgan

Les yeux de Morgan sont des règles d'inférence utilisées dans la logique propositionnelle, qui établissent le résultat de la négation d'une disjonction et d'une conjonction de propositions ou de variables propositionnelles. Ces lois ont été définies par le mathématicien Augustus De Morgan.

Les lois de Morgan représentent un outil très utile pour démontrer la validité d'un raisonnement mathématique. Plus tard, ils ont été généralisés au concept d'ensembles du mathématicien George Boole.

Cette généralisation faite par Boole est tout à fait équivalente aux lois initiales de Morgan, mais elle est développée spécifiquement pour les ensembles plutôt que pour les propositions. Cette généralisation est également connue sous le nom de lois de Morgan.

Révision de la logique propositionnelle

Avant d'examiner en détail quelles sont les lois de Morgan et leur utilisation, il convient de rappeler quelques notions de base de la logique propositionnelle. (Pour plus de détails, voir l'article sur la logique propositionnelle).

Dans le domaine de la logique mathématique (ou propositionnelle), une inférence est une conclusion émise à partir d'un ensemble de prémisses ou d'hypothèses. Cette conclusion, associée aux prémisses susmentionnées, donne naissance à ce que l’on appelle le raisonnement mathématique.

Ce raisonnement doit pouvoir être démontré ou nié; c'est-à-dire que toutes les inférences ou conclusions d'un raisonnement mathématique ne sont pas valides.

Erreur

Une fausse inférence émise par certaines hypothèses supposées vraies est connue sous le nom d'erreur. Les sophismes ont la particularité d'être des arguments qui semblent corrects, mais mathématiquement ils ne le sont pas.

La logique propositionnelle est chargée de développer et de fournir avec précision des méthodes grâce auxquelles on peut, sans aucune ambiguïté, valider ou réfuter un raisonnement mathématique; c’est-à-dire déduire d’une conclusion valable de la prémisse Ces méthodes sont appelées règles d'inférence, dont font partie les lois de Morgan.

Propositions

Les éléments essentiels de la logique propositionnelle sont des propositions. Les propositions sont des déclarations sur lesquelles on peut dire si elles sont valides ou non, mais qu’elles ne peuvent pas être vraies ou fausses en même temps. Il ne devrait y avoir aucune ambiguïté à ce sujet.

De même que les nombres peuvent être combinés par des opérations d’addition, de soustraction, de multiplication et de division, les propositions peuvent être exploitées à l’aide du ou des connecteurs connus (logique): négation (, "non"), disjonction (V, "O"), conjonction (, "et"), conditionnelle (→, "si ..., alors ...") et biconditionnelle (↔, "oui, et seulement si").

Pour travailler plus généralement, au lieu de prendre en compte des propositions spécifiques, nous considérons des variables propositionnelles qui représentent des propositions et sont généralement désignées par des lettres minuscules p, q, r, s, etc.

Une formule propositionnelle est une combinaison de variables propositionnelles via une partie du connectif logique. En d'autres termes, il s'agit d'une composition de variables propositionnelles. Ils sont généralement désignés par des lettres grecques.

On dit qu'une formule propositionnelle en implique logiquement une autre lorsque celle-ci est vraie à chaque fois que la première est vraie. Ceci est noté par:

Lorsque l'implication logique entre deux formules propositionnelles est réciproque, c'est-à-dire lorsque l'implication précédente est également valable dans la direction opposée, les formules sont dites logiquement équivalentes et sont désignées par

L'équivalence logique est une sorte d'égalité entre les formules propositionnelles et permet de remplacer l'une par l'autre lorsque cela est nécessaire.

Lois de Morgan

Les lois de Morgan consistent en deux équivalences logiques entre deux formes propositionnelles, à savoir:

Ces lois permettent de séparer la négation d'une disjonction ou d'une conjonction, en tant que négations des variables impliquées.

Le premier peut être lu comme suit: la négation d’une disjonction est égale à la conjonction des négations. Et le second se lit comme suit: la négation d’une conjonction est la disjonction des négations.

En d'autres termes, refuser la disjonction de deux variables propositionnelles équivaut à la conjonction des négations des deux variables. De même, refuser la conjonction de deux variables propositionnelles équivaut à la disjonction des négations des deux variables.

Comme mentionné précédemment, la substitution de cette équivalence logique permet de démontrer des résultats importants, ainsi que les autres règles d'inférence existantes. Avec ceux-ci, vous pouvez simplifier de nombreuses formules propositionnelles, de sorte qu’elles soient plus utiles.

Voici un exemple de preuve mathématique utilisant des règles d'inférence, parmi ces lois de Morgan. Plus précisément, il est montré que la formule:

est équivalent à:

Ce dernier est plus simple à comprendre et à développer.

Démonstration

Il convient de mentionner que la validité des lois de Morgan peut être démontrée mathématiquement. Une solution consiste à comparer vos tables de vérité.

Ensembles

Les mêmes règles d'inférence et les notions de logique appliquées aux propositions peuvent également être développées en considérant des ensembles. C'est ce qu'on appelle l'algèbre de Boole, d'après le mathématicien George Boole.

Pour différencier les cas, il est nécessaire de changer la notation et de transférer en ensembles toutes les notions déjà vues de la logique propositionnelle.

Un ensemble est une collection d'objets. Les ensembles sont désignés par les lettres majuscules A, B, C, X, ... et les éléments d'un ensemble par les lettres minuscules a, b, c, x, etc. Lorsqu'un élément a appartient à un ensemble X, il est noté:

Quand il n'appartient pas à X, la notation est la suivante:

La manière de représenter les ensembles consiste à placer leurs éléments à l'intérieur de clés. Par exemple, l'ensemble des nombres naturels est représenté par:

Les ensembles peuvent également être représentés sans écrire une liste explicite de leurs éléments. Ils peuvent être exprimés sous la forme {:}. Les deux points sont lus "tels que". Une variable représentant les éléments de l'ensemble est placée à gauche des deux points et la propriété ou la condition à laquelle ils satisfont est placée à droite. C'est:

Par exemple, l'ensemble des entiers supérieurs à -4 peut être exprimé par:

Ou de manière équivalente, et plus abrégée, comme:

De même, les expressions suivantes représentent les ensembles de nombres pairs et impairs, respectivement:

Union, intersection et compléments d'ensembles

Nous verrons ensuite les analogues de la connectique logique dans le cas des ensembles, qui font partie des opérations de base entre ensembles.

Union et intersection

L'union et l'intersection des ensembles sont définies respectivement de la manière suivante:

Par exemple, considérons les ensembles:

Ensuite, vous devez:

Complément

Le complément d'un ensemble est formé par les éléments n'appartenant pas à cet ensemble (du même type que l'original). Le complément d'un ensemble A, est noté:

Par exemple, dans les nombres naturels, le complément de l'ensemble des nombres pairs est celui des nombres impairs, et inversement.

Pour déterminer le complément d’un ensemble, il faut clairement préciser dès le début l’ensemble universel ou principal des éléments considérés. Par exemple, il n'est pas égal de considérer le complément d'un ensemble sur les nombres naturels sur les nombres rationnels.

Le tableau suivant montre la relation ou l'analogie existant entre les opérations sur les ensembles précédemment définis et les fonctions de connexion de la logique propositionnelle:

Lois de Morgan pour les sets

Enfin, les lois de Morgan sur les ensembles sont les suivantes:

En mots: le complément d'une union est l'intersection des compléments, et le complément d'une intersection est l'union des compléments.

Une preuve mathématique de la première égalité serait la suivante:

La démonstration de la seconde est analogue.