Logique (mathématiques)/Exercices/Méthode de Quine

L'exercice

Soit la formule : $\phi =(A\land (B\rightarrow \neg (A\lor C)))\rightarrow (C\lor \neg A)$.

• Calculez ses formes normales disjonctive et conjonctive quelconques (pas obligatoirement canonique) par la méthode de Quine (via ses modèles et contre-modèles).

Solution

• Les modèles sont les branches où l’on obtient "1" :

${\begin{aligned}&A=0\\&A=1,B=0,C=1\\&A=1,B=1\\\end{aligned}}$
La forme normale disjonctive est donc : $FND\equiv (\neg A)\lor (A\land \neg B\land C)\lor (A\land B)$

• Les contre-modèles sont les branches où l’on obtient "0", ici, il n'y en a qu'un :

${\begin{aligned}&A=1,B=0,C=0\\\end{aligned}}$
La forme normale conjonctive est donc : $FNC\equiv (\neg A)\land B\land C$