Variables distinctes pour différentes clauses

Edit: j'ai trouvé un meilleur exemple. Considérez ces clauses: Évidemment, cet ensemble de clauses est contradictoire. Mais sans renommer les variables, le seul résolvant possible est et plus aucun résolvant n'est possible - tous conduisent à substituer à , ce qui est impossible.

\begin{aligned} \neg P (x) \lor P (f (x)) \\ P (x) \\ \neg P (f (f (x))) \end{aligned}

$\begin{align} & \lnot P(x) \lor P(f(x)) \\ & P(x) \\ & \lnot P(f(f(x)))\\ \end{align}$

P (f (x))

$P(f(x))$

f (x)

$f(x)$

x

$x$

Edit: Réfléchissez à la signification des clauses. Chaque clause est implicitement universellement quantifiée. La signification de ses variables n'est donc fixée à rien. Supposons maintenant que vous ayez deux clauses contenant chacune . Si vous effectuez une résolution sans renommer dans l'un d'eux, alors vous ajoutez un sens à qu'il n'a pas: vous dites que signifie la même chose dans les deux clauses, ce qui n'est pas vrai. Si vous n'avez pas de variables distinctes dans vos clauses, la résolution vous donnera des conclusions trop faibles. $x$ $x$ $x$ $x$

(La réponse d'origine.) Par exemple, nous allons avoir 4 clauses:

$A\lor B(x)$
$\lnot A\lor C(x)$
$\lnot B(c)$
$\lnot C(d)$

où sont des variables et des constantes . Si nous effectuons une résolution sur les deux premiers sans renommer , nous obtiendrons . Nous pouvons continuer avec pour obtenir mais maintenant nous ne pouvons pas le résoudre avec . $x, y$ $c, d$ $x$ $B(x)\lor C(x)$ $\lnot B(c)$ $C(c)$ $\lnot C(d)$

D'un autre côté, si nous renommons en dans le second pour avoir un ensemble de variables disjointes, nous obtiendrons partir de la première étape de résolution et nous pouvons dériver une clause vide en utilisant et . $x$ $y$ $B(x)\lor C(y)$ $\lnot B(c)$ $\lnot B(d)$

Petr Pudlák
la source

Lorsque j'essaie cela dans mon prouveur avec des variables distinctes désactivées, il résout avec pour donner , obtient également et de là la clause vide, donc le résultat final est le même. Suis-je en train de manquer quelque chose?

B (x)

$B(x)$

\neg B (c)

$\lnot B(c)$

A

$A$

\neg A

$\lnot A$

rwallace

@rwallace Ne pas avoir de variables distinctes ne signifie pas que vous ne pouvez pas dériver la clause vide, juste que les méthodes ne sont pas complètes. Si vous renommez toujours des variables, peu importe l'ordre dans lequel vous choisissez les clauses, vous dériverez toujours la clause vide si l'ensemble d'origine n'est pas satisfaisant - la méthode est terminée. Mais, si vous ne renommez pas de variables, alors (comme le montre l'exemple), l'ordre importe soudainement - certaines séquences de dérivations ne trouveront pas la clause vide. Et, un prouveur ne peut pas "dire" à l'avance quelle séquence de dérivations est la bonne.

Petr Pudlák

Mais n'est-il pas vrai qu'une méthode complète doit finalement essayer toutes les dérivations possibles (sauf si elle trouve d'abord la clause vide)? Pour être sûr qu'il n'y a aucune garantie, il essaiera les dérivations que j'ai mentionnées avant celles que vous avez mentionnées, mais lorsque celles que vous avez mentionnées échouent en raison du manque de variables distinctes, celles que j'ai mentionnées sont toujours ouvertes et une méthode complète doit revenir en arrière et essayer tôt ou tard?

rwallace

Votre addendum concernant le sens des clauses dans l'abstrait est logique, mais il me semble que si tel est le cas, il devrait être possible de trouver un cas de test, quelque chose que je puisse alimenter dans un prouveur et lui faire donner la mauvaise réponse si la fonction de variables distinctes est désactivée. Je n'ai tout simplement pas pu trouver un tel cas de test jusqu'à présent.

rwallace

@rwallace Pourquoi voudriez-vous faire cela? La résolution est une méthode complète et vous savez qu'en toutes circonstances, il n'est nécessaire d'effectuer une résolution sur chaque paire de clauses qu'une seule fois. Vous proposez éventuellement d'essayer toutes les séquences possibles sur la façon de procéder au retour en arrière. Cela se traduira par une augmentation vraiment énorme de la complexité de l'algorithme, même pas comparable à distance avec simplement renommer des variables à chaque étape.

Petr Pudlák

Variables distinctes pour différentes clauses

Réponses: