Est complète résolution ou seulement-complète réfutation?

Question

En passant par quelques tutoriels de représentation des connaissances sur résolution en ce moment, et je suis tombé sur < a href = "http://www.cs.toronto.edu/~sheila/384/w11/Lectures/csc384w11-Lecture-05-KR.pdf"> glissière 05.KR, no77 .

Il est mentionné que « la procédure est terminée ».

Je pense que cette exhaustivité ne peut pas dire que si une phrase est impliqué par KB, il sera dérivé par la résolution. Par exemple, la résolution ne peut pas déduire $ (q \ lor \ neg q) $ d'une seule clause KB avec $ \ neg p $. (Exemple de KRR, brachmane et Levesque, page 53).

Aide Quelqu'un pourrait me comprendre ce que l'on entend dans cette diapositive? Est-ce le caractère complet de la diapositive se réfèrent à être refutaton-complet et non une preuve complète procédure?

Answer 1

La résolution est complète en tant que système de réfutation. Autrement dit, si $ S $ est un ensemble de clauses contradictoires, alors la résolution peut démentir $ S $, à savoir $ S \ vdash \ bot $.

Ceci est suffisant puisque $ T \ vdash A $ est équivalent à la tasse T de $ \ {\ lnot A \} \ vdash \ bot $. Donc, si nous voulons une formule $ A $ est dérivable de $ T $, nous avons seulement besoin de vérifier s'il y a une preuve de réfutation pour la coupe de $ T \ {\ lnot A \} $ qui peut être vérifié à l'aide de résolution.

Answer 2

La résolution est seulement complète réfutationnellement, comme vous l'avez mentionné. Ceci est destiné et très utile, car il réduit considérablement l'espace de recherche. Au lieu d'avoir à terme tirer toutes les conséquences possibles (pour trouver une preuve d'une certaine conjecture), la résolution ne cherche à tirer la clause vide.

Answer 3

Il est également implicationally complet dans le sens suivant:

Si un ensemble de clauses $ F $ implique une clause de non tautologique $ C $, il est toujours possible de tirer une seule clause $ C '$ subsumant $ C $ (À savoir $ C » \ subseteq C $).

Source:
Christian G. Fermüller, implicationnel Exhaustivité de la Résolution signée, 2002

Notez que le résultat initial est refered à:
R.C.T. Lee. Un théorème de complétude et un programme informatique pour théorèmes nding dérivables des axiomes donnés . doctorat Thèse, Université de Californie, Berkeley, 1967.