Algèbre de Boole

L'**algèbre de Boole** est un ensemble de **lois** qui permettent de réécrire des expressions booléennes. Chaque loi dit que deux expressions sont **équivalentes** : elles ont la même valeur de vérité pour toutes les entrées, donc tu peux toujours remplacer l'une par l'autre. Grâce aux lois, tu peux **simplifier** une expression sans construire à chaque fois une nouvelle table de vérité. On écrit 1 pour vrai et 0 pour faux (les tables de vérité interactives utilisent aussi 1 et 0). Les ingénieurs écrivent souvent $A \cdot B$ pour $A \land B$, $A + B$ pour $A \lor B$ et $\overline{A}$ pour $\neg A$ : cela signifie exactement la même chose. Dans cette leçon, on utilise $\land$, $\lor$ et $\neg$. **Les lois** ($A$, $B$ et $C$ sont des variables booléennes) : | Loi | Forme ET | Forme OU | |:---|:---:|:---:| | Élément neutre | $A \land 1 = A$ | $A \lor 0 = A$ | | Élément absorbant (domination) | $A \land 0 = 0$ | $A \lor 1 = 1$ | | Idempotence | $A \land A = A$ | $A \lor A = A$ | | Complément | $A \land \neg A = 0$ | $A \lor \neg A = 1$ | | Double négation | $\neg\neg A = A$ | (une seule forme) | | Commutativité | $A \land B = B \land A$ | $A \lor B = B \lor A$ | | Associativité | $(A \land B) \land C = A \land (B \land C)$ | $(A \lor B) \lor C = A \lor (B \lor C)$ | | Distributivité | $A \land (B \lor C) = (A \land B) \lor (A \land C)$ | $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ | | Loi d'absorption | $A \land (A \lor B) = A$ | $A \lor (A \land B) = A$ | | De Morgan | $\neg(A \land B) = \neg A \lor \neg B$ | $\neg(A \lor B) = \neg A \land \neg B$ | Remarque la régularité : échange $\land$ et $\lor$, ainsi que 0 et 1, dans une colonne et tu obtiens l'autre colonne. C'est ce qu'on appelle la **dualité**. **Simplifier étape par étape :** utilise une seule loi par étape et nomme-la. Vérifie ensuite le résultat avec une table de vérité : si les colonnes finales coïncident sur chaque ligne, la simplification est correcte.

Élément neutre et élément absorbant

Simplifie $(A \land 1) \lor (B \land 0)$.

Applique la loi de l'élément neutre à la première parenthèse: $A \land 1 = A$, car ET avec vrai ne change rien = $A \lor (B \land 0)$

Applique la loi de l'élément absorbant à la seconde parenthèse: $B \land 0 = 0$, car ET avec faux est toujours faux = $A \lor 0$

Applique encore la loi de l'élément neutre: $A \lor 0 = A$, car OU avec faux ne change rien = $A$

Answer: $(A \land 1) \lor (B \land 0) = A$. La valeur de $B$ n'a aucune importance.

Démontrer la loi d'absorption

Montre à l'aide d'autres lois que $A \lor (A \land B) = A$.

Écris $A$ sous la forme $A \land 1$ (élément neutre): $A \lor (A \land B) = (A \land 1) \lor (A \land B)$ = Les deux parenthèses commencent par $A$

Factorise $A$ (distributivité, lue de droite à gauche): $(A \land 1) \lor (A \land B) = A \land (1 \lor B)$ = $A \land (1 \lor B)$

Applique la commutativité et l'élément absorbant: $1 \lor B = B \lor 1 = 1$ = $A \land 1$

Applique la loi de l'élément neutre: $A \land 1 = A$ = $A$

Answer: $A \lor (A \land B) = A$. En mots : si $A$ est vrai, tout le OU est vrai, et si $A$ est faux, alors $A \land B$ est faux aussi. Dans les deux cas, le résultat est égal à $A$.

De Morgan et double négation

Simplifie $\neg(\neg A \land B)$ et vérifie le résultat avec une table de vérité.

Applique la loi de De Morgan: Le NON d'un ET devient un OU des négations : $\neg(\neg A \land B) = \neg\neg A \lor \neg B$ = $\neg\neg A \lor \neg B$

Applique la double négation: $\neg\neg A = A$ = $A \lor \neg B$

Construis la colonne de l'expression de départ: Lignes $(A, B)$ = 00, 01, 10, 11 : $\neg A \land B$ vaut 0, 1, 0, 0, donc $\neg(\neg A \land B)$ vaut 1, 0, 1, 1 = 1, 0, 1, 1

Construis la colonne du résultat: $\neg B$ vaut 1, 0, 1, 0, donc $A \lor \neg B$ vaut 1, 0, 1, 1 = Même colonne sur chaque ligne

Answer: $\neg(\neg A \land B) = A \lor \neg B$. Les deux colonnes coïncident sur les 4 lignes, donc la simplification est correcte.

Factoriser avec la loi du complément

Simplifie $(A \land B) \lor (A \land \neg B)$ et vérifie avec une table de vérité.

Factorise $A$ (distributivité): $(A \land B) \lor (A \land \neg B) = A \land (B \lor \neg B)$ = $A \land (B \lor \neg B)$

Applique la loi du complément: $B \lor \neg B = 1$, car $B$ est soit vrai, soit faux = $A \land 1$

Applique la loi de l'élément neutre: $A \land 1 = A$ = $A$

Vérifie avec une table de vérité: Lignes $(A, B)$ = 00, 01, 10, 11 : $A \land B$ vaut 0, 0, 0, 1 et $A \land \neg B$ vaut 0, 0, 1, 0, donc le OU vaut 0, 0, 1, 1 = Comme la colonne $A$ : 0, 0, 1, 1

Answer: $(A \land B) \lor (A \land \neg B) = A$. Un circuit de 4 portes (deux ET, un NON, un OU) devient un simple fil.

Moins de portes dans un circuit

Un circuit calcule $\neg(A \lor B) \lor (\neg A \land B)$. Simplifie-le et compte les portes économisées (une porte pour chaque $\land$, $\lor$ et $\neg$).

Compte les portes de l'expression de départ: Opérateurs : $\neg$ et $\lor$ dans la première partie, $\neg$ et $\land$ dans la seconde, et le $\lor$ du milieu = 5 portes

Applique la loi de De Morgan à la première partie: $\neg(A \lor B) = \neg A \land \neg B$ = $(\neg A \land \neg B) \lor (\neg A \land B)$

Factorise $\neg A$ (distributivité): $(\neg A \land \neg B) \lor (\neg A \land B) = \neg A \land (\neg B \lor B)$ = $\neg A \land (\neg B \lor B)$

Applique le complément et l'élément neutre: $\neg B \lor B = 1$ et $\neg A \land 1 = \neg A$ = $\neg A$

Compte de nouveau les portes: $\neg A$ ne demande qu'une porte NON : $5 - 1 = 4$ = 4 portes économisées

Answer: Le circuit est équivalent à $\neg A$ : une porte NON au lieu de 5 portes. Vérification : l'expression de départ est vraie exactement sur les lignes 00 et 01, c'est-à-dire là où $A = 0$.

Chaque $\land$, $\lor$ et $\neg$ d'une expression devient une **porte logique** dans un circuit. Une expression plus courte, c'est moins de portes, et moins de portes, c'est une puce moins chère, plus petite, plus rapide et qui consomme moins d'énergie. - **Électronique** : un processeur contient des milliards de portes, donc économiser une porte dans un circuit copié un million de fois économise un million de portes - **Programmation** : une condition comme NON (week-end OU jour férié) peut s'écrire (NON week-end) ET (NON jour férié), ce qui est souvent plus facile à lire et à tester - **Recherche et bases de données** : un filtre comme maths OU (maths ET logique) donne exactement les mêmes résultats que maths tout seul - **Démonstrations** : les lois permettent de prouver que deux circuits ou deux conditions font la même chose sans essayer toutes les entrées Dans la leçon Tables de vérité, tu as vérifié des équivalences ligne par ligne, et dans la leçon Portes logiques, tu as construit des circuits. L'algèbre de Boole relie les deux : elle transforme un grand circuit en un petit, et une table de vérité confirme que rien n'a changé.

Mistake: Écrire $\neg(A \land B) = \neg A \land \neg B$

Why: La loi de De Morgan change l'opérateur en plus des variables. Teste $A = 1$, $B = 0$ : le membre de gauche vaut $\neg 0 = 1$, celui de droite $0 \land 1 = 0$.

Correct: Casse la barre et change le signe : $\neg(A \land B) = \neg A \lor \neg B$ et $\neg(A \lor B) = \neg A \land \neg B$.

Mistake: Utiliser les règles de l'algèbre ordinaire, comme $A \lor A = 2A$ ou $A \land A = A^2$

Why: Les variables booléennes valent seulement 0 ou 1, et $1 \lor 1$ vaut 1, pas 2. Répéter une variable n'apporte rien de nouveau.

Correct: Utilise l'idempotence : $A \lor A = A$ et $A \land A = A$.

Mistake: Lire $A \lor B \land C$ comme $(A \lor B) \land C$

Why: ET est évalué avant OU, comme la multiplication avant l'addition. Avec $A = 1$, $B = 0$, $C = 0$, la bonne valeur est $1 \lor 0 = 1$, mais la mauvaise lecture donne $1 \land 0 = 0$.

Correct: Ajoute les parenthèses avant d'appliquer une loi : $A \lor B \land C = A \lor (B \land C)$.

Mistake: Appliquer la loi du complément à deux variables différentes, comme $A \land \neg B = 0$

Why: La loi du complément ne fonctionne qu'avec une variable et sa propre négation. Avec $A = 1$, $B = 0$ : $A \land \neg B = 1 \land 1 = 1$, pas 0.

Correct: Cherche la même lettre : $A \land \neg A = 0$ et $B \lor \neg B = 1$, mais $A \land \neg B$ ne se simplifie pas.

Concevoir des puces moins chères

Les concepteurs de puces simplifient chaque circuit avec l'algèbre de Boole avant de le fabriquer, car chaque porte coûte de la place, de l'énergie et de l'argent.

Un circuit pour $(A \land B) \lor (A \land C)$ utilise 3 portes. Factorisé en $A \land (B \lor C)$, il n'en faut plus que 2.

Des conditions lisibles dans un programme

Les programmeurs utilisent les lois de De Morgan pour supprimer les doubles négations confuses dans les conditions de leur code.

NON (week-end OU jour férié) revient à (NON week-end) ET (NON jour férié) : le magasin est ouvert les jours qui ne sont ni l'un ni l'autre.

Filtres de recherche

Les moteurs de recherche et les bases de données simplifient les filtres avec la loi d'absorption avant de les exécuter.

Le filtre maths OU (maths ET logique) renvoie exactement les mêmes livres que le filtre maths.

L'algèbre de Boole utilise des lois pour réécrire une expression en une expression équivalente, sans nouvelle table de vérité à chaque fois

Les lois de l'élément neutre, de l'élément absorbant, d'idempotence et du complément éliminent les constantes et les variables répétées : $A \land 1 = A$, $A \lor 1 = 1$, $A \lor A = A$, $A \land \neg A = 0$

La commutativité, l'associativité et la distributivité permettent de réordonner, de regrouper et de factoriser ; en algèbre de Boole, OU est aussi distributif sur ET

Lois d'absorption : $A \lor (A \land B) = A$ et $A \land (A \lor B) = A$

Lois de De Morgan : casse la barre et change le signe, $\neg(A \land B) = \neg A \lor \neg B$ et $\neg(A \lor B) = \neg A \land \neg B$

Simplifie avec une loi par étape, nomme chaque loi et vérifie le résultat avec une table de vérité ; une expression plus simple signifie moins de portes

Q: Pourquoi OU est-il distributif sur ET, alors que $a + b \times c$ n'est pas égal à $(a + b) \times (a + c)$ pour les nombres ?

A: Parce que les variables booléennes valent seulement 0 ou 1. Vérifie les deux cas : si $A = 1$, les deux membres de $A \lor (B \land C) = (A \lor B) \land (A \lor C)$ valent 1 ; si $A = 0$, les deux membres deviennent $B \land C$. Avec des nombres ordinaires, $1 + 2 \times 3 = 7$ mais $(1 + 2) \times (1 + 3) = 12$, donc cette loi n'est vraie qu'en algèbre de Boole.

Q: Comment savoir quelle loi utiliser ensuite ?

A: Repère des motifs : un NON devant une parenthèse appelle De Morgan, une variable répétée dans deux parenthèses appelle une factorisation (distributivité), et une variable à côté de sa propre négation appelle la loi du complément. Les constantes 0 et 1 disparaissent avec les lois de l'élément neutre et de l'élément absorbant.

Q: Ai-je encore besoin des tables de vérité si je connais les lois ?

A: Les lois trouvent la simplification, la table de vérité la confirme. Une table à 2 variables n'a que 4 lignes, c'est donc une vérification rapide et fiable, surtout quand tu doutes d'une étape.

Q: Puis-je vérifier une loi avec l'arithmétique ordinaire ?

A: Oui, avec 0 et 1 : $A \land B = A \times B$, $\neg A = 1 - A$ et $A \lor B = A + B - A \times B$. Par exemple, avec $A = 1$ et $B = 1$ : $1 + 1 - 1 \times 1 = 1$, donc $1 \lor 1 = 1$. La calculatrice de cette leçon fonctionne avec ces nombres.

Quitter la présentation

Algèbre de Boole

1 / 14

Logique & Ensembles / Logique booléenne

Algèbre de Boole

Apprends les lois de l'algèbre de Boole, dont les lois de De Morgan, utilise-les pour simplifier des expressions étape par étape et vérifie le résultat avec une table de vérité.

Avancé30 min

Utilisez les touches fléchées ou la barre d'espace pour naviguer