Patrimonialisation scientifique et technique : L'algèbre de Boole, une logique à la source de l'informatique (9/10 - année 2020)

Publié par ACONIT (Association pour un Conservatoire de l'Informatique et de la Télématique), le 16 novembre 2020   4k

Par René Gindre et Jean-Louis Gondol (membres du bureau de l’ACONIT)


Aujourd'hui encore, lorsque nous allumons notre ordinateur pour accéder au monde du numérique, nous utilisons massivement l’algèbre de Boole sans le savoir. Une telle intégration dans notre société technologique n’est pas le fruit du hasard. L’ACONIT a consacré à ce sujet un outil pédagogique pour mieux appréhender sa spécificité et son apport pratique. Cet article en développe les éléments clés.


George Boole, un théoricien de l’algèbre

Logicien et mathématicien autodidacte britannique, George Boole, mort en 1864, est le créateur de la logique moderne, fondée sur une structure algébrique et sémantique que l'on appelle algèbre de Boole en son honneur. De 1844 à 1854, il crée une algèbre binaire, dite booléenne, n'acceptant que deux valeurs numériques : 0 et 1. Cette algèbre, qui présente, entre autre, une affinité avec les états électriques “inactif” et “actif”, aura de nombreuses applications en téléphonie et en informatique.

Les travaux précurseurs de Boole, s'ils sont théoriques à la base, n'en trouveront pas moins des applications primordiales. Dès 1867 en effet, le logicien Charles Sanders Peirce, qui était aussi professeur de mathématiques et d'astronomie à l'université d’Harvard, commence à diffuser les idées principales de l'algèbre de Boole aux États-Unis.

Fig. 1 : Portrait de George Boole et le « piano logique » de Stanley Jevons - à droite -. Photo du musée Powerhouse de Sydney (source Wikicommons)


Les premières applications de l’algèbre de Boole

En 1869, l'économiste et logicien William Stanley Jevons construit la première machine logique d'importance notable, qu'il présente à la Royal Society de Londres l'année suivante. C'est la première machine qui permet d'utiliser les principes de l'algèbre de Boole pour obtenir automatiquement la solution d'un problème logique, de telle sorte que la conclusion qui pourrait être tirée d'un ensemble donné de prémisses puisse également être obtenue de façon mécanique. Elle est créée pour illustrer les avantages de la nouvelle logique booléenne sur la théorie des syllogismes d'Aristote. Du fait de sa ressemblance avec un piano, cette machine est connue à cette époque sous le nom de « piano logique ».

En 1881, Alan Marquand, professeur à l'université de Princeton, invente à son tour une nouvelle machine logique qui apporte quelques améliorations au piano logique de Jevons, et envisage, avec l'aide de Charles Sanders Peirce, de résoudre des problèmes logiques et arithmétiques en construisant un système électrique.

Durant les années 1930, l'Américain Claude Shannon se rend compte qu'il est possible d'appliquer l'algèbre de la logique à la conception et à l'analyse de circuits électriques. Il avait étudié minutieusement la théorie de Boole dans son œuvre fondamentale, Les Lois de la pensée et dans son ouvrage intitulé L'analyseur différentiel. Il prend conscience des similitudes et de la ressemblance qui existent entre les opérations effectuées par les tout nouveaux relais électroniques et la logique de Boole. En 1938, il parvient à montrer, dans sa thèse intitulée Analyse symbolique des relais et des circuits commutateurs, comment cette théorie peut être appliquée à la conception et à la simplification de circuit. En 1938, Claude Shannon optimise l'usage d'interrupteurs commandés (relais, tubes à vide, et plus tard les transistors) en s'appuyant sur l'algèbre de Boole. Ces constatations permirent la construction de calculateurs tels que l'ENIAC (1945), et plus tard des ordinateurs, grâce à la réalisation de circuits logiques et de registres cadencés par une horloge.


Comment fonctionne l'algèbre de Boole

Aussi appelé calcul booléen, cette algèbre est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques, ce qui permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions.

L'ACONIT a développé un panneau interactif qui vient compléter les panneaux de son exposition « Au doigt et à l'oeil ». Ce panneau explique comment l'algèbre de Boole est utilisée dans le cadre d'additions de bits, puis d'addition d'octets. Les tables de vérité des portes ET, OU, OU exclusif, et ET-NON (NAND) sont affichées et câblées, de telle sorte que l'utilisation d'interrupteurs et de LEDs permet d'en comprendre le fonctionnement. Après manipulation par un opérateur, le mode automatique balaie la table de vérité associée, ligne par ligne, montrant ainsi le comportement d’un additionneur de bits. Les valeurs peuvent être affichées en octal, décimal ou hexadécimal.

On trouve dans le commerce des circuits intégrés contenant des portes ET, OU et OU exclusif, mais le prix des circuits intégrés contenant des portes NAND est beaucoup plus attractif. Les réalisations à partir de portes NAND nécessitent un nombre de portes plus important qu'avec des portes ET, OU et OU exclusif, pour atteindre le même objectif, mais elles sont plus économiques, et donc méritent d'être mentionnées. Leur utilisation complexe et la compréhension difficile des réalisations ont guidé le choix de ne pas les utiliser pour le panneau de l'ACONIT.

Fig. 2 : Les deux fonctions initiales de l'algèbre de Boole - ou portes logiques - et leur table de vérité (source ACONIT)


Intégration, postérité et conclusion

Au cours de l'évolution de l'informatique, ces portes logiques seront concrètement réalisées grâce à des interrupteurs programmables : des relais à l'époque de Shannon, puis des lampes à vide, puis des transistors. Pour exemple, l'ENIAC a nécessité 17468 tubes à vide et 1500 relais. Il faut deux transistors par portes, cinq portes pour réaliser une addition de deux bits, soit 10 transistors, et donc 80 transistors pour l'addition de deux octets. Le panneau de l'ACONIT permet de comprendre pourquoi les microprocesseurs contiennent tant de transistors (1,7 milliard de transistors pour un microprocesseur récent Intel i3), compte tenu du fait qu'il y a de nombreux additionneurs et, sur le même principe, des multiplexeurs, des registres, des mémoires... et qu'ils manipulent des entités allant jusqu'à 64 bits !

Quand on pense à la complexité de la structure des microprocesseurs actuels qui s'appuie sur des tables de logique découvertes en 1850 par George Boole, et que celles-ci constituent toujours la base de l'informatique d'aujourd'hui, on se rend compte combien ces découvertes ont été fondamentales !


Fig. 3 : La partie fonctionnelle du panneau pédagogique de l'ACONIT consacré à l'algèbre de Boole (source ACONIT)

Pour aller plus loin :

Site Wikipédia consacré à George Boole : suivre le lien

(contextualisation de cet article par Xavier Hiron, ACONIT)