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

Leçons de niveau 12
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Logique combinatoire et algèbre de Boole : Théorèmes
Logique combinatoire et algèbre de Boole/Théorèmes
 », n'a pu être restituée correctement ci-dessus.

Théorèmes de Boole[modifier | modifier le wikicode]

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. aa = 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 ab ⋅ (ab), si on pose a = ab, alors ab ⋅ (ab) = 0.

  1. a + b = b + a
  2. ab = ba

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

  1. a + (b + c) = (a + b) + c = a + b + c
  2. a ⋅ (bc) = (ab) ⋅ c = abc
    1. a ⋅ (b + c ) = ab + ac
    2. (a + b) ⋅ (c + d) = ac + ad + bc + bd

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

  • abc + abc = b ⋅ (ac + ac)
  • abc + abd = ab ⋅ (c + d)
  1. a + ab = a
  2. a + ab = a + b

Théorèmes de De Morgan[modifier | modifier le wikicode]

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

  1. (ab) = a + b
  2. (a + b) = ab

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

Simplification par tableau de Karnaugh[modifier | modifier le wikicode]

Tableau de Karnaugh[modifier | modifier le wikicode]

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 2n cases pour le tableau de Karnaugh comme on trouvait 2n 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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 2n é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) = ab + ab
bc
00 01 11 10
a 0 1 1 0 0
1 1 0 1 0
f(a, b, c) = abc + b ⋅ (a + c)