DevSimplifier une expression booléenne consiste à trouver une formule équivalente plus courte, en utilisant les lois de l'algèbre de Boole. Les méthodes principales : manipulation algébrique, tables de vérité, tableaux de Karnaugh.
Lois fondamentales
- Commutativité : $a + b = b + a$, $a \cdot b = b \cdot a$
- Associativité : $(a+b)+c = a+(b+c)$
- Distributivité : $a(b+c) = ab + ac$
- De Morgan : $\overline{a+b} = \bar{a} \cdot \bar{b}$ et $\overline{a \cdot b} = \bar{a} + \bar{b}$
- Absorption : $a + ab = a$
- Idempotence : $a + a = a$, $a \cdot a = a$
- Complément : $a + \bar{a} = 1$, $a \cdot \bar{a} = 0$
Exercice : simplifier (a + b)(a + c)
Développons : $(a + b)(a + c) = a \cdot a + a \cdot c + b \cdot a + b \cdot c = a + ac + ab + bc$ (idempotence $a \cdot a = a$).
Factorisons $a$ dans les trois premiers termes : $a(1 + c + b) + bc = a \cdot 1 + bc = a + bc$.
Résultat : $(a + b)(a + c) = a + bc$. C'est l'identité d'absorption-distribution.
Exercice : simplifier a·b + a·b̄ + ā·b̄
Factorisons $a$ dans les deux premiers termes : $a(b + \bar{b}) + \bar{a}\bar{b} = a + \bar{a}\bar{b}$ (complément $b + \bar{b} = 1$).
Appliquons la règle d'absorption dual : $a + \bar{a}\bar{b} = a + \bar{b}$.
Résultat : $ab + a\bar{b} + \bar{a}\bar{b} = a + \bar{b}$.
Méthode des tableaux de Karnaugh
Pour des formules à 3-4 variables, les tableaux de Karnaugh sont visuels et efficaces. On dispose les minterms dans une grille, en variant les variables par code de Gray (une seule variable change entre deux cases adjacentes).
Pour 3 variables $a, b, c$ : grille 2×4 avec $a$ en ligne (0, 1) et $bc$ en colonnes (00, 01, 11, 10). On place un 1 dans chaque case correspondant à un minterm de la fonction.
On cherche ensuite à regrouper les 1 adjacents en rectangles de taille $2^k$. Chaque regroupement de taille $2^k$ correspond à un terme produit simplifié de $(n-k)$ littéraux. L'objectif est de couvrir tous les 1 avec un minimum de regroupements, aussi grands que possible.
Exercice : minimiser f(a,b,c) avec table de vérité donnée
Supposons $f(a,b,c) = 1$ pour les entrées (0,0,1), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), et 0 ailleurs.
FND brute : $\bar{a}\bar{b}c + \bar{a}bc + a\bar{b}\bar{c} + a\bar{b}c + ab\bar{c} + abc$. 6 termes à 3 littéraux chacun = 18 littéraux.
En Karnaugh, on regroupe. Groupes maximaux : $\{\bar{a}c, a\}$ → formule simplifiée $\bar{a}c + a = a + c$ (si $a$ seul couvre tous les cas avec $a=1$).
Vérification : $f = a + c$ donne bien 1 sur les 6 cas cibles et 0 sur (0,0,0) et (0,1,0). ∎
Une question ou une suggestion ? Écrivez-nous.