¿La resolución es completa o solo completa de refutación?

Question

Ir a través Algunos tutoriales de representación del conocimiento en resolución en este momento, y me encontré Diapositiva 05.kr, No77.

Allí se menciona que "el procedimiento también está completo".

Creo que esta integridad no puede significar que si KB implica una oración, entonces se derivará por resolución. Por ejemplo, la resolución no puede derivar $ (q lor neg Q) $ de un KB con una sola cláusula $ neg P $. (Ejemplo de KRR, Brachman y Levesque, página 53).

¿Alguien podría ayudarme a averiguar qué se entiende en esta diapositiva? ¿La integridad de la diapositiva se refiere a ser refutaton-complete y no un procedimiento de prueba completo?

Answer 1

La resolución se completa como un sistema de refutación. Es decir, si $ S $ es un conjunto contradictorio de cláusulas, entonces la resolución puede refutar $ S $, es decir, $ S VDash Bot $.

Esto es suficiente ya que $ t vDash a $ es equivalente a $ t cup { lnot a } vDash Bot $. Entonces, si queremos ver que una fórmula $ a $ se sea derivable de $ t $, solo necesitamos verificar si hay una prueba de refutación para $ t cup { lnot a } $ que se puede verificar usando la resolución.

Answer 2

La resolución solo es refutacionalmente completa, como mencionó. Esto es destinado y muy útil, porque reduce drásticamente el espacio de búsqueda. En lugar de tener que derivar eventualmente todas las consecuencias posibles (para encontrar una prueba de alguna conjetura), la resolución solo está tratando de derivar la cláusula vacía.

Answer 3

También está implacablemente completo en el siguiente sentido:

Si un conjunto de cláusulas $ f $ implica una cláusula no tautológica $ C $, entonces siempre es posible obtener una cláusula única $ C '$ que subsume $ C $ (es decir, $ c' subseteq c $).

Fuente:
Christian G. Fermüller, Integridad implacable de la resolución firmada, 2002

Tenga en cuenta que se hace referencia al resultado original:
RCT Lee. Un teorema de integridad y un programa informático para los teoremas que se derivan de los axiomas dados. Doctor. Tesis, Universidad de California, Berkely, 1967.