Algèbre de Boole

Constitue une partie des travaux de Georges Boole (1815-1864) relatif à l'élaboration d'une base mathématique au raisonnement logique.
Une algèbre de Boole est la donnée de :
· un ensemble E,
· deux éléments particuliers de E : 0 et 1,
· deux opérations binaires sur E : + et . (le . sera parfois omis),
· une opération unaire sur E.
qui vérifient les axiomes suivants : soient

commutativité a+b=b+a ab=ba
associativité (a+b)+c=a+(b+c) (ab)c=a(bc)
distributivité a(b+c)=ab+ac a+(bc)=(a+b)(a+c)
éléments neutres a+0=a a1=a
complémentation a+ =1 a =0

Les théorèmes suivants peuvent être déduits :

idempotence a+a=a aa=a
absorption a+ab=a a(a+b)=a
De Morgan (dualité) = . = +
éléments absorbants a+1=1 a0=0

? Démontrer que aa=a
On se restreind ici à l'algèbre de Boole minimale, où . Cette algèbre peut être interprétée comme suit :
· 1 est interprété ``vrai'' et 0 ``faux'',
· + est interprété ``ou'' (disjonction logique)
· . est interprété ``et'' (conjonction logique)
· - est interprété ``non'' (négation logique)

? L'algèbre des ensembles munis des opérations d'union, d'intersection et de complémentation est elle une algèbre de boole ?
Tables de vérité et portes logiques
On a les tables de vérités suivantes :

a
0 1
1 0

a b a + b
0 0 0
0 1 1
1 0 1
1 1 1

a b ab
0 0 0
0 1 0
1 0 0
1 1 1

? Comment peut être interprétée l'opération logique dont la table est :
a b a b
0 0 0
0 1 1
1 0 1
1 1 0

Ces opérations sont mises en uvres par des circuits logiques de base appelés portes logiques.

! La plupart des circuits intégrés des ordinateurs actuels sont conçus à partir de portes NON-ET (NAND) et NON-OU (NOR).

? Montrer que les opérations ET, OU et NON sont réalisables à partir de portes NAND.
Expressions et fonctions booléennes
Expression booléenne = terme construit à partir de variables booléennes et d'opérateur booléens.
Fonction booléenne = fonction binaire à variables binaires (de dans ).
Une fonction booléenne peut être décrite par :
· sa table de vérité (recensant toutes les combinaisons de valeur des variables)
· une expression booléenne (décrivant la sortie 1 de la fonction, par convention, désigne la valeur 0 pour a)
Exemple : fonction booléenne majorité s'exprime par

a b c majorité
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

ou : majorité(a,b,c) = bc + a c + ab + abc

? Montrer qu'il y a 22n fonctions booléennes à n arguments ?

! Les portes NAND et NOR sont dites complètes car on peut réaliser n'importe quelle fonction boléenne avec l'une ou l'autre.
Simplificaton d'expressions booléennes
Deux fonctions booléennes sont équivalentes ssi les valeurs de leurs sorties sont les mêmes pour toutes les configurations identiques de leurs variables d'entrées.
Il est intéressant de minimiser le coût (en nombre de portes logiques) de réalisation d'une fonction en trouvant l'expression booléenne de cette fonction la moins couteuse.

? Montrer que la fonction majorité(a,b,c) se simplifie en bc + ac + ab

? Un afficheur 7 segments est composé de 7 diodes notés a, b, ..., g disposées ``en 8''. Des nombres sont fournis en binaire sur 4 bits, x1 x2 x3 x4. Donner l'expression des 7 fonctions a( x1 x2 x3 x4), b( x1 x2 x3 x4), etc... qui permettent d'afficher les nombres fournis.