Théorèmes de DeMorgan

Un mathématicien nommé DeMorgan a développé une paire de règles importantes concernant la complémentation de groupe dans l’algèbre de Boole.

Par complémentation de groupe, je fais référence au complément d’un groupe de termes, représenté par une longue barre sur plus d’une variable.

Vous devez vous rappeler du chapitre sur les portes logiques que l’inversion de toutes les entrées d’une porte inverse la fonction essentielle de cette porte de ET à OU, ou vice versa, et inverse également la sortie.

Donc, une porte OR avec toutes les entrées inversées (une porte Negative-OR) se comporte de la même manière qu’une porte NAND, et une porte AND avec toutes les entrées inversées (une porte Negative-AND) se comporte de la même manière qu’une porte NOR.

Les théorèmes de DeMorgan énoncent la même équivalence sous une forme  » inversée  » : que l’inversion de la sortie de n’importe quelle porte entraîne la même fonction que le type opposé de porte (AND vs. OR) avec des entrées inversées:

Une longue barre s’étendant sur le terme AB agit comme un symbole de groupement, et en tant que tel est entièrement différent du produit de A et B indépendamment inversé.

En d’autres termes, (AB)’ n’est pas égal à A’B’. Parce que le symbole « premier » (‘) ne peut pas être étiré sur deux variables comme le peut une barre, nous sommes obligés d’utiliser des parenthèses pour qu’il s’applique à l’ensemble du terme AB dans la phrase précédente.

Une barre, cependant, agit comme son propre symbole de groupement lorsqu’elle est étirée sur plus d’une variable.

Cela a un impact profond sur la façon dont les expressions booléennes sont évaluées et réduites, comme nous allons le voir.

Théorème de DeMorgan

Le théorème de DeMorgan peut être pensé en termes de rupture d’un long symbole de barre.

Lorsqu’une longue barre est rompue, l’opération directement sous la rupture passe de l’addition à la multiplication, ou vice versa, et les morceaux de barre rompus restent sur les variables individuelles. Pour illustrer :

Lorsque plusieurs  » couches  » de barres existent dans une expression, vous ne pouvez rompre qu’une barre à la fois, et il est généralement plus facile de commencer la simplification en rompant d’abord la barre la plus longue (la plus haute).

Pour illustrer, prenons l’expression (A + (BC)’)’ et réduisons-la en utilisant les théorèmes de DeMorgan :

Suivant le conseil de briser d’abord la barre la plus longue (la plus haute), je vais commencer par briser la barre couvrant toute l’expression dans un premier temps :

En conséquence, le circuit original se réduit à une porte ET à trois entrées avec l’entrée A inversée:

Vous ne devez jamais casser plus d’une barre en une seule étape, comme illustré ici :

Aussi tentant que cela puisse être d’économiser les étapes et de casser plus d’une barre à la fois, cela conduit souvent à un résultat incorrect, alors ne le faites pas !

Il est possible de réduire correctement cette expression en cassant d’abord la barre courte, plutôt que la barre longue :

Le résultat final est le même, mais davantage d’étapes sont nécessaires par rapport à l’utilisation de la première méthode, où la barre la plus longue était cassée en premier.

Notez comment, à la troisième étape, nous avons cassé la barre longue en deux endroits.

C’est une opération mathématique légitime, et ce n’est pas la même chose que de casser deux barres en une seule étape !

L’interdiction de casser plus d’une barre en une seule étape n’est pas une interdiction de casser une barre à plus d’un endroit.

Casser à plus d’un endroit en une seule étape est acceptable ; casser plus d’une barre en une seule étape ne l’est pas.

Vous vous demandez peut-être pourquoi des parenthèses ont été placées autour de la sous-expression B’ + C’, compte tenu du fait que je viens de les supprimer dans l’étape suivante.

Je l’ai fait pour souligner un aspect important mais facilement négligé du théorème de DeMorgan.

Puisqu’une barre longue fonctionne comme un symbole de regroupement, les variables anciennement regroupées par une barre brisée doivent rester regroupées de peur de perdre la bonne préséance (ordre d’opération).

Dans cet exemple, cela n’aurait vraiment aucune importance si j’oubliais de mettre des parenthèses après avoir cassé la barre courte, mais dans d’autres cas, cela pourrait être le cas.

Regardons cet exemple, en commençant par une expression différente :

Comme vous pouvez le voir, le maintien du regroupement impliqué par les barres de complémentation pour cette expression est crucial pour obtenir la bonne réponse.

Appliquons les principes des théorèmes de DeMorgan à la simplification d’un circuit de porte :

Comme toujours, notre première étape dans la simplification de ce circuit doit être de générer une expression booléenne équivalente.

Nous pouvons le faire en plaçant une étiquette de sous-expression à la sortie de chaque porte, au fur et à mesure que les entrées sont connues. Voici la première étape de ce processus :

Puis, nous pouvons étiqueter les sorties de la première porte NOR et de la porte NAND.

Lorsqu’il s’agit de portes à sortie inversée, je trouve plus facile d’écrire une expression pour la sortie de la porte sans l’inversion finale, avec une flèche pointant juste avant la bulle d’inversion.

Puis, au niveau du fil qui sort de la porte (après la bulle), j’écris l’expression complète et complétée.

Cela permet de s’assurer que je n’oublie pas une barre de complément dans la sous-expression, en me forçant à diviser la tâche d’écriture de l’expression en deux étapes :

Enfin, nous écrivons une expression (ou une paire d’expressions) pour la dernière porte NOR :

Maintenant, nous réduisons cette expression en utilisant les identités, propriétés, règles et théorèmes (DeMorgan) de l’algèbre de Boole :

Le circuit de porte équivalent pour cette expression très simplifiée est le suivant :

REVISION :

• Les théorèmes de DeMorgan décrivent l’équivalence entre les portes à entrées inversées et les portes à sorties inversées. En termes simples, une porte NON-ET est équivalente à une porte OU négatif, et une porte NOR est équivalente à une porte NON-ET négatif.
• Lorsqu’on « casse » une barre de complémentation dans une expression booléenne, l’opération directement sous la cassure (addition ou multiplication) s’inverse, et les morceaux de barre cassée restent sur les termes respectifs.
• Il est souvent plus facile d’aborder un problème en cassant la barre la plus longue (la plus haute) avant de casser toutes les barres situées sous elle. Vous ne devez jamais tenter de briser deux barres en une seule étape !
• Les barres de complémentation fonctionnent comme des symboles de regroupement. Par conséquent, lorsqu’une barre est rompue, les termes qui se trouvent sous elle doivent rester groupés. Des parenthèses peuvent être placées autour de ces termes groupés pour éviter de modifier la préséance.