Simplifier une expression booléenne par le calcul

Simplifier une expression booléenne, c'est trouver une expression équivalente (qui a la même table de vérité) avec moins de termes et moins de variables, en appliquant les règles de l'algèbre de Boole. Une expression simplifiée donne une condition plus lisible dans un programme, une requête plus courte, ou un circuit avec moins de portes. Ce chapitre donne une méthode, dix exemples détaillés pas à pas et les pièges à éviter. L'autre méthode, graphique, est le tableau de Karnaugh.

La méthode

Il n'existe pas d'algorithme unique : simplifier demande de l'œil, qui vient avec l'entraînement. Cet ordre marche dans la grande majorité des exercices :

1. Se ramener à une somme de produits. Développe les produits de sommes (distributivité), et fais disparaître les barres au-dessus des parenthèses avec De Morgan.
2. Chercher les paires qui ne diffèrent que par une variable. xy + xy̅ = x(y + y̅) = x : la variable qui change disparaît. C'est la règle qui fait le plus gros du travail.
3. Appliquer les absorptions. x + xy = x (un terme qui en contient un autre disparaît) et x + x̅y = x + y (le complément disparaît).
4. Supprimer les termes en double (x + x = x) et les termes nuls (xx̅ = 0).
5. Vérifier, par une table de vérité, par quelques valeurs ou avec un petit programme.

Sur une copie, cite la règle à chaque étape (« par distributivité », « par absorption », « par De Morgan »). Le correcteur évalue le raisonnement autant que le résultat.

Dix exemples pas à pas

Exemple 1. F = ab + ab̅

• F = a(b + b̅), en mettant a en facteur ;
• F = a · 1, par complémentarité ;
• F = a, car 1 est neutre pour le produit.

Les deux termes ne diffèrent que par b, qui disparaît.

Exemple 2. F = ab + abc

• F = ab(1 + c), en mettant ab en facteur ;
• F = ab · 1, car 1 + c = 1 ;
• F = ab.

C'est l'absorption x + xy = x avec x = ab : le terme abc, plus exigeant que ab, n'ajoute aucun cas.

Exemple 3. F = a̅b̅ + a̅b + ab̅

• F = a̅(b̅ + b) + ab̅, en mettant a̅ en facteur dans les deux premiers termes ;
• F = a̅ + ab̅, par complémentarité ;
• F = a̅ + b̅, par absorption du complément (x + x̅y = x + y, avec x = a̅).

Par De Morgan, F = non(ab) : F vaut 1 dans tous les cas sauf a = b = 1. C'est la porte NAND.

Exemple 4. F = abc + abc̅ + ab̅c + ab̅c̅

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

Les quatre termes couvrent toutes les combinaisons de b et c avec a = 1 : seule a compte.

Exemple 5. F = (a + b)(a + b̅)

Première méthode, par distributivité de la somme : F = a + bb̅ = a + 0 = a.

Seconde méthode, en développant : F = aa + ab̅ + ba + bb̅ = a + ab̅ + ab + 0 = a(1 + b̅ + b) = a. Plus long, même résultat.

Exemple 6. F = a̅bc + abc + ab̅c

• On duplique abc (idempotence) : F = (a̅bc + abc) + (abc + ab̅c) ;
• F = bc(a̅ + a) + ac(b + b̅) ;
• F = bc + ac, que l'on peut factoriser en c(a + b).

Exemple 7. F = non(a̅ + b) + ab

• non(a̅ + b) = a b̅, par De Morgan (le complément de a̅ est a) ;
• F = ab̅ + ab = a(b̅ + b) ;
• F = a.

Exemple 8. F = (a + b)(a̅ + c)

• On développe : F = aa̅ + ac + a̅b + bc = ac + a̅b + bc, car aa̅ = 0 ;
• Le terme bc est inutile : bc = bc(a + a̅) = abc + a̅bc. Or abc est absorbé par ac et a̅bc par a̅b ;
• F = ac + a̅b.

Cette dernière étape est le théorème du consensus : xy + x̅z + yz = xy + x̅z. Le terme yz, appelé consensus, est redondant. Il n'est pas exigé au BTS, mais il explique les termes qui « disparaissent » dans un tableau de Karnaugh.

Exemple 9. F = a + a̅b + a̅b̅c

• a + a̅b = a + b, par absorption du complément ;
• F = (a + b) + a̅b̅c. Or a̅b̅ = non(a + b) par De Morgan : en posant x = a + b, F = x + x̅c = x + c ;
• F = a + b + c.

Exemple 10. F = non(ab + a̅b̅)

• Par De Morgan : F = non(ab) · non(a̅b̅) = (a̅ + b̅)(a + b) ;
• En développant : F = a̅a + a̅b + b̅a + b̅b = a̅b + ab̅, car a̅a = 0 et b̅b = 0 ;
• F = a̅b + ab̅, qui vaut 1 quand a et b sont différents : c'est le ou exclusif a ⊕ b.

ab + a̅b̅ vaut 1 quand a et b sont égaux : c'est l'équivalence, et son complément est bien le ou exclusif.

Vérifier un résultat

Une simplification fausse coûte tous les points de la question. Trois façons de vérifier :

• Par une table de vérité de l'expression de départ et du résultat : les colonnes doivent être identiques. Huit lignes pour trois variables, c'est rapide.
• Par quelques valeurs choisies, en priorité celles qui annulent ou valent 1 dans le résultat. Une seule différence prouve une erreur ; l'absence de différence sur quelques cas ne prouve rien, mais rassure.
• Avec Python, qui teste toutes les combinaisons en une boucle :

from itertools import product

def depart(a, b, c):
    return (a and b and c) or (a and b and not c) or (a and not b and c)

def simplifiee(a, b, c):
    return (a and b) or (a and c)

ok = all(depart(a, b, c) == simplifiee(a, b, c)
         for a, b, c in product([False, True], repeat=3))
print(ok)   # True : les deux expressions sont équivalentes

product([False, True], repeat=3) génère les 8 combinaisons de trois booléens, comme les 8 lignes d'une table de vérité. Ce test est aussi un bon exercice d'algorithmique pour l'épreuve pratique de l'E3.

Les pièges classiques

Exercices

from itertools import product

ok = all(((a or b) and (a or c) and (b or c)) == ((a and b) or (a and c) or (b and c))
         for a, b, c in product([False, True], repeat=3))
print(ok)   # True