Introduction à l'algèbre de Boole
Indiscutablement, George Boole fut une personnalité hors du commun. Né en 1815 en Angleterre dans une famille pauvre, enfant prodige, il ouvrit sa première école à l’âge de dix-neuf ans. Ses découvertes furent fécondes (théorie des invariants…) mais il est surtout resté célèbre pour l’algèbre qui porte son nom et sur laquelle est basée l’informatique (voir les portes logiques). Ci-dessous, prtrait de Boole généré par Ideogram, logiciel d'IA.
Remarquant des similitudes entre les règles de la logique et celles de l’algèbre usuelle, il publia en 1847 une Analyse mathématique de la logique dans laquelle il proposa une algèbre ne comprenant que deux valeurs, 0 et 1. Celle-ci permettait de s’appliquer parfaitement à la logique (1 = vrai et 0 = faux).
C’est ainsi que l’on put mettre en parallèle le calcul propositionnel et l’algèbre de Boole, mais aussi l’algèbre des parties d’un ensemble. Les maths sont décidément extraordinaires.
Définition
L’algèbre de Boole est un ensemble \(E = \{0\, ;1\}\) muni de deux lois de composition interne \(+\) et \(\times\) ou . (un point).
| \(a\) | \(b\) | \(a + b\) |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| \(a\) | \(b\) | \(a . b\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Jusque là c’est simple. Il suffit de se faire à l’idée que \(1 + 1 = 1.\)
Propriétés
L’associativité : \((a + b) + c = a + (b + c)\) et \((a . b) . c = a . (b . c)\)
Exemple : \((1 + 1) + 0 = 1 + 0 = 1\) et \(1 + (1 + 0) = 1 + 1 = 1\)
La commutativité : \(a + b = b + a\) et \(a . b = b . a\)
Démonstration de l’addition :
| \(a\) | \(b\) | \(a + b\) | \(b + a\) |
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 |
Éléments neutres : \(a + 0 = a\) et \(p . 1 = p\)
Éléments absorbants : \(a + 1 = 1\) et \(a . 0 = 0\)
Double distributivité :
\(a + (b . c)\) \(=\) \((a + b) . (a + c)\)
\(a . (b + c)\) \(=\) \((a . b)(a . c)\)
Propriété d’absorption : \(a + (a . b) = a\) et \(a . (a + b) = a\)
Ainsi, \(p + (p . 1) = p + p = p\) et \(p . (p + 0) = p . p = p\) (propriété d’idempotence).
Complément et lois de De Morgan
Il existe plusieurs façons de noter le complément de \(a.\) Nous le noterons \(\overline{a}.\) Ainsi :
| \(a\) | \(\overline{a}\) |
| 1 | 0 |
| 0 | 1 |
Vous remarquerez sans mal que \(a + \overline{a} = 1\) et \(a . \overline{a} = 0.\)
Il s’ensuit les égalités suivantes (lois de De Morgan) :
\(\overline{a + b} = \overline{a} . \overline{b}\)
\(\overline{a . b} = \overline{a} + \overline{b}\)
Pour la petite histoire, Auguste De Morgan était l’ami de George Boole. Plus réputé que lui (du moins dans les années 1840), il usa de son influence pour l’aider à devenir professeur au Queen’s College de Cork.
Démontrons la première égalité.
| \(a\) | \(b\) | \(a + b\) | \(\overline{a+b}\) | \(\overline{a}\) | \(\overline{b}\) | \(\overline{a} . \overline{b}\) |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
La quatrième et la septième colonne sont identiques. L’égalité est démontrée.
Matrices
En algèbre classique, on dit d’une matrice constituée de 0 et de 1 qu’elle est booléenne. Mais ce sont bien les règles de cette algèbre qui s’appliquent (celle où \(1 + 1 = 2\)).
Ici, les opérations sur matrices, somme et produit, appliquent bien sûr l’algèbre de Boole. À titre d’exemple :
\(\left( {\begin{array}{*{20}{c}} 0&1\\ 0&1 \end{array}} \right) + \left( {\begin{array}{*{20}{c}} 0&1\\ 1&1 \end{array}} \right)\) \(=\) \(\left( {\begin{array}{*{20}{c}} 0&1\\ 1&1 \end{array}} \right)\)
Autour de l’algèbre de Boole
Les propriétés de l’algèbre de Boole sont analogues à celles des parties d’un ensemble et à celles du calcul propositionnel mais c’est bien l’algèbre de Boole qui est la plus pratique à utiliser.
Exemple
Montrons que \(a + b + (\overline{b} . c)\) \(=\) \(a + b + c\)
| \(a\) | \(b\) | \(c\) | \(\overline{b}\) | \(\overline{b} . c\) | \(a + b + \overline{b} . c\) | \(a + b + c\) |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
Les deux dernières colonnes sont bien identiques.
