Logique combinatoire et algèbre de Boole/Théorèmes

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Théorèmes de Boole

L'algèbre de Boole peut servir à analyser un circuit logique (composer de plusieurs portes) et à exprimer ce dernier sous forme mathématique . Nous allons voir qu'en étudiant les théorèmes de Boole, nous allons pouvoir simplifier les expressions logiques, et ainsi les circuits logiques.

1. a ⋅ 0 = 0
2. a ⋅ 1 = a
3. a ⋅ a = a
4. a ⋅ a = 0
5. a + 0 = a
6. a + 1 = 1
7. a + a = a
8. a + a = 1

Il va de soit que a n'est pas forcément une variable unique.

Ainsi si nous avons a ⋅ b ⋅ (a ⋅ b), si on pose a = a ⋅ b, alors a ⋅ b ⋅ (a ⋅ b) = 0.

9. a + b = b + a
10. a ⋅ b = b ⋅ a

Ces deux théorèmes montrent que ET et OU sont des lois commutatives ainsi l'ordre n'a pas d'importance.

11. a + (b + c) = (a + b) + c = a + b + c
12. a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c = a ⋅ b ⋅ c
13. 1. a ⋅ (b + c ) = a ⋅ b + a ⋅ c
    2. (a + b) ⋅ (c + d) = a ⋅ c + a ⋅ d + b ⋅ c + b ⋅ d

Le produit est une loi distributive comme en algèbre classique. Ceci démontre aussi que nous pouvons factoriser. Exemples :

• a ⋅ b ⋅ c + a ⋅ b ⋅ c = b ⋅ (a ⋅ c + a ⋅ c)
• a ⋅ b ⋅ c + a ⋅ b ⋅ d = a ⋅ b ⋅ (c + d)

2. a + a ⋅ b = a
3. a + a ⋅ b = a + b

Théorèmes de De Morgan

Somme et produit peuvent être complémentés, afin de devenir produit et somme des variables complémentées.

16. (a ⋅ b) = a + b
17. (a + b) = a ⋅ b

Exemple : (a ⋅ b̅ + c) = (a ⋅ b̅) ⋅ c = (a + b) ⋅ c

Simplification par tableau de Karnaugh

Tableau de Karnaugh

Un tableau de Karnaugh se présente sous la forme d'un carré ou d'un rectangle. Chaque case est repérée par ses coordonnées placées sur les bords du tableau selon un code appelé binaire réfléchi.

De plus, chaque case correspond à une ligne de la table de vérité, ainsi pour une fonction à n variables, on trouvera 2ⁿ cases pour le tableau de Karnaugh comme on trouvait 2ⁿ lignes dans la table de vérité.

Cette méthode n'est valable que jusqu'à quatre variables, ensuite elle implique des mécanismes qui rende la méthode de Karnaugh peu intéressante.

Exemples

Fonction à deux variables b 0 1 a 0 — — 1 — —

Fonction à trois variables bc 00 01 11 10 a 0 — — — — 1 — — — —

Construction d'un tableau de Karnaugh

Pour des raisons de commodités, on place en général les bits de poids fort à gauche du tableau de Karnaugh, ceux de poids faible sur le haut.

Exemples

On a S = f(a, b) b 0 1 a 0 f(a = 0, b = 0) f(a = 0, b = 1) 1 f(a = 1, b = 0) f(a = 1, b = 1) a b S 0 0 f(a = 0, b = 0) 0 1 f(a = 0, b = 1) 1 0 f(a = 1, b = 0) 1 1 f(a = 1, b = 1)

On a S = f(a, b, c) bc 00 01 11 10 a 0 f(a = 0, b = 0, c = 0) f(a = 0, b = 0, c = 1) f(a = 0, b = 1, c = 1) f(a = 0, b = 1, c = 0) 1 f(a = 1, b = 0, c = 0) f(a = 1, b = 0, c = 1) f(a = 1, b = 1, c = 1) f(a = 1, b = 1, c = 0)

On va donc faire correspondre à chaque lignes de la table de vérité une case du tableau de Karnaugh.

Simplification graphique par Karnaugh

Le tableau de Karnaugh est construit de tel façon que deux termes adjacents algébriquement le sont aussi géométriquement.

1. On regroupe toutes les cases adjacentes possédant des 1L pour former des groupements de 2ⁿ éléments, selon les groupements les plus grands possibles.
2. On lit les coordonnées de chaque groupe pour en déduire l'expression de la fonction logique. Sur la base de x + x ≠ 1, chaque coordonnées qui change dans le groupement est éliminé. Chaque groupement donne un ET, on « additionne » ensuite les ET par des OU.

Rémarques :

• Il ne faut pas oublier un seul 1L.
• On peut prendre plusieurs fois un 1L dans plusieurs groupements différents.

b 0 1 a 0 0 1 1 0 1 f(a, b) = b

b 0 1 a 0 0 1 1 1 0 f(a, b) = a ⋅ b + a ⋅ b

bc 00 01 11 10 a 0 1 1 0 0 1 1 0 1 0 f(a, b, c) = a ⋅ b ⋅ c + b ⋅ (a + c)