Grâce au chapitre précédent, on sait enfin comment sont représentées nos données les plus simples avec des bits. On n'est pas encore allés bien loin : on ne sait pas comment représenter des bits dans notre ordinateur ou les modifier, les manipuler, ni faire quoi que ce soit avec. On sait juste transformer nos données en paquets de bits (et encore, on ne sait vraiment le faire que pour des nombres entiers, des nombres à virgule et du texte...). C'est pas mal, mais il reste du chemin à parcourir ! Rassurez-vous, ce chapitre est là pour corriger ce petit défaut. On va vous expliquer quels traitements élémentaires notre ordinateur va effectuer sur nos bits.
Les portes logiques de base.
Les portes logiques sont des circuits qui possèdent des sorties et des entrées sur lesquelles on va placer ou récupérer des bits. Les entrées ne sont rien d'autre que des morceaux de « fil » conducteur sur lesquels on envoie un bit (une tension). À partir de là, le circuit électronique va réagir et déduire le bit à placer sur chaque sortie. Tous les composants d'un ordinateur sont fabriqués avec ce genre de circuits.
Les portes logiques ont différent symboles selon le pays et l'organisme de normalisation :
La porte NON.
La première porte fondamentale est la porte NON, qui agit sur un seul bit : la sortie d'une porte NON est exactement le contraire de l'entrée.
Pour simplifier la compréhension, je vais rassembler les états de sortie en fonction des entrées pour chaque porte logique dans un tableau que l'on appelle table de vérité.
La porte ET.
La porte ET possède plusieurs entrées, mais une seule sortie. Cette porte logique met sa sortie à 1 quand toutes ses entrées valent 1. Dans le cas le plus simple, une porte ET possède deux entrées.
Certaines portes ET ont plus de deux entrées, et peuvent en avoir 3, 4, 5, 6, 7, etc. Là encore, leur sortie ne vaut 1 que si toutes les entrées valent 1 : dans le cas contraire, la sortie de la porte ET vaut 0. Dit autrement, si une seule entrée vaut 0, la sortie de la porte ET vaut 0.
La porte NAND.
La porte NAND donne l'exact inverse de la sortie d'une porte ET. En clair, sa sortie ne vaut 1 que si au moins une entrée est nulle. Dans le cas contraire, si toutes les entrées sont à 1, la sortie vaut 0. Dans le cas le plus simple, une porte NAND a deux entrées. Certaines portes NAND ont plus de deux entrées : elles peuvent en avoir 3, 4, 5, 6, 7, etc. Là encore, leur sortie ne vaut 1 que si au moins une entrée est nulle : dans le cas contraire, la sortie de la porte NAND vaut 0. Dit autrement, si toutes les entrées sont à 1, la sortie vaut 0.
Au fait, si vous regardez le schéma de la porte NAND, vous verrez que son symbole est presque identique à celui d'une porte ET : seul un petit rond (blanc pour ANSI, noir pour DIN) ou une barre (CEI) sur la sortie de la porte a été rajouté. Il s'agit d'une sorte de raccourci pour schématiser une porte NON.
La porte OU.
La porte OU est une porte dont la sortie vaut 1 si et seulement si au moins une entrée vaut 1. Dit autrement, sa sortie est à 0 si toutes les entrées sont à 0. Dans le cas le plus simple, la porte OU possède deux entrées, ainsi qu'une seule sortie. Elle met sa sortie à 1 quand au moins une de ses entrées vaut 1. Certaines portes OU ont plus de deux entrées. Là encore, leur sortie est à 0 si et seulement si toutes les entrées sont à 0 : si une seule entrée est à 1, alors la sortie vaut 1.
La porte NOR.
La porte NOR donne l'exact inverse de la sortie d'une porte OU. Là encore, il en existe une version avec deux entrées, et des versions avec plus de deux entrées. Les tableaux et symboles qui suivent sont ceux d'une porte NOR à deux entrées.
La porte XOR.
Avec une porte OU, deux ET et deux portes NON, on peut créer une porte nommée XOR. Cette porte est souvent appelée porte OU exclusif. Sa sortie est à 1 quand les deux bits placés sur ses entrées sont différents, et vaut 0 sinon.
La porte XNOR.
La porte XOR possède une petite sœur : la XNOR. Sa sortie est à 1 quand les deux entrées sont identiques, et vaut 0 sinon (elle est équivalente à une porte XOR suivie d'une porte NON).
Fabriquer des portes logiques complexes à partir de portes basiques.
Pour information, il est possible de recréer toutes les portes logiques existantes à partir de seulement quelques portes de base. Par exemple, il est possible de construire toute porte logique, et donc tout circuit numérique, à partir de portes NON, ET et OU. Ces trois portes de base suffisent à créer toutes les autres. La même chose est possible avec uniquement des portes NAND ou seulement des portes NOR. Dans cette section, nous allons voir comment cela est possible.
L'idée est tout simplement qu'on peut obtenir une porte logique en combinant deux autres, parfois plus. La porte ainsi obtenue par combinaison est donc une porte "superflue", elle n'est pas une porte de base. Cela n'a rien d'étonnant et on peut déjà se rendre compte que certaines portes sont l'inverse l'une de l'autre. Par exemple, la porte ET et la porte NAND sont l'inverse l'une de l'autre : il suffit d'en combiner une avec une porte NON pour obtenir l'autre. Même chose pour les portes OU et NOR, ainsi que les portes XOR et NXOR.
Une idée serait de retirer les portes NOR, NAND et NXOR, qui peuvent se calculer en combinant une porte NON avec un porte ET ou OU. Mais la question est : faut-il garder les portes ET/OU/XOR ou les portes NOR/NAND/NXOR ? L'un de ces choix est plus pertinent que l'autre, mais nous ne savons pas lequel pour le moment. Intuitivement, on se doute que l'on devrait retirer les portes NOR, NAND et NXOR, mais n'allons pas trop vite en besogne, nous ne sommes pas à l'abri d'une surprise. Dans ce qui suit, nous allons garder les portes NAND, NOR et NXOR.
L'élimination des portes XOR et NXOR.
Pour commencer, nous allons montrer que les portes XOR/NXOR peuvent se fabriquer à partir de portes NON, ET/NAND et OU/NOR. 
Pour la porte XOR, il y a plusieurs possibilités, plusieurs combinaisons de portes logiques faisant l'affaire. La plus simple s'obtient à partir des techniques que l'on verra au chapitre suivant, mais on peut aussi la déduire d'un raisonnement assez simple. Pour cela, partons du tableau vu plus haut :
On voit que la sortie est à 1 dans deux situations : soit l'entrée n°1 est à 1 et l'entrée 2 à 0, soit c'est l'inverse. L'idée est de créer un circuit qui vérifie si on est dans la première situation, un circuit pour l'autre situation, et de quoi combiner la sortie de ces deux circuits. Les deux circuits de vérification ont une sortie à 1 si les entrées sont adéquates et 0 sinon. Le circuit qui vérifie la première situation est composé d'une porte NON sur l'entrée 2 et d'une porte ET. Le circuit pour la seconde situation est le même, sauf que la porte NON est placée sur l'entrée 2. La sortie des deux circuits est combinée avec une porte OU, car une seule des deux situations rencontrées met la sortie à 1. Le circuit obtenu est le suivant :
Une autre possibilité est la suivante. L'idée est que la sortie d'une porte XOR est à 1 quand au moins une des entrées est à 1, et qu'au moins une des entrées est à zéro. Pour vérifier qu'une des entrées est à 1, il suffit d'une porte OU : par définition sa sortie sera à un si l'une des entrées est à 1. Pour vérifier que au moins l'une des entrées est à zéro, il suffit d'utiliser une porte NAND, qui sort un 1 quand l'une des entrées est à zéro, par définition. Et cette fois, on combine le résultat des deux vérifications avec une porte ET.
Il est possible de créer une porte NXOR en plaçant une porte NON en sortie d'une porte XOR, mais il est aussi possible de faire plus simple. Par exemple, on peut procéder de la manière suivante. Le circuit suivant est simplement basé sur le fait que la porte NXOR sort un 1 soit quand ses deux entrées sont à 1, soit quand elles sont toutes deux à 0. La porte ET a sa sortie à 1 dans le premier cas, quand les deux entrées sont à 1, alors que la porte NOR (une OU suivie d'une NOT) a sa sortie à 1 quand les deux entrées sont à 0. La porte finale combine le résultat de la porte NOR avec celui de la porte ET pour obtenir un résultat valide. Vu que la sortie doit être à 1 dans l'un des deux cas, c'est à dire quand l'une des deux portes ET/NOR est à 1, la porte finale est naturellement une porte OU.
L'élimination des portes ET et OU.
Vu que les portes XOR et NXOR sont superflues, il nous reste les portes NON, ET, OU, NOR et NAND. Dans cette section, nous allons montrer que le ET et le OU peuvent se fabriquer avec d'autres portes, mais sans passer par la solution évidente qui consiste à inverser la sortie d'une NAND ou d'une NOR. Nous allons voir que toute porte peut être créée avec seulement des portes ET et NON, sans porte OU. Nous allons aussi voir qu'il est possible de faire de même, mais avec seulement des portes NON et des portes OU, sans porte ET.
L'élimination de la porte OU.
Pour montrer que seules les portes NON et ET suffisent, il suffit de créer une porte OU avec seulement des portes NON et ET.
Premièrement, il est possible de créer une porte NOR avec des NON et des ET. Ce qui réalisée avec le circuit ci-dessous.
On peut créer une porte OU en ajoutant une porte NON au bout du circuit précédent, pour inverser son résultat.
L'élimination de la porte ET.
Pour montrer que seules les portes NON et OU suffisent, il suffit de créer une porte ET avec seulement des portes NON et OU.
Premièrement, il est possible de créer une porte NAND avec des NON et des OU, ou encore avec des NON et des NAND. Ce qui réalisée avec le circuit ci-dessous.
On peut aussi créer une porte ET en ajoutant une porte NON au bout du circuit précédent pour inverser son résultat.
L'élimination de la porte NON.
Dans la section précédente, nous avons vu qu'il existe deux possibilités : soit on supprime les portes ET/NAND et on garde les portes OU/NOR, soit on fait l'inverse. Les deux possibilités sont équivalentes et permettent chacune de fabriquer toutes les portes logiques restantes. Les deux solutions laissent respectivement les portes logiques suivantes : NON, OU et NOR pour la première solution, NON, ET et NAND pour la seconde. Vu que le NAND est l'inverse du ET et que le NOR est l'inverse du OU, on peut simplifier et ne garder que deux portes logiques. Cela donne alors quatre possibilités : NON et ET, NON et NAND, NON et OU, NON et NOR. Les quatre possibilités permettent chacune de créer n'importe quel circuit.
Cependant, il est possible d'éliminer le NON, en utilisant une porte NAND ou une porte NOR. Ce qui permet de fabriquer tout circuit avec seulement un type de porte logique : soit on construit le circuit avec uniquement des NAND, soit avec uniquement des NOR. L'intérêt de n'utiliser qu'un seul type de porte est que les circuits intégrés comportent plusieurs portes d'un même type ; utiliser un seul type de porte évite d'utiliser différents types de circuits intégrés et de gaspiller des portes non utilisées. Pour donner un exemple, sachez que les ordinateurs chargés du pilotage et de la navigation des missions Appollo étaient intégralement conçus avec des portes NOR.
Voyons comment fabriquer une porte NON avec une porte NAND. Pour cela, il suffit d'envoyer le bit à inverser sur les deux entrées d'une porte NAND. Pour comprendre pourquoi cela marche, il faut imaginer que la porte NAND est composée d'une porte ET suivie par une porte NON. L'idée est que le bit envoyé va subir un ET avec lui-même, avant d'être inversé. Or, on a obligatoirement, pour tout bit a : formula_1. En clair, le passage dans le ET ne changera pas le bit, mais la porte NON l'inversera. On peut faire la même chose avec des portes NOR, la porte NAND n'étant pas la seule à avoir ce privilège. Là encore, la porte NON est fabriquée en envoyant le bit à inverser sur les deux entrées d'une porte NOR, afin que le OU entre le bit et lui-même laisse celui-ci inchangé, mais le NON l'inverse.
Créer les autres portes logiques est alors un jeu d'enfant avec ce qu'on a appris dans les sections précédentes. Il suffit de remplacer les portes NON et ET par leurs équivalents fabriqués avec des NAND.