Forme normale négative décomposable

En logique propositionnelle, dans le cadre de la compilation de connaissance, une fonction booléenne est passée d'un langage de représentation standard (par exemple une représentation CNF) vers un langage cible plus adapté pour répondre aux futures requêtes sur la fonction. Les circuits booléens en forme normale négative décomposable — plus succinctement DNNF, de l'anglais Decomposable Negation Normal Form — constituent un de ces langages cibles. Toute fonction booléenne a au moins un circuit DNNF qui lui est équivalent. Les circuits DNNF sont parmi les représentations les plus compactes des fonctions qui permettent de réaliser des tests de cohérence (ou satisfaisabilité) en temps polynomial en la taille du circuit, en contre-partie de tels circuits sont souvent plus larges que les représentations standards de la fonctions, et par un facteur exponentiel.

Définition

Concepts de base sur les circuits booléens

Les circuits considérés ont un nombre fini d'entrées et une seule sortie booléenne. Les entrées sont des variables booléennes ou des constantes vrai (notée $1$) ou faux (notée $0$). On désigne par $var(C)$ l'ensemble des variables en entrée du circuit $C$. La taille de $C$, notée $\vert C\vert$, est le nombre de ses connexions entre portes. Un circuit sur $n$ variables est associé à une fonction booléenne $f:\{0,1\}^{n}\rightarrow \{0,1\}$ dont les modèles (les affectations de variables pour lesquelles la fonction vaut $1$) sont exactement les affectations de variables pour lesquelles la sortie du circuit est mise à $1$ (vrai). Par extension on appelle également ces affectations des modèles du circuit, on utilise $C^{-1}(1)$ pour désigner l'ensemble des modèles de $C$.

Circuits NNF

Les portes utilisées par les circuits sous forme normal négative, ou NNF (de l'anglais Negation Normal Form), sont

• les portes ET ($\wedge$) ;
• les portes OU ($\vee$) ;
• les portes NEG ($\lnot$) à une entrée.

Il n'y a pas de limite sur l'arité en sortie de ces portes. Il n'y a pas de limite sur l'arité en entrée des portes ET et OU.

Un circuit $C$ est sous forme NNF si

• le graphe orienté de ses portes est acyclique et
• les portes NEG sont uniquement appliquées sur des entrées de $C$.

Régulièrement on étend les entrées des circuits aux variables booléennes ($x$) et à leurs compléments ($\neg x$), de sorte qu'il n'y a plus de portes NEG dans les circuits NNF.

Circuits DNNF

Une porte ET est décomposable si les sous-circuits branchés en entrée agissent sur des ensembles distincts de variables. Formellement, les circuits $C_{1},C_{2},...,C_{m}$ branchés sur les entrées d'une porte ET décomposable vérifient $var(C_{i})\cap var(C_{j})=\emptyset$ pour tout $i\neq j$, autrement dit si la variable $x$ ou son complément est une entrée de $C_{i}$, alors ni $x$ ni $\neg x$ n'est une entrée $C_{j}$. Un circuit NNF décomposable, ou DNNF (de l'anglais Decomposable Negation Normal Form) est un circuit NNF dont toutes les portes ET sont décomposables.

A gauche : un circuit NNF dont la première porte est un ET non décomposable. À droite : un circuit DNNF représentant la même fonction booléenne.

Terminologie : circuits ou formules ?

Certaines représentations de fonctions booléennes sont désignés comme des formules, par exemple des formules DNF ou CNF, en général on évite d'employer ce terme pour les NNF. Une formule booléenne désigne un circuit booléen dont chaque porte ne peut être l'entrée que d'une seule autre porte (l'arité en sortie des portes est au plus 1). Cette condition est toujours remplie par les circuits CNF et DNF de sorte que les appellations « formules CNF » et « formules DNF » sont correctes. Cependant les NNF, et a fortiori les DNNF, ne requièrent pas de limite sur l'arité en sortie des portes, il est donc préférable de les désigner comme des circuits booléens.

Relations d'inclusion et de compacité pour les DNNF

Par définition, les DNNF forment une sous-classe des NNF, ce que l'on notera

${\textsf {DNNF}}\subset {\textsf {NNF}}$

Les DNNF englobent d'autres classes importantes de circuits, notamment les DNF (Disjunctive Normal Form, ou en français : Forme Normale Disjonctive) et certains types de BDD (Binary Decision Diagram, ou en français : Diagramme de Décision Binaires).

DNNF et DNF

Les DNF sont des DNNF à condition d'être cohérentes : c'est-à-dire qu'aucun terme ne contient à la fois une variable $x$ et son complément $\neg x$. Chaque terme cohérent d'une DNF forme une porte ET décomposable, les DNF sont donc des DNNF à deux étages : un premier étage de portes ET correspondant aux différents termes de la DNF, et un second étage composé d'une unique porte OU sur laquelle les portes ET des termes sont branchées en entrée.

${\textsf {DNF}}\subset {\textsf {DNNF}}$

DNNF et BDD

A gauche : un nœud de décision sur la variable $x$. À droite : la traduction de ce nœud en circuit.

Les diagrammes de décision binaires (BDD) ont une traduction NNF naturelle. Une méthode pour l'obtenir consiste à convertir les nœuds de décision de la BDD en circuits NNF comme indiqué sur la figure. Quand on atteint les nœuds terminaux $0$ et $1$, ceux-ci sont transformés en entrées constantes $0$ ou $1$. Comme le graphe orienté d'une BDD est acyclique et qu'aucune porte NEG n'est introduite dans la procédure sauf sur des entrées booléennes, le circuit obtenu est sous forme NNF. Si dans le cas représenté sur la figure, $x$ n'appartient ni à $var(C_{0})$ ni à $var(C_{1})$ alors le circuit pour ce nœud de décision est une DNNF.

On obtient donc des DNNF quand les BDD sont telles que chaque variable apparaît au plus une fois par chemin. Ces BDD forment la classe des FBDD (Free Binary Decision Diagram). Par souci de simplicité on considère directement les FBDD comme une sous-classe des DNNF. Une sous-classe importante des FBDD sont les OBDD (Ordered Binary Decision Diagram), pour lesquels l'ordre d'apparition des variables est le même pour chaque chemin. Les OBDD forment donc aussi une sous-classe de DNNF.

${\textsf {OBDD}}\subset {\textsf {FBDD}}\subset {\textsf {DNNF}}$

Relation de compacité

Différents circuits représentant une même fonction booléenne sont comparés selon leur taille (nombre de connexions entre portes). Soit deux classes des circuits ${\mathcal {L}}$ et ${\mathcal {L}}'$ permettant de représenter n'importe quelle fonction booléenne, on dit que ${\mathcal {L}}$ permet des représentations plus compactes que ${\mathcal {L}}'$ (noté ${\mathcal {L}}\preceq {\mathcal {L}}'$) quand il existe une polynôme réel $p$ tel que pour chaque circuit $C'\in {\mathcal {L}}'$ il existe un circuit équivalent $C\in {\mathcal {L}}$ vérifiant $\vert C'\vert \leq p(\vert C\vert )$. La relation $\preceq$ est transitive. Il est clair que si ${\mathcal {L}}'\subset {\mathcal {L}}$, alors ${\mathcal {L}}\preceq {\mathcal {L}}'$, puisque chaque $C'$ dans ${\mathcal {L}}'$ appartient aussi à ${\mathcal {L}}$ et que donc la définition précédente s'applique avec $p$ le polynôme identité.
On note ${\mathcal {L}}\prec {\mathcal {L}}'$ quand ${\mathcal {L}}\preceq {\mathcal {L}}'$ mais que la relation inverse est fausse. C'est-à-dire que ${\mathcal {L}}'\npreceq {\mathcal {L}}$ : il existe une famille ${\mathcal {F}}$ (nécessairement infinie) de circuits dans ${\mathcal {L}}$ et une fonction $f$ super-polynomiale (i.e., tout polynôme réel est dans $o(f)$, typiquement $f(n)=\Omega (2^{n})$ ou $f(n)=\Omega (n^{\log {n}})$) telles que pour tout $C\in {\mathcal {F}}$ et $C'\in {\mathcal {L}}'$ équivalent à $C$, on a $\vert C'\vert \geq f(\vert C\vert )$.

Les relations de compacités entre les DNNF et les classes de circuits précédemment décrites sont strictes :

${\textsf {DNF}}\prec {\textsf {DNNF}}\prec {\textsf {NNF}}$ et ${\textsf {FBDD}}\prec {\textsf {DNNF}}$

Les OBDD formant une sous-classe de FBDD, on a aussi ${\textsf {OBDD}}\prec {\textsf {DNNF}}$ par transitivité.

Requêtes sur des circuits DNNF

Faisabilité des différentes requêtes en temps polynomial

Le choix d'une classe de circuits pour représenter une fonction booléenne dépend des requêtes auxquelles la fonction sera sujette. Les requêtes peuvent être des problèmes de décision (par exemple déterminer si la fonction a un modèle) ou des tâches plus constructives (par exemple retourner la liste des modèles de la fonction). On dit que l'on satisfait une requête pour une classe de circuits ${\mathcal {L}}$ quand il existe un algorithme qui prend en entrée (entre autres) un circuit $C$ de ${\mathcal {L}}$ et retourne le résultat de la requête sur $C$ en temps polynomial.

Certaines requêtes sont systématiquement étudiées en compilation de connaissance. Ces requêtes sont décrites dans le tableau suivant. Leur faisabilité pour la classe des DNNF est indiquée par un symbole en fin de ligne :

• $\checkmark$ : on peut satisfaire la requête pour la classe des DNNF ;
• $\bullet$ : on ne peut pas satisfaire la requête pour la classe des DNNF, sauf si P = NP.

Notation	Nom	Description
CO	Test de cohérence (consistency check)	Étant donné un circuit $C$, déterminer en temps polynomial (en $|C|$) s'il existe une affectation de variables satisfaisant $C$.	$\checkmark$
VA	Test de validité (validity check)	Étant donné un circuit $C$, déterminer en temps polynomial (en $|C|$) si toutes les affectations de variables satisfont $C$.	$\bullet$
CE	Test de clause impliquée (clausal entailment check)	Étant donnés une clause $\gamma$ et un circuit $C$, déterminer en temps polynomial (en $|C|$) si $C\models \gamma$.	$\checkmark$
IM	Test de terme impliquant (implicant check)	Étant donnés un terme $\tau$ et un circuit $C$, déterminer en temps polynomial (en $|C|$) si $\tau \models C$.	$\bullet$
SE	Test d'implication (sentential entailment check)	Étant donnés deux circuits $C$ et $C'$ appartenant à la même classe, déterminer en temps polynomial (en $|C|$ et $\vert C'\vert$) si $C\models C'$.	$\bullet$
EQ	Test d'équivalence (equivalence check)	Étant donnés deux circuits $C$ et $C'$ appartenant à la même classe, déterminer en temps polynomial (en $|C|$ et $\vert C'\vert$) si $C\equiv C'$.	$\bullet$
CT	Comptage des modèles (model counting)	Étant donné un circuit $C$, retourner en temps polynomial (en $|C|$) le nombre d'affectations de variables satisfaisant $C$.	$\bullet$
ME	Énumération des modèles (model enumeration)	Étant donné un circuit $C$, retourner en temps polynomial (en $|C|$ et $|C^{-1}(1)|$) toutes les affectations de variables satisfaisant $C$.	$\checkmark$

Test de cohérence (CO)

Tester l'existence d'un modèle n'est en général pas réalisable en temps polynomial pour n'importe quel circuit NNF. Dans le cas des circuits DNNF, la décomposabilité des portes ET ($\wedge$) rend le test faisable en temps polynomial.

Soit $g$ une porte ET décomposable $g=C_{1}\wedge \dots \wedge C_{m}$. Supposons pour tout $i$, le sous-circuit $C_{i}$ retourne vrai pour une affectation $a_{i}$ des variables de $var(C_{i})$. Par décomposabilité les ensembles $var(C_{1}),\dots ,var(C_{m})$ sont deux-à-deux disjoints, donc il ressort que $a=a_{1}\wedge \dots \wedge a_{m}$ est une affectation cohérente des variables de $var(g)$ — c'est-à-dire que $a$ affecte une et une seule valeur à chaque variable de $var(g)$ — et $a$ est clairement un modèle de $g$. Ainsi un circuit dont la racine est une porte ET décomposable admet un modèle si et seulement si tous les sous-circuits en entrée admettent un modèle, cette condition est nécessaire mais en général pas suffisante pour les portes ET non décomposables.

Un algorithme possible, que l'on note $A_{\textbf {CO}}$, pour tester l'existence de modèles d'une DNNF $C$ fonctionne récursivement selon le protocole suivant :

• si la sortie de $C$ est une porte $g$ de type OU, $g=C_{1}\vee \dots \vee C_{m}$, alors $A_{\textbf {CO}}(C)$ retourne vrai si et seulement si au moins un des $A_{\textbf {CO}}(C_{i})$ retourne vrai ;
• si la sortie de $C$ est une porte $g$ de type ET, $g=C_{1}\wedge \dots \wedge C_{m}$, alors $A_{\textbf {CO}}(C)$ retourne vrai si et seulement si tous les $A_{\textbf {CO}}(C_{i})$ retournent vrai ;
• pour des entrées Booléennes $x$ ou $\neg x$, $A_{\textbf {CO}}(x)$ et $A_{\textbf {CO}}(\neg x)$ retournent vrai ;
• pour une entrée constante, $A_{\textbf {CO}}(1)$ retourne vrai et $A_{\textbf {CO}}(0)$ retourne faux.

Chaque porte du circuit génère au plus autant d'appels récursifs que son arité en entrée, donc le nombre d'appels récursifs est en $O(\vert C\vert )$ et $A_{\textbf {CO}}(C)$ s'exécute en temps polynomial en $\vert C\vert$.

Test de clause impliquée (CE)

Étant donné une clause $\gamma =l_{1}\wedge \dots \wedge l_{n}$ sur les variables $var(\gamma )=\{x_{1},\dots ,x_{n}\}$ où chaque $l_{i}$ représente $x_{i}$ ou $\neg x_{i}$, on peut associer le terme $\neg \gamma$ à une affectation des variables de $var(\gamma )$ (c'est l'unique modèle de $\neg \gamma$ sur $var(\gamma )$).

Soit $C$ un circuit sur un sur-ensemble de $var(\gamma )$. On désigne par $C\vert (\neg \gamma )$ le circuit obtenu en remplaçant les variables d'entrée appartenant à $var(\gamma )$ par leur affectation ($0$ ou $1$) dans $\neg \gamma$. On dit que l'on a conditionné $C$ sur $\neg \gamma$. Si $C$ est une DNNF, affecter des valeurs à certaines variables d'entrée n'impacte pas la décomposabilité des portes ET, donc $C\vert (\neg \gamma )$ est encore une DNNF dont la taille n'est pas supérieure à celle de $C$.

$C$ implique $\gamma$ (noté $C\models \gamma$) si et seulement si $C\equiv C\wedge \gamma$. Après conditionnement sur $\neg \gamma$ des deux côtés, on obtient que $C\models \gamma$ si $C\vert (\neg \gamma )\equiv 0$. Donc pour tester $C\models \gamma$ on peut simplement vérifier que $C\vert (\neg \gamma )$ n'a pas de modèle. Si $C$ est une DNNF, un algorithme $A_{\textbf {CE}}$ pour le test de clause impliquée se réduit à un appel à $A_{\textbf {CO}}$ : $A_{\textbf {CE}}(C,\gamma )$ retourne vrai si et seulement si $A_{\textbf {CO}}(C\vert (\neg \gamma ))$ retourne faux. $A_{\textbf {CO}}(C\vert (\neg \gamma ))$ s'exécute en temps polynomial en la taille de $C\vert (\neg \gamma )$, laquelle est inférieure à $\vert C\vert$, donc $A_{\textbf {CE}}(C,\gamma )$ s'exécute en temps polynomial en $\vert C\vert$.

Énumération des modèles (ME)

On veut énumérer tous les modèles d'un circuit $C$ sous forme DNNF. On peut déjà tester l'existence de modèles avec le test de cohérence sur $C$. Par la suite si on détecte que $C$ a des modèles, on construit un arbre à $n+1$ niveaux dont chaque feuille (ici un nœud de niveau $n$, la racine étant le niveau $0$) correspond à un modèle du circuit. Les nœuds de l'arbre de niveau $i$ correspondent à des affectations de variables sur $\{x_{1},\dots ,x_{i}\}$ (par convention vide pour la racine, qui est le niveau $0$). La construction commence depuis la racine et suit la règle suivante : tant qu'il existe un nœud de niveau $i<n$ sans fils, soit $a_{i}$ l'affectation de variables correspondante :

• si $C\vert (a_{i}\wedge x_{i+1})$ a un modèle, on lui ajoute à ce nœud un fils correspondant à $a_{i}\wedge x_{i+1}$ ;
• si $C\vert (a_{i}\wedge \neg x_{i+1})$ a un modèle, on lui ajoute à ce nœud un fils correspondant à $a_{i}\wedge \neg x_{i+1}$.

À noter qu'au moins un des deux tests réussi puisqu'on sait que le circuit de départ a des modèles. La construction prend fin quand tous les chemins sont de taille $n$, les modèles de $C$ sont alors les affectations de variables correspondant aux feuilles.

Les circuits conditionnés $C\vert (a_{i}\wedge x_{i+1})$ sont des DNNF de taille inférieure à $\vert C\vert$ donc tester l'existence de modèles se fait en temps polynomial avec $A_{\textbf {CO}}$. En tout, l'algorithme fait $O(n\vert C^{-1}(1)\vert )$ tests, d'où son temps d'exécution polynomial en $\vert C\vert$ et $\vert C^{-1}(1)\vert$.