CNF (ET de OU) et DNF (OU de ET)
← Retour au cours Logique booléenne Essayer le simulateur
Toute expression booléenne peut s'écrire sous une forme normalisée, utile pour comparer ou fabriquer des circuits.
Une ligne où le résultat vaut 1 donne une clause ET ; on relie les clauses par OU.
Exactement l'inverse de la DNF : on part des lignes où f = 0.
Quand la table de vérité de ton circuit est complète, le simulateur en lit la forme disjonctive (DNF) et la forme conjonctive (CNF) : compare avec ton calcul à la main.
Deux expressions booléennes peuvent s'écrire de façons très différentes tout en étant équivalentes. Les formes normales donnent une écriture canonique, systématique, directement lisible sur une table de vérité.
| a | b | f = a XOR b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Deux lignes où f = 1 : (a=0, b=1) et (a=1, b=0). Chaque ligne devient une clause ET, reliées par OU :
DNF de a XOR b : f = (non a · b) + (a · non b) ligne (0,1) ─┘ └─ ligne (1,0)
La CNF utilise la méthode duale : on part des lignes où f = 0, pas où f = 1. Sur la table du XOR, deux lignes valent 0 : (a=0, b=0) et (a=1, b=1).
Pour chaque ligne à 0, on construit une clause OU qui doit être fausse exactement sur cette ligne — donc chaque littéral est nié quand la variable vaut 1 (convention inverse de la DNF, où on niait quand elle valait 0) :
CNF de a XOR b : ligne (0,0) : a=0, b=0 → clause (a + b) ligne (1,1) : a=1, b=1 → clause (non a + non b) f = (a + b) · (non a + non b)
Vérification rapide : sur (a=0, b=0), (a+b) vaut 0, donc le produit entier vaut 0 — bien la bonne valeur de f. Sur (a=1, b=1), c'est (non a+non b) qui vaut 0. Sur les deux autres lignes, les deux clauses valent 1, donc f = 1. La DNF et la CNF de a XOR b sont deux écritures différentes de la même fonction — le choix dépend de l'usage (voir ci-dessous).
La DNF est la façon la plus directe de construire un circuit à partir d'une table de vérité : chaque clause ET devient une porte AND, le OU final une porte OR (voir la fiche Portes logiques). La CNF est la forme utilisée par les solveurs SAT (satisfiabilité), qui décident si une expression peut valoir vrai.
def xor_original(a, b):
return a != b
def xor_dnf(a, b):
# (non a et b) ou (a et non b)
return (not a and b) or (a and not b)
for a in (False, True):
for b in (False, True):
assert xor_original(a, b) == xor_dnf(a, b)
print("DNF vérifiée sur les 4 combinaisons")
def xor_original(a, b):
return a != b
def xor_cnf(a, b):
# (a ou b) et (non a ou non b)
return (a or b) and (not a or not b)
for a in (False, True):
for b in (False, True):
assert xor_original(a, b) == xor_cnf(a, b)
print("CNF vérifiée sur les 4 combinaisons")
DNF = OU de (ET de littéraux) — une clause par ligne où f = 1 ; littéral nié si la variable vaut 0 sur cette ligne.
CNF = ET de (OU de littéraux) — une clause par ligne où f = 0 ; littéral nié si la variable vaut 1 sur cette ligne (convention inversée par rapport à la DNF).
Les deux décrivent la même fonction ; on choisit celle qui compte le moins de lignes à traiter, ou celle qu'impose l'outil utilisé (un solveur SAT attend une CNF, un circuit se câble plus naturellement à partir d'une DNF).