MGU et normalisation variable - CNF

Question

I ai lu sur la conversion de premières phrases logiques de commande de forme normale conjonctive, et en effectuant ensuite la résolution.

L'une des étapes de conversion à CNF, est aux variables Standardiser: renommer toutes les variables afin que chaque quantificateur a son propre nom variable unique,

.

La plupart Unifier générale est l'unification moins spécialisée de deux clauses.

Question 1: J'ai cherché à trouver un exemple qui montre quels sont les problèmes potentiels si je ne standardiser les variables, mais toutes les ressources en ligne que je trouve à seulement expliquer le « comment » et non le « pourquoi ». Pourriez-vous me donner un exemple d'un problème potentiel?

Question 2: Le même problème que la première question. Et si nous ne l'utilisons MGU, et utiliser un plus fédérateur spécialisé? Quels sont les problèmes potentiels? Pourriez-vous me donner un exemple?

Mes sincères remerciements. Felipe

Answer 1

1. Voir cette réponse - c'est un exemple d'un ensemble de clauses contradictoires où l'on ne peut tirer un contradiction sans variables renommer. Notez qu'il est que nous avons ne suffit pas à des variables que renommage après la conversion en CNF, pour renommer les variables comme distinctes avant tous application de la règle de résolution. Vous pouvez le voir comme suit: variable A apparaissant dans deux clauses distinctes a un sens différent dans chacun d'eux comme ils sont implicitement universellement quantifiés. Si nous ne renomme pas la variable dans l'une des clauses, nous faisons une fausse hypothèse que la variable signifie la même chose dans les deux clauses.

2. En utilisant MGU, nous tirons la plus clause générale dans une étape de résolution. Si nous utilisons une qui est plus fédérateur spécialisé que leur MGU, la clause qui en résulte est plus faible. Cela signifie que nous ne déduisent toutes les connaissances que nous pourrions, et nous pouvons manquer une dérivation d'une clause vide, même si elle existe. Par exemple: \ Begin {array} {c} P (x, y) \ lor Q (y) \\ \ Lnot Q (d) \\ \ Lnot P (c, d) \ End {array} Si nous faisons un résolutive des deux premières clauses utilisant MGU qui envoie $ y \ à d $, nous obtenons $ P (x, d) $ et nous pouvons procéder à la troisième clause. Si nous prenons un rassembleur plus faible, comme celui qui envoie également $ x \ à d $, nous obtenons $ P (d, d) $ et nous ne sommes pas en mesure de faire une résolvante avec la troisième clause. Cela signifie que la méthode n'est plus complet.