Introduction à l'algèbre de Boole
Nous rappelons quelques éléments déjà évoqués dans les chapitres précédents, notamment lorsque nous avons découvert la porte NAND qui s'écrit s=¯a.b.
Il s'agit bien d'une expression, certes très simple, de l'algèbre de Boole. Nous en profitons pour rappeler des résultats déjà rencontrés :
Nous allons étudier dans ce chapitre les postulats de l'algèbre de Boole et un certain nombre de théorèmes que nous n'allons toutefois pas démontrer de manière exhaustive. La question de la démonstration sera toutefois abordée, ça ou là.
Postulats de l'algèbre de Boole
Bien qu'évidentes, les relations suivantes doivent être considérées comme postulats de l'algèbre de Boole. En fait, nous les avons déjà rencontrées, mais il est important de les redéfinir ici comme la base axiomatique de l'algèbre de Boole.
1.1=1, 0+0=0 ;
1.0=0.1=0, 0+1=1+0=1 ;
0.0=0, 1+1=1 ;
ˉ1=0 et ˉ0=1
Théorèmes de l'algèbre de Boole
Nous ne donnons pas une liste exhaustive, mais uniquement les théorèmes les plus importants. En termes de démonstration, si le théorème implique un nombre très limité de combinaisons des variables d'entrée, le théorème se démontre aisément par l'étude de toutes les combinaisons par table de vérité. Nous donnerons l'une ou l'autre démonstration lorsque le résultat n'est pas trivial, par la méthode de la table de vérité. Quand le théorème généralise un résultat vrai pour 2 entrées à n quelconque, la démonstration se fait généralement par récurrence.
Théorème 1 : absorption
0.X=0
1+X=1
X n'est pas nécessairement une variable primaire, X peut être une expression booléenne à priori de n'importe quelle complexité. Cette remarque vaudra pour toutes les expressions ultérieures.
Théorème 2 : éléments neutres
1.X=X
0+X=X
Théorème 3 : idempotence
X+X=X
X.X=X
On étend les résultats ci-dessus à un premier membre de n termes ou facteurs quelconque par récurrence :
X+X+X+...+X=X
X.X.X....X=X
Théorème 4 : complémentarité
ˉˉX=X
X+ˉX=1
X.ˉX=0
Théorème 5 : associativité
(a+b)+c=a+(b+c)=a+b+c
(a.b).c=a.(b.c)=a.b.c
Théorème 6 : commutativité
a+b=b+a
a.b=b.a
Théorème 7 : distributivité
a.(b+c)=a.b+a.c
a+(b.c)=(a+b).(a+c)
Sauriez-vous démontrer la deuxième relation du théorème 7 en construisant les tables de vérité des deux membres ?
Théorème 8 : simplification
a+ˉa.b=a+b
a.(ˉa+b)=a.b
Théorème 9 : redondance
a.b+ˉa.c=a.b+ˉa.c+b.c
Théorème 10 : lois de De Morgan
¯a+b=ˉa.ˉb
¯a.b=ˉa+ˉb
Ces deux expressions mettent en évidence la "dualité" entre les deux fonctions ET et OU et les variables directes et complémentées. C'est un concept important, beaucoup utilisé en électronique numérique. Nous verrons dans le chapitre suivant comment on peut l'utiliser efficacement.
Sauriez-vous démontrer comment les lois de De Morgan se généralisent à 3 entrées ? n entrées ?
En résumé
Nous avons listé quelques-unes des expressions les plus importantes de l'algèbre de Boole. D'autres pourraient encore être démontrées à partir de celles que nous venons de voir. Dans le chapitre suivant, nous allons les utiliser pour simplifier des expressions longues et obtenir des expressions plus simples, plus économes en termes de nombre de portes élémentaires à utiliser pour les réaliser sur simulateur, par exemple.
