Exemple 19.3.6.
Toute expression booléenne représente un circuit à interrupteurs. Par exemple, étant donné l’expression \((a \vee b) \wedge (a \vee b') \wedge (a \vee b)\text{,}\) nous pouvons construire le circuit de Figure 19.3.9.
Section 19.3 L’algèbre des circuits électriques
L’utilité des algèbres de Boole est devenue de plus en plus évidente au cours des dernières décennies avec le développement de l’ordinateur moderne. La conception des circuits des puces informatiques peut s’exprimer en termes d’algèbres de Boole. Dans cette section, nous allons développer l’algèbre de Boole des circuits électriques et des interrupteurs ; cependant, ces résultats peuvent facilement être généralisés à la conception des circuits intégrés informatiques.
Un interrupteur est un dispositif, situé en un certain point d’un circuit électrique, qui contrôle le passage du courant dans le circuit. Chaque interrupteur a deux états possibles : il peut être ouvert, et ne pas permettre le passage du courant dans le circuit, ou il peut être fermé, et permettre le passage du courant. Ces états sont mutuellement exclusifs. Nous exigeons que tout interrupteur soit dans l’un ou l’autre état—un interrupteur ne peut pas être ouvert et fermé en même temps. De plus, si un interrupteur est toujours dans le même état qu’un autre, nous désignerons les deux par la même lettre ; c’est-à-dire que deux interrupteurs étiquetés tous deux par la même lettre \(a\) seront toujours ouverts en même temps et fermés en même temps.
Étant donné deux interrupteurs, nous pouvons construire deux types fondamentaux de circuits. Deux interrupteurs \(a\) et \(b\) sont en série s’ils constituent un circuit du type illustré dans Figure 19.3.1. Le courant peut passer entre les bornes \(A\) et \(B\) dans un circuit en série uniquement si les deux interrupteurs \(a\) et \(b\) sont fermés. Nous notons cette combinaison d’interrupteurs \(a \wedge b\text{.}\) Deux interrupteurs \(a\) et \(b\) sont en parallèle s’ils forment un circuit du type qui apparaît dans Figure 19.3.2. Dans le cas d’un circuit en parallèle, le courant peut passer entre \(A\) et \(B\) si l’un ou l’autre des interrupteurs est fermé. Nous notons une combinaison en parallèle de circuits \(a\) et \(b\) par \(a \vee b\text{.}\)
Nous pouvons construire des circuits électriques plus complexes à partir de circuits en série et en parallèle en remplaçant n’importe quel interrupteur dans le circuit par l’un de ces deux types fondamentaux de circuits. Les circuits construits de cette manière sont appelés circuits série-parallèle.
Nous considérerons deux circuits comme équivalents s’ils se comportent de la même façon. C’est-à-dire que si nous réglons les interrupteurs dans des circuits équivalents exactement de la même manière, nous obtiendrons le même résultat. Par exemple, dans un circuit en série \(a \wedge b\) est exactement identique à \(b \wedge a\text{.}\) Remarquons que c’est exactement la loi commutative des algèbres de Boole. En fait, l’ensemble de tous les circuits série-parallèle forme une algèbre de Boole sous les opérations \(\vee\) et \(\wedge\text{.}\) Nous pouvons utiliser des diagrammes pour vérifier les différents axiomes d’une algèbre de Boole. La loi distributive, \(a \wedge ( b \vee c ) = (a \wedge b ) \vee ( a \wedge c )\text{,}\) est illustrée dans Figure 19.3.3. Si \(a\) est un interrupteur, alors \(a'\) est l’interrupteur qui est toujours ouvert quand \(a\) est fermé et toujours fermé quand \(a\) est ouvert. Un circuit qui est toujours fermé est \(I\) dans notre algèbre ; un circuit qui est toujours ouvert est \(O\text{.}\) Les lois pour \(a \wedge a' = O\) et \(a \vee a' = I\) sont illustrées dans Figure 19.3.4 et Figure 19.3.5, respectivement.
Théorème 19.3.7.
L’ensemble de tous les circuits est une algèbre de Boole.
Nous laissons en exercice la preuve de ce théorème pour les axiomes d’algèbre de Boole non encore vérifiés. Nous pouvons maintenant appliquer les techniques des algèbres de Boole à la théorie des circuits à interrupteurs.
Exemple 19.3.8.
Étant donné un circuit complexe, nous pouvons maintenant appliquer les techniques de l’algèbre de Boole pour le réduire à un circuit plus simple. Considérons le circuit de Figure 19.3.9. Puisque
\begin{align*}
(a \vee b) \wedge (a \vee b') \wedge (a \vee b) & = (a \vee b) \wedge (a \vee b) \wedge (a \vee b')\\
& = (a \vee b) \wedge (a \vee b')\\
& = a \vee ( b \wedge b')\\
& = a \vee O\\
& = a\text{,}
\end{align*}
nous pouvons remplacer le circuit plus complexe par un circuit contenant le seul interrupteur \(a\) et obtenir la même fonction.
Sous-section 19.3.1 Note historique
George Boole (1815–1864) fut la première personne à étudier les treillis. En 1847, il publia The Investigation of the Laws of Thought, un livre dans lequel il utilisait les treillis pour formaliser la logique et le calcul des propositions. Boole pensait que les mathématiques étaient l’étude de la forme plutôt que du contenu ; c’est-à-dire qu’il se préoccupait moins de ce qu’il calculait que de la façon dont il le calculait. Les travaux de Boole furent poursuivis par son ami Augustus De Morgan (1806–1871). De Morgan observa que le principe de dualité s’appliquait souvent en théorie des ensembles, comme l’illustrent les lois de De Morgan pour la théorie des ensembles. Il croyait, comme Boole, que les mathématiques étaient l’étude des symboles et des opérations abstraites.
La théorie des ensembles et la logique furent encore développées par des mathématiciens tels qu’Alfred North Whitehead (1861–1947), Bertrand Russell (1872–1970), et David Hilbert (1862–1943). Dans Principia Mathematica, Whitehead et Russell tentèrent de montrer la connexion entre les mathématiques et la logique par la déduction du système des nombres naturels à partir des règles de la logique formelle. Si les nombres naturels pouvaient être déterminés à partir de la logique elle-même, alors il en serait de même pour une grande partie du reste des mathématiques existantes. Hilbert tenta de construire les mathématiques en utilisant la logique symbolique d’une manière qui prouverait la cohérence des mathématiques. Son approche reçut un coup fatal de Kurt Gödel (1906–1978), qui démontra qu’il y aura toujours des problèmes « indécidables » dans tout système axiomatique suffisamment riche ; c’est-à-dire que dans tout système mathématique de quelque importance que ce soit, il y aura toujours des énoncés qui ne pourront jamais être prouvés vrais ou faux.
Comme cela se produit souvent, ces recherches fondamentales en mathématiques pures sont devenues par la suite indispensables dans une grande variété d’applications. Les algèbres de Boole et la logique sont devenues essentielles dans la conception des circuits intégrés à grande échelle que l’on trouve dans les puces informatiques d’aujourd’hui. Les sociologues ont utilisé les treillis et les algèbres de Boole pour modéliser les hiérarchies sociales ; les biologistes les ont utilisés pour décrire les biosystèmes.
