Formes normales

Dans les leçons précédentes de cette unité, on a donné un sens aux formules : la leçon sur la sémantique de la logique propositionnelle a prolongé chaque valuation à toutes les formules ; la leçon sur la conséquence et l’équivalence sémantiques a défini l’équivalence $\varphi \eqsem \psi$ et démontré le remplacement sémantique ; la leçon sur les lois généralisées de De Morgan et de distributivité a étendu ces lois aux conjonctions et aux disjonctions de $n$ formules ; et la leçon sur la complétude fonctionnelle a montré que toute fonction de vérité est représentée par une formule. Or une fonction de vérité est représentée par une infinité de formules, qui peuvent être très différentes les unes des autres : $(v_1 \rightarrow v_2)$, $\neg(v_1 \wedge \neg v_2)$ et $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ sont trois noms de la même chose. S’il en est ainsi, il convient de choisir dans chaque classe d’équivalence un représentant de forme fixe, qui se lise sans effort et avec lequel certaines questions se résolvent en regardant. Voilà ce que sont les formes normales.

Littéraux, clauses et formes normales

Rappelons, de la leçon sur les lois généralisées, la notation de la conjonction et de la disjonction de $n$ formules, définie par récurrence et en associant à gauche ; celle d’une seule formule est la formule elle-même.

Dans la même leçon, on a démontré que l’ordre et le regroupement des termes n’altèrent pas la formule à équivalence près (associativité généralisée et indépendance de l’ordre et des répétitions) ; c’est pourquoi nous écrirons aussi $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ sans parenthèses, le regroupement étant entendu à gauche.

Un littéral est une variable $v_n$, que l’on appelle littéral positif, ou la négation $\neg v_n$ d’une variable, que l’on appelle littéral négatif. L’opposé d’un littéral $\ell$, que nous notons $\ell^{*}$, est le littéral de la même variable et de l’autre signe :

Il découle de la définition que $(\ell^{*})^{*} = \ell$. Deux littéraux forment une paire complémentaire si l’un est l’opposé de l’autre, comme $v_3$ et $\neg v_3$.

Une clause est une disjonction de littéraux, $\bigvee_{j=1}^{k} \ell_j$, et une conjonction élémentaire est une conjonction de littéraux, $\bigwedge_{j=1}^{k} \ell_j$, avec $k \geq 1$ dans les deux cas ; un littéral seul est donc à la fois une clause et une conjonction élémentaire. On dit qu’un littéral figure dans une clause ou dans une conjonction élémentaire s’il est l’un de ses $\ell_j$.

Une formule est en forme normale disjonctive si elle est une disjonction de conjonctions élémentaires, et en forme normale conjonctive si elle est une conjonction de clauses ; c’est-à-dire si elle est, respectivement, de l’une des deux formes suivantes, où $m$ et $k_1, \ldots, k_m$ sont des entiers naturels et chaque $\ell_{i,j}$ est un littéral :

Nous dirons que $\Phi$ est une forme normale disjonctive de $\varphi$ si elle est en forme normale disjonctive et $\varphi \eqsem \Phi$, et de même pour la conjonctive. Les longueurs $k_i$ peuvent varier d’une conjonction (ou d’une clause) à l’autre : exiger le même nombre de littéraux dans toutes obligerait à compléter par des répétitions et n’ajouterait rien.

Il convient de s’arrêter sur ce que signifie « être en forme normale ». C’est une propriété de la chaîne de cercles et de disques, non de son sens : la leçon sur la récurrence sur les entiers et l’induction sur les formules a démontré la lecture unique, de sorte que demander si une formule est une disjonction, et de quoi, n’a qu’une réponse. Or les abréviations officielles font que certaines formules sont en forme normale sans le paraître. L’implication $(v_1 \rightarrow v_2)$ est définie comme $(\neg v_1 \vee v_2)$ : ce n’est pas qu’elle équivaut à cette clause, c’est qu’elle est cette chaîne même, et elle est donc déjà en forme normale. Plus surprenante est la double négation. Par les définitions de $\neg$ et de $\vee$, la chaîne $(\varphi \vee \varphi)$ est $\neg(\varphi \downarrow \varphi)$, c’est-à-dire $\neg\neg\varphi$ ; d’où $\neg\neg v_1$ n’est pas un littéral, mais est, symbole par symbole, la clause $(v_1 \vee v_1)$.

La valeur des conjonctions et des disjonctions

De la leçon sur la sémantique, on reprend les valeurs des connecteurs dérivés : $v(\neg\varphi) = 1 - v(\varphi)$ ; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$, qui vaut $1$ si et seulement si les deux valent $1$ ; et $v(\varphi \vee \psi) = 0$ si et seulement si les deux valent $0$. La leçon sur les lois généralisées de De Morgan et de distributivité les a étendues à $n$ formules, par récurrence sur le nombre de termes, dans le lemme de la valeur : pour toute valuation $v$, la conjonction $\bigwedge_{i=1}^{n} \varphi_i$ vaut $1$ sous $v$ si et seulement si chaque $\varphi_i$ vaut $1$ sous $v$, et la disjonction $\bigvee_{i=1}^{n} \varphi_i$ vaut $1$ sous $v$ si et seulement si l’une des $\varphi_i$ vaut $1$ sous $v$. Ce lemme, que l’on cite ici sans en répéter la démonstration, est l’instrument avec lequel on calcule la valeur de n’importe quelle forme normale.

Le second cas passe facilement inaperçu : en niant une forme normale, on a tendance à écrire $\neg\ell_{i,j}$ au lieu d’un littéral, et $\neg\neg v_n$ n’en est pas un. C’est la double négation qui ramène le résultat dans le moule.