Une technique basée sur des graphes pour représenter des fonctions booléennes comme des graphes acycliques orientés (diagrammes de décision binaires, BDD) avec des règles de réduction (fusion des sous-graphes isomorphes et élimination des tests redondants) qui peuvent produire une forme canonique réduite et ordonnée (ROBDD) pour un ordre de variables fixé, permettant des vérifications d'équivalence et de satisfiabilité efficaces.

Principe

Représenter la fonction par un graphe de décision et appliquer deux règles de réduction fondamentales : (1) fusionner les sous-graphes isomorphes (partage via table d'unicité) et (2) supprimer les nœuds dont les successeurs 'low' et 'high' sont identiques ; avec un ordre de variables fixe ces réductions produisent une forme canonique de la fonction booléenne.

Démonstration

Étant donnée une fonction booléenne f sur des variables x1 < x2 < x3, construire son DAG de décision complet puis appliquer la réduction : fusionner les sous-graphes identiques et supprimer les nœuds dont les successeurs bas/haut coïncident, obtenant une ROBDD compacte qui peut être comparée par égalité de pointeurs pour tester l'équivalence avec une autre fonction sous le même ordre.

Mauvaise application

Supposer que la réduction BDD donne toujours une représentation compacte indépendamment de l'ordre des variables — en réalité de mauvais ordres peuvent provoquer une explosion exponentielle ; ou utiliser des BDD pour des fonctions requérant naturellement d'autres stratégies de décomposition (p.ex. chaînes d'addition binaire) sans envisager des représentations alternatives.

Conséquence

Lorsque l'ordre des variables est bien choisi, la réduction produit une forme canonique permettant un test d'équivalence en temps polynomial et permet d'implémenter efficacement de nombreuses opérations booléennes symboliques ; elle sous-tend aussi des outils de model checking et de manipulation symbolique.

Inversion

En contraste avec CNF-SAT ou une énumération explicite des tables de vérité : ces techniques énumèrent affectations ou clauses, tandis que les BDD réduits fournissent une représentation structurée partagée ; inverser l'approche suggère de choisir des algorithmes d'énumération lorsque la taille du BDD devient incontrôlable.

Limite

S'applique aux fonctions booléennes et dépend crucialement d'un ordre de variables fixé ; elle ne prévient pas le coût exponentiel dans le pire cas pour certaines fonctions et n'est pas directement une bonne représentation pour des objets non booléens ou de l'arithmétique d'ordre élevé sans décomposition.

Tension sémantique

Tension entre OBDD (ordonné, réduit) et d'autres représentations comme FBDD (BDD libre), SDDs ou codages CNF : les compromis portent sur canonicité, sensibilité à l'ordre des variables et les classes de fonctions représentées de façon compacte.

Synthèse

La réduction de BDD transforme un processus décisionnel pour une fonction booléenne en un graphe partagé canonique en fusionnant les sous-graphes isomorphes et en supprimant les redondances sous un ordre de variables fixe ; la ROBDD résultante, lorsqu'elle est compacte, permet des tests d'équivalence et des opérations symboliques efficaces.