Mise sous forme normale, pas à pas

(a) Trois étapes, dans l'ordre.

L'étape 2 mérite le détail : De Morgan sur $\neg (A\vee B)$ donne $\neg A\wedge \neg B$, d'où $\neg \neg p\wedge \neg (q\wedge \neg r)$ ; la double négation simplifie le premier facteur en $p$, et De Morgan sur le second donne $\neg q\vee \neg \neg r=\neg q\vee r$.

Le résultat est une fnc à deux clauses, dont une réduite à un seul littéral : $(p)\wedge (\neg q\vee r)$. Une clause d'un seul littéral s'appelle une clause unitaire, et c'est l'information la plus précieuse pour un solveur — elle force $p:=V$ sans aucun choix.

Ses trois modèles, vérifiés : $(V,V,V)$, $(V,F,V)$, $(V,F,F)$. On note que $p$ vaut $V$ dans les trois, comme la clause unitaire l'annonçait.

(b) Ici l'étape 3 travaille. On distribue $\vee$ sur $\wedge$, deux fois :

$$(p\wedge q)\vee (r\wedge s)\equiv (p\vee r)\wedge (p\vee s)\wedge (q\vee r)\wedge (q\vee s).$$

Quatre clauses, et l'on voit le mécanisme : il faut choisir un littéral dans le premier groupe et un dans le second, soit $2\times 2$ combinaisons. Avec $n$ groupes de deux, ce serait $2^n$ — c'est exactement l'exemple du cours.

Le piège à nommer : l'ordre des étapes n'est pas négociable. Si l'on distribue avant d'avoir poussé les négations, on distribue sur une formule où un $\neg$ coiffe encore un $\wedge$, et le résultat n'est pas une fnc. Et si l'on pousse les négations avant d'avoir éliminé les $\to$, De Morgan ne s'applique pas : $\neg (a\to b)$ n'est ni $\neg a\to \neg b$ ni rien de ce genre — il vaut $a\wedge \neg b$, ce qu'on ne voit qu'après la décomposition.