Tout est dans le NON !

Aujourd'hui, j'ai décidé de vous présenter le pouvoir du NON. Pour être plus précis, je vais tenter d'expliquer comment créer l'algèbre de Boole, à partir du chiffre 0 et du seul opérateur logique NON.

Cette propriété connue est utilisée chaque jour pour créer les circuits logiques des puces de nos ordinateurs. Mais au delà de çà, ce principe me fascine car il permet de penser que "tout existe à partir du zéro et du NON".

Définissons tout d'abord quelques notions.

Opérateur : loi de transformation d'un ou plusieurs éléments d'un ensemble, vers un ou plusieurs éléments d'un autre ensemble (éventuellement le même).

Soit O un opérateur quelconque, on écrira :

O : E^a -> F^b

Ce qui signifie que l'opérateur O prend en entrée a éléments de l'ensemble E et génère en sortie b éléments de l'ensemble F.

Construire l'algèbre de Boole revient à exprimer tous les opérateurs logiques unaires et binaires, à partir de l'opérateur NON.

A partir de la définition d'un opérateur, on se place dans le cas suivant :

E = F = {0, 1}
b = 1
a = 1 (pour les opérateurs unaires)
a = 2 (pour les opérateurs binaires)

Autrement dit : les opérateurs logiques
unaires sont les transformations d'un élément 0 ou 1 en un autre élément valant 0 ou 1. Les opérateurs logiques binaires sont les transformations d'un couple d'éléments (0,0) , (0,1) , (1,0) ou (1,1) en un seul élément valant 0 ou 1.

Tables de vérité

La table de vérité d'un opérateur est le tableau qui donne pour chaque élément en entrée, l'élément correspondant en sortie. Voici quelques exemples :

Table de vérité de l'opérateur unaire identité :

0	0
1	1

Table de vérité de l'opérateur unaire négation :

0	1
1	0

Pour les opérateurs binaires, on peut représenter la table de vérité sous la forme d'un tableau à deux dimensions :

Table de vérité de l'opérateur binaire OU :

	0	1
0	0	1
1	1	1

Table de vérité de l'opérateur binaire ET :

	0	1
0	0	0
1	0	1

Les nombres en gras représentent les éléments en entrée, les autres les éléments en sortie. Pour connaître le résultat, il suffit de choisir une ligne et une colonne et de lire le résultat. Par exemple : 1 ET 1 = 1

Ici l'ordre des éléments en entrée n'a pas d'importance, mais lorsque ce sera le cas, on lira en premier la ligne, puis la colonne.

Codage des opérateurs logiques

Comment connaître tous les opérateurs logiques ? Pour cela, nous allons utiliser une méthode de codage qui va nous permettre de les compter et de n'en oublier aucun. Pour coder un opérateur, nous allons d'abord réécrire sa table de vérité de manière "compacte".

Par exemple, pour les opérateurs unaires, on constate que la première colonne est inutile : le 0 et le 1 seront toujours à la même place. On va donc accoler les chiffres restants, c'est à dire :

Codage de l'opérateur unaire identité : 10
Codage de l'opérateur unaire négation : 01

Vous constaterez qu'on a inversé les nombres, afin que le résultat de l'élément 0 soit situé à droite et celui de l'élément 1 à gauche. Ce choix est plus logique, car on lit les nombres de droite à gauche.

On peut en déduire qu'il existe seulement 4 opérateurs logiques unaires :

• 00 : L'opérateur zéro
• 01 : L'opérateur négation
  
• 10 : L'opérateur identité
• 11 : l'opérateur un

On remarque que le premier opérateur est la négation du dernier (1 n'est pas nécéssaire car c'est la négation du 0).

De même, le deuxième opérateur (le fameux NON) est la négation du troisième (l'identité).

Donc seul la moitié de ces opérateurs semble utile (0 et NON) puisque les deux autres peuvent s'obtenir en rajoutant l'opérateur NON.

Nous pouvons donc exprimer tous les opérateurs unaires en utilisant le 0 et le NON (que nous noterons "!") :

On note A l'élément de départ, appliqué à chaque opérateur unaire (souvenez-vous que A peut prendre la valeur 0 ou 1) :

• 00(A) = 0
• 01(A) = !A
• 10(A) = A
• 11(A) = !0 (non, je n'utiliserai pas le 1 !)
  

Codage des opérateurs logiques binaires :

Nous allons maintenant appliquer cette méthode pour d'abord coder, puis pour exprimer tous les opérateurs logiques binaires en fonction de l'opérateur NON.

En reprenant les tables de vérité, on va supprimer les éléments en entrée, comme on l'a fait pour les opérateurs unaires, puis on va accoler les 4 éléments en sortie. De maniuère générale, la table suivante :

	0	1
0	A	B
1	C	D

Deviendra le code : DCBA

Par exemple, les codes des opérateurs OU et ET sont respectivement 1110 et 1000.

A nouveau, on voit qu'il ne peut y avoir que 16 opérateurs logiques binaires distincts (il y a quatres chiffres binaires, soit 2^4 = 16 possibilités).

Comme nous l'avons fait pour les opérateurs unaires, il nous suffira de calculer les 8 premiers opérateurs, les 8 suivants étant symétriques (à l'opérateur NON près)

Avant de pouvoir coder les opérateurs, il nous faut cependant étendre le domaine de validité de l'opérateur logique unaire NON aux opérateurs logiques binaires, en mathématiques, on noterait :

NON : E -> F
NON(A) = !A

NON ET : E^2 -> F
NON ET(A,B) = A!B = NON(A) ET NON(B)

Je dois reconnaître ici que j'ai un peu triché en annonçant que l'on n'aurait besoin que du NON et du 0. En effet, pour étendre l'opérateur NON aux opérateurs binaires, nous devons le combiner avec un opérateur binaire quelconque , ici on a choisi ET.

Mais ce qui est important, c'est que l'on aurait pu prendre n'importe quel opérateur non trivial (comme 0 ou 1) : l'opérateur ET est donc uniquement là pour faire la figuration, bien qu'il nous permette d'accéder au monde merveilleux des opérateurs binaires.

Donc muni de notre opérateur étendu "!" (à la fois unaire et binaire), tentons d'exprimer les opérateurs binaires logiques en utilisant toujours uniquement les symboles 0 et "!" avec un peu de calcul, on obtient :

• 0000(A,B) = 0
• 0001(A,B) = !(!A!!B)
• 0010(A,B) = !(!A!B)
• 0011(A,B) = !A
• 0100(A,B) = !(A!!B)
  
• 0101(A,B) = !B
  
• 0110(A,B) = (!A!B)!(A!!B)
  
• 0111(A,B) = A!B
  
• 1000(A,B) = !(A!B)
  
• 1001(A,B) = (A!B)!(!A!!B)
• 1010(A,B) = B
  
• 1011(A,B) = A!!B
  
• 1100(A,B) = A
  
• 1101(A,B) = !A!B
  
• 1110(A,B) = !A!!B
  
• 1111(A,B) = !0 (on n'a toujours pas besoin du 1...)
  

En exprimant tous les opérateurs logiques à l'aide de 0 et "!", nous pouvons maintenant réaliser n'importe quel calcul dans l'algèbre de Boole. Il suffit d'assembler les différents opérateurs dont on a besoin, d'obtenir la formule écrite avec les symboles "!", "0" et bien sûr les éléments en entrée (par exemple A et B).

Remarque : Pour exprimer une opération quelconque en fonction de A, B 0 et "!", il suffit de la décomposer en des opérateurs dont on connait le code, d'effectuer l'opération sur le code des opérateurs, puis de lire l'expression correspndante dans le tableau ci-dessus, par exemple :
A correspond à l'opérateur 1100, B, à l'opérateur 1010, donc l'expression A OU B correspond à l'opérateur (1100 OU 1010) = 1110, soit l'expression !A!!B

On peut ensuite réaliser le circuit de portes logiques en utilisant uniquement la porte NON ET : c'est la dernière étape dans la conception d'un circuit électronique.

Ci dessous, un circuit logique simple qui réalise l'opération OU (opérateur 1110 dans notre liste), avec les entrées E1 et E2, la sortie S et trois portes logiques NON ET. Les entrées sont d'abord reliées chacune à une porte NON, puis les sorties respectives sont reliées entre elles à une même porte NON ET, qui donne le résultat final S.



En lisant ce schéma, on peut tout à fait vérifier la formule 1110(E1,E2) = !E1!!E2 ou si vous préférez 1110(E1,E2) = (!E1)!(!E2).

Cliquez-ici pour voir les circuits d'autres opérateurs logiques, réalisés avec la porte NON ET (également appelé NAND).

Enfin, on peut bien sûr étendre cette méthode pour manipuler autant d'entrées qu'on le souhaite et ainsi réaliser des circuits plus élaborés (sommateurs, compteurs, multiplexeurs...) comme on en trouve au coeur des puces électroniques...

Voilà, cet article est terminé. J'espère que cela vous aura intéressé. J'aimerais avoir votre avis ou vos réflexions sur ce sujet ou sur l'algèbre de Boole en général... Que pensez-vous également de cette méthode de codage (on pourrait presque parler de classification) des opérateurs logiques ? Que changeriez-vous dans le codage pour obtenir une classification des opérateurs plus élégante ?

Pour terminer sur une note plus spirituelle, je pense sincèrement que derrière l'opérateur NON se profile toute la puissance génératrice du zéro. Une sorte de preuve que tout ce qui existe peut-être généré à partir de ce qui n'existe pas (à partir de rien en fait)... mais il s'agit bien sûr d'un sentiment personnel.

Pour plus d'informations sur l'opérateur NON et sur l'histoire du zéro, je vous recommande le livre "A propos de rien, une histoire du zéro" (Robert Kaplan).

A très bientôt.