Algèbre de Boole : définition, règles et propriétés

L'algèbre de Boole est le calcul sur des variables qui ne prennent que deux valeurs, 0 et 1, avec trois opérations : le complément (a̅, « non a »), le produit (ab, « a et b ») et la somme (a + b, « a ou b »). Elle rassemble en un seul calcul la logique des propositions et les opérations sur les ensembles, et elle sert à simplifier des conditions et à concevoir les circuits des ordinateurs. Ce chapitre la définit et donne toutes ses règles de calcul.

Deux exemples qui se ressemblent trait pour trait

Les chapitres précédents ont construit deux calculs :

• sur les propositions, avec ¬, ∧ et ∨, et les valeurs F et V ;
• sur les parties d'un ensemble E, avec le complémentaire, ∩ et ∪, et les parties particulières ∅ et E.

Leurs lois sont les mêmes, ligne pour ligne : commutativité, associativité, distributivité dans les deux sens, éléments neutres, complémentarité, De Morgan. Quand deux calculs obéissent aux mêmes règles, on gagne à les étudier une seule fois sous une forme abstraite. C'est ce qu'a fait le mathématicien anglais George Boole au milieu du XIXe siècle, et c'est cette structure qu'on appelle une algèbre de Boole.

Définition et notations

Une algèbre de Boole est un ensemble B muni :

• de deux éléments distingués, notés 0 et 1 ;
• d'une opération unaire, le complément : à chaque a de B, elle associe a̅ (« a barre » ou « non a ») ;
• de deux opérations binaires, la somme a + b (« a ou b ») et le produit a · b, noté aussi ab (« a et b ») ;

qui vérifient les propriétés du tableau de la section suivante (commutativité, associativité, distributivité, neutres, complémentarité).

L'exemple le plus important, celui de tous les exercices du BTS, est B = {0, 1} avec les tables suivantes, qui sont celles de non, et, ou avec 0 pour faux et 1 pour vrai :

Le produit booléen se calcule comme un produit ordinaire de 0 et de 1. La somme booléenne, elle, diffère de l'addition sur une seule ligne : 1 + 1 = 1. Il n'y a pas de 2 en algèbre de Boole : « vrai ou vrai » est vrai.

Une variable booléenne est une variable qui prend la valeur 0 ou 1. Une expression booléenne combine des variables booléennes avec les trois opérations, comme ab̅ + a̅c.

Priorités. Comme en arithmétique, le produit passe avant la somme : a + bc se lit a + (bc). Le complément s'applique à ce qu'il couvre. On peut omettre le point du produit : ab = a · b.

Les règles de calcul

Voici toutes les règles, dans la notation du BTS. Chacune se démontre en vérifiant les quatre (ou huit) lignes de sa table de vérité : on appelle cela une démonstration par induction parfaite.

Et l'involution (double complément) : le complément de a̅ est a.

D'où viennent les règles les moins intuitives

a + 1 = 1. « a ou vrai » est toujours vrai. Côté ensembles : A ∪ E = E.

a + ab = a (absorption). Si a = 1, les deux membres valent 1. Si a = 0, le membre de gauche vaut 0 + 0 · b = 0. Par le calcul : a + ab = a · 1 + ab = a(1 + b) = a · 1 = a. En français : « être cadre, ou être cadre et en télétravail » revient à « être cadre ».

a + a̅b = a + b. Par la distributivité de la somme : a + a̅b = (a + a̅)(a + b) = 1 · (a + b) = a + b. En français : dans « a ou (non a et b) », la précision « non a » est inutile, car si a est vrai, la condition est déjà remplie.

a + bc = (a + b)(a + c). Cette distributivité n'a pas d'équivalent pour les nombres (2 + 3 × 4 = 14, alors que (2 + 3)(2 + 4) = 30). Elle se vérifie par une table :

Les colonnes de a + bc et de (a + b)(a + c) sont identiques.

Les lois de De Morgan en algèbre de Boole

Pour complémenter une expression plus longue, on applique De Morgan de l'extérieur vers l'intérieur, en gardant les parenthèses :

• non(ab + c) = non(ab) · c̅ = (a̅ + b̅) c̅ = a̅c̅ + b̅c̅ ;
• non(a(b̅ + c)) = a̅ + non(b̅ + c) = a̅ + b c̅.

Dualité

Chaque règle du tableau a deux formes, « produit » et « somme ». On passe de l'une à l'autre en échangeant + et ·, et 0 et 1 : c'est le principe de dualité. Par exemple, la duale de a + 0 = a est a · 1 = a, et la duale de a + a̅b = a + b est a(a̅ + b) = ab. Toute égalité vraie en algèbre de Boole a une duale vraie. Retenir une colonne du tableau suffit donc pour retrouver l'autre.

Ce qu'on ne peut pas faire

L'algèbre de Boole ressemble à l'algèbre des nombres, mais certaines habitudes sont fausses :

• pas de soustraction ni de division : de a + b = a + c, on ne peut pas déduire b = c (contre-exemple : a = 1, b = 0, c = 1) ; de ab = ac non plus (a = 0) ;
• pas de coefficients ni d'exposants : a + a = a, et non 2a ; aa = a, et non a² ;
• 1 + 1 = 1, pas 2, et pas 0 (0 serait le résultat du ou exclusif, voir XOR).

Exercices

Exercice 1 sur 5 Calculs avec 0 et 1 Réussi À revoir

Calcule, en algèbre de Boole :

1. 1 + 1 + 0
2. 1 · 0 + 1
3. non(1 + 0) · 1
4. 0̅ + 0 · 1
5. a + 1 + b, pour tous a et b
6. a · 0 + b · 1

Voir la réponseMasquer la réponse de l'exercice 1

1. 1 + 1 + 0 = 1 + 0 = 1
2. 1 · 0 + 1 = 0 + 1 = 1 (le produit d'abord)
3. non(1 + 0) · 1 = non(1) · 1 = 0 · 1 = 0
4. 0̅ + 0 · 1 = 1 + 0 = 1
5. a + 1 + b = 1 + b = 1 (1 est absorbant pour la somme)
6. a · 0 + b · 1 = 0 + b = b

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 Démontrer une règle par une table Réussi À revoir

Démontre par une table de vérité la règle d'absorption du complément : a + a̅b = a + b.

Voir la réponseMasquer la réponse de l'exercice 2

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

Les deux dernières colonnes sont identiques, donc a + a̅b = a + b pour toutes les valeurs de a et b.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 Complémenter avec De Morgan Réussi À revoir

Écris le complément de chaque expression sous forme d'une somme de produits (sans barre au-dessus d'une parenthèse).

1. E₁ = a + b̅
2. E₂ = ab̅c
3. E₃ = ab + c̅
4. E₄ = (a + b)(a̅ + c)

Voir la réponseMasquer la réponse de l'exercice 3

1. non(a + b̅) = a̅ · b (le complément de b̅ est b).
2. non(ab̅c) = a̅ + b + c̅.
3. non(ab + c̅) = non(ab) · c = (a̅ + b̅)c = a̅c + b̅c.
4. non((a + b)(a̅ + c)) = non(a + b) + non(a̅ + c) = a̅b̅ + ac̅.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 Vrai ou faux ? Réussi À revoir

Pour chaque égalité, dis si elle est vraie pour toutes les valeurs des variables. Si elle est fausse, donne un contre-exemple.

1. a + ab̅ = a
2. non(ab) = a̅ b̅
3. (a + b)(a + b̅) = a
4. a + b = a + c ⇒ b = c
5. a̅ + ab = a̅ + b

Voir la réponseMasquer la réponse de l'exercice 4

1. Vraie : c'est l'absorption a + a(b̅) = a.
2. Fausse : contre-exemple a = 1, b = 0. non(1 · 0) = non(0) = 1, mais a̅ b̅ = 0 · 1 = 0. La bonne loi est non(ab) = a̅ + b̅.
3. Vraie : par distributivité de la somme, (a + b)(a + b̅) = a + bb̅ = a + 0 = a.
4. Fausse : contre-exemple a = 1, b = 0, c = 1. a + b = 1 et a + c = 1, mais b ≠ c.
5. Vraie : c'est l'absorption du complément appliquée à a̅ : a̅ + (le complément de a̅)b = a̅ + b.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Un ensemble qui est une algèbre de Boole Réussi À revoir

Soit E = {x, y}. On considère P(E) muni de la réunion, de l'intersection et du complémentaire dans E.

1. Écris les éléments de P(E). Quels éléments jouent le rôle de 0 et de 1 ?
2. Calcule {x} ∪ {y}, {x} ∩ {y} et le complémentaire de {x}. À quelles égalités booléennes correspondent-ils si l'on code {x} par a et {y} par a̅ ?

Voir la réponseMasquer la réponse de l'exercice 5

1. P(E) = {∅, {x}, {y}, {x, y}}. L'ensemble vide joue le rôle de 0 (neutre de la réunion), E = {x, y} celui de 1 (neutre de l'intersection).
2. {x} ∪ {y} = {x, y} = E, {x} ∩ {y} = ∅, et le complémentaire de {x} est {y}. Avec a = {x} et a̅ = {y}, ce sont les règles de complémentarité : a + a̅ = 1 et a a̅ = 0. P(E) est une algèbre de Boole à 4 éléments.

Tu avais trouvé ?

Oui, j'avais bonPas encore