Comme nous l’avons vu précédemment, l’algèbre booléenne utilise un ensemble de lois et de règles pour définir le fonctionnement d’un circuit logique numérique, les « 0 » et les « 1 » étant utilisés pour représenter une condition d’entrée ou de sortie numérique. L’algèbre booléenne utilise ces zéros et ces uns pour créer des tables de vérité et des expressions mathématiques permettant de définir le fonctionnement numérique d’une opération logique ET, OU et NON (ou inversion) ainsi que des moyens d’exprimer d’autres opérations logiques telles que la fonction XOR (Exclusive-OR).
Alors que l’ensemble des lois et des règles de George Boole nous permet d’analyser et de simplifier un circuit numérique, il existe deux lois au sein de son ensemble qui sont attribuées à Augustus DeMorgan (un mathématicien anglais du XIXe siècle) qui considère les opérations logiques NAND et NOR comme des fonctions NOT AND et NOT OR distinctes respectivement.
Mais avant d’examiner la théorie de DeMorgan plus en détail, rappelons les opérations logiques de base où A et B sont des variables binaires d’entrée logiques (ou booléennes), et dont les valeurs ne peuvent être que « 0 » ou « 1 » produisant quatre combinaisons d’entrée possibles, 00, 01, 10 et 11.
Tableau de vérité pour chaque opération logique
| Variable d’entrée | Conditions de sortie | |||||||||||
| A | B | AND | NAND | OR | NOR | |||||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | |
Le tableau suivant donne une liste des fonctions logiques courantes et leur notation booléenne équivalente où un « . » (un point) signifie une opération ET (produit), un » + » (signe plus) signifie une opération OU (somme), et le complément ou l’inverse d’une variable est indiqué par une barre sur la variable.
| Fonction logique | Notation booléenne |
| ET | A.B |
| OR | A+B |
| A | |
| NAND | A .B | NOR | A+B |
Théorie de DeMorgan
Les théorèmes de DeMorgan sont essentiellement deux ensembles de règles ou de lois développées à partir des expressions booléennes pour AND, OR et NOT en utilisant deux variables d’entrée, A et B. Ces deux règles ou théorèmes permettent de nier les variables d’entrée et de convertir une forme de fonction booléenne en une forme opposée.
Le premier théorème de DeMorgan stipule que deux variables (ou plus) NOR’ed ensemble est le même que les deux variables inversées (Complément) et AND’ed, tandis que le second théorème stipule que deux variables (ou plus) NAND’ed ensemble est le même que les deux termes inversés (Complément) et OR’ed. C’est-à-dire remplacer tous les opérateurs OR par des opérateurs AND, ou tous les opérateurs AND par un opérateur OR.
Premier théorème de DeMorgan
Le premier théorème de DeMorgan prouve que lorsque deux (ou plusieurs) variables d’entrée sont AND’ed et niées, elles sont équivalentes au OR des compléments des variables individuelles. Ainsi, l’équivalent de la fonction NAND sera une fonction OU négatif, prouvant que A.B = A+B. Nous pouvons montrer cette opération à l’aide du tableau suivant.
Vérification du premier théorème de DeMorgan à l’aide de la table de vérité
| Entrées | Sorties de la table de vérité pour chaque terme | |||||||
| B | A | A.B | A.B | A | B | A + B | ||
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | ||
Nous pouvons également montrer que A.B = A+B en utilisant des portes logiques comme indiqué.
Mise en œuvre de la première loi de DeMorgan à l’aide de portes logiques
L’arrangement de portes logiques supérieur de : A.B peut être mis en œuvre en utilisant une porte NAND standard avec des entrées A et B. La disposition de la porte logique inférieure inverse d’abord les deux entrées produisant A et B. Celles-ci deviennent alors les entrées de la porte OU. Par conséquent, la sortie de la porte OU devient : A+B
On voit donc ici qu’une fonction de porte OU standard avec des inverseurs (portes NOT) sur chacune de ses entrées est équivalente à une fonction de porte NAND. Ainsi, une porte NAND individuelle peut être représentée de cette manière car l’équivalence d’une porte NAND est un OU négatif.
Deuxième théorème de DeMorgan
Le deuxième théorème de DeMorgan prouve que lorsque deux (ou plusieurs) variables d’entrée sont soumises à un OU et à une négation, elles sont équivalentes au ET des compléments des variables individuelles. Ainsi, l’équivalent de la fonction NOR est une fonction ET négatif prouvant que A+B = A.B, et encore une fois, nous pouvons montrer cette opération en utilisant la table de vérité suivante.
Vérification du second théorème de DeMorgan à l’aide de la table de vérité
| Entrées | Sorties de la table de vérité pour chaque terme | |||||||
| B | A | A+B | A+B | A | B | A . B | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
Nous pouvons également montrer que A+B = A.B en utilisant l’exemple de portes logiques suivant.
Mise en œuvre de la deuxième loi de DeMorgan à l’aide de portes logiques
L’arrangement de portes logiques supérieur de : A+B peut être mis en œuvre en utilisant une fonction de porte NOR standard en utilisant les entrées A et B. L’arrangement de porte logique inférieur inverse d’abord les deux entrées, produisant ainsi A et B. Ainsi deviennent alors les entrées de la porte ET. Par conséquent, la sortie de la porte ET devient : A.B
Alors, nous pouvons voir qu’une fonction de porte ET standard avec des inverseurs (portes NOT) sur chacune de ses entrées produit une condition de sortie équivalente à une fonction de porte NOR standard, et une porte NOR individuelle peut être représentée de cette façon car l’équivalence d’une porte NOR est un négatif-ET.
Bien que nous ayons utilisé les théorèmes de DeMorgan avec seulement deux variables d’entrée A et B, ils sont également valables pour une utilisation avec des expressions à trois, quatre variables d’entrée ou plus, par exemple :
Pour une entrée à 3 variables
A.B.C = A+B+C
et aussi
A+B+C = A.B.C
Pour une entrée à 4 variables
A.B.C.D = A+B+C+D
et aussi
A+B+C+D = A.B.C.D
et ainsi de suite.
Les portes équivalentes de DeMorgan
Nous avons vu ici qu’en utilisant les théorèmes de DeMorgan, nous pouvons remplacer tous les opérateurs AND (.) par un OR (+) et vice versa, puis compléter chacun des termes ou variables de l’expression en l’inversant, c’est-à-dire les 0 en 1 et les 1 en 0 avant d’inverser la fonction entière.
Ainsi, pour obtenir l’équivalent de DeMorgan pour une porte AND, NAND, OR ou NOR, il suffit d’ajouter des inverseurs (NOT-gates) à toutes les entrées et sorties et de changer un symbole AND en un symbole OR ou de changer un symbole OR en un symbole AND comme le montre le tableau suivant.
Les portes équivalentes de DeMorgan
| Porte logique standard | Porte équivalente de DeMorgan | |
 |
 |
 |
 |
 |
 |
|
 |
 |
Donc, nous avons vu dans ce tutoriel sur le Thereom de DeMorgan que le complément de deux (ou plusieurs) variables d’entrée ET est équivalent au OU des compléments de ces variables, et que le complément de deux (ou plus) variables OR’ed est équivalent au AND des compléments de ces variables, tel que défini par DeMorgan.
.