Pour convertir la logique du premier ordre en CNF:
- Convertir en forme normale de négation. Éliminer les implications et les équivalences: remplacer à plusieurs reprises par; remplacer par. …
- Standardiser les variables. …
- Skolemize la déclaration. …
- Supprimer tous les quantificateurs universels.
- Répartir les OU vers l'intérieur sur les ET: remplacer à plusieurs reprises par.
Qu'est-ce qu'une formule CNF ?
La forme normale conjonctive (CNF) est une approche de la logique booléenne qui exprime des formules sous forme de conjonctions de clauses avec un ET ou un OU. Chaque clause reliée par une conjonction, ou ET, doit être soit un littéral, soit contenir une disjonction, ou un opérateur OU. CNF est utile pour la démonstration automatisée de théorèmes.
Pouvez-vous convertir DNF en CNF ?
Si vous souhaitez introduire des variables supplémentaires, vous pouvez convertir la forme DNF en CNF en temps polynomial en en utilisant la transformation Tseitin. La formule CNF résultante sera équisatisfiable avec la formule DNF d'origine: la formule CNF sera satisfaisable si et seulement si la formule DNF d'origine était satisfaisable.
Comment puis-je obtenir le CNF ?
Écrivez simplement la table de vérité, qui est assez simple à trouver, et déduisez vos CNF et DNF. Si vous voulez trouver DNF, vous devez regarder toutes les lignes qui se terminent par T. Lorsque vous trouvez ces lignes, prenez les valeurs x, y et z de chaque colonne respective. Ainsi, vous obtenez (x∧y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧¬z)∨(¬x∧¬y∧z).
Comment convertir disjonctif enforme normale ?
Une proposition composée est dite en forme normale disjonctive, ou DNF, si elle est une disjonction de conjonctions de termes simples, et si, de plus, chaque proposition la variable se produit au plus une fois dans chaque conjonction et chaque conjonction se produit au plus une fois dans la disjonction.
