Lire les deux formes normales dans la table

1. La table, calculée :

Cinq lignes vraies, trois fausses.

2. La fnd complète : une conjonction par ligne vraie, où chaque variable apparaît sous sa forme positive si elle vaut $V$, niée sinon.

$$\phi \equiv (p\wedge q\wedge r)\vee (p\wedge \neg q\wedge r)\vee (p\wedge \neg q\wedge \neg r)\vee (\neg p\wedge q\wedge r)\vee (\neg p\wedge \neg q\wedge r).$$

Cinq termes, un par ligne vraie. Chaque terme est vrai pour cette seule valuation : la disjonction décrit donc exactement l'ensemble des modèles.

3. La fnc complète suit le procédé dual : une clause par ligne fausse, avec les littéraux inversés.

$$\phi \equiv (\neg p\vee \neg q\vee r)\wedge (p\vee \neg q\vee r)\wedge (p\vee q\vee r).$$

Trois clauses, une par ligne fausse. L'inversion s'explique : la clause doit être fausse exactement sur la ligne dont elle provient, et une disjonction n'est fausse que lorsque tous ses littéraux le sont.

Pourquoi la fnc est plus courte ici : parce que $\phi$ a plus de modèles que de contre-modèles. La règle est générale et vaut la peine d'être retenue :

La somme des deux tailles vaut toujours $2^n$ termes-et-clauses : on ne peut pas être court des deux côtés à la fois, et l'une des deux est toujours $\le 2^{n-1}$. Toute la question est de savoir laquelle — ce qui, en général, demande de connaître la table, donc $2^n$ calculs.

Vérification : la fnd complète ci-dessus a été réévaluée sur les huit valuations et coïncide avec $\phi$.