Opérations sur les diagrammes binaires de décision

OPÉRATIONS SUR LES DIAGRAMMES BINAIRES DE DÉCISION

Plusieurs opérations liées aux fonctions booléennes telles que la satisfaisabilité, la vérification de la tautologie ou l’équivalence de deux expressions booléennes et l’application des opérations logiques entres les fonctionnes booléennes peuvent être vérifiées par les DBD. Dans ce qui suit, on présente la résolution des opérations les plus intéressantes des fonctions booléennes par les DBD.

ÉVALUATION

Soit f une fonction booléenne sur X = {x1,x2,…,xn} et une assignation a ∶ X → {vrai, f aux} des variables de X. Le problème d’évaluation sert à déterminer la valeur de la fonction booléenne f (x1,x2,…,xn) pour l’assignation a des variables xi,i ∈ [1,n].

Théorème 3. L’évaluation d’une assignation par un DBD s’effectue en O(n).

Démonstration : La valeur de la fonction f pour une assignation des variables d’entrées peut être trouvée en traversant le DBD depuis la racine jusqu’à une feuille en empruntant la branche gauche ou droite de chaque sommet selon la valeur de la variable d’entrée correspondante. Dans le pire cas, le DBD correspondant à une fonction f est composé de n branches entre la racine et une feuille. Donc, la complexité d’une procédure d’évaluation d’une fonction, c’est à dire le parcours d’un DBD depuis sa racine est O(n).

TAUTOLOGIE

On dit qu’une fonction booléenne est une tautologie si elle est toujours vraie pour toute assignation, c’est-à-dire vraie quelle que soit les valeurs de variables. On dit autrement, la table de vérité de cette fonction prend toujours la valeur vrai (1). On peut poser le problème de tautologie d’autre manière : Une fonction booléenne f est une tautologie si et seulement si la fonction f est la fonction identiquement égale à 1.

Théorème 4. La vérification de la tautologie par un DBD est d’ordre O(1).

Démonstration : Pour montrer que la fonction f est une tautologie, il suffit de vérifier si la racine du DBD correspondant à f est la feuille 1 ou non. Il est évident que cela a le coût O(1).

ÉGALITÉ

L’un des plus grand problèmes des fonctions booléennes est de déterminer si deux fonctions booléennes sont égales, surtout, parce que une fonction booléenne peut avoir plusieurs représentations différentes. Ce problème peut paraître simple, mais deux fonctions booléennes ayant des représentations complètement différentes peuvent être égales. Ce problème n’a pas lieu d’être si chaque fonction booléenne f a une unique représentation dans un système de représentation. Donc, pour vérifier l’égalité de deux fonctions, il suffit de vérifier l’égalité de ses représentations.

Théorème 5. La vérification de l’égalité de deux fonctions booléennes par les DBD est d’ordre O(n).

Démonstration : D’après le théorème d’unicité du DBDOR d’une telle fonction , pour tester l’égalité de deux fonctions booléennes f et g, il suffit de comparer les DBD qui les représentent. Soit n la taille du graphe représentant f et m la taille du graphe représentant g, la complexité de l’opération d’égalité dans le pire cas est égale au minimum de n et m, donc elle est d’ordre O(n).

SATISFAISABILITÉ

Le problème de SAT a été discuté dans le premier chapitre (voir section 1.2 pour plus de détails). On peut poser le problème SAT de cette manière. Soient f(x1,x2,…,xn) une fonction booléenne de n variables, a une assignation des variables, et Sf = {a ∈ Bn ∣ f (a) = 1} l’ensemble des assignations qui rendent f vraie. On peut définir trois types de problèmes de satisfaisabilité :

– Satisfaisabilité : On dit que f est satisfaisable si Sf ≠ ∅, c’est-à-dire, elle n’est pas équivalente à la fonction booléenne constante 0.
– Satisfait-Un : Pour une assignation a, Satisfait-Un consiste à déterminer si a ∈ Sf .
– Satisfait-Tous : Satisfait-Tous consiste à calculer Sf.

Théorème 6. La complexité des opérations de vérification de la satisfaisabilité par les DBD est d’ordre O(1), de Satisfait-Un est d’ordre O(n) et de Satisfait-Tous est d’ordre O(n.∣Sf∣).

Démonstration : Pour montrer que la fonction f est satisfaisable, il suffit de vérifier si la racine du DBD correspondant à f est la feuille 0 ou non. Il est évident que cela a le coût O(1). Pour montrer Satisfait-Un, il suffit de partir de la feuille 1 du DBD correspondant à f et de remonter un chemin jusqu’à la racine. La complexité est en O(n). Pour montrer Satisfait-Tous, Il suffit de réitérer autant de fois que nécessaire le Satisfy-Un. Le coût de cette procédure est d’ordre O(n.∣Sf∣).