È la risoluzione completa o solo confutazione-complete?

Question

alcuni tutorial di rappresentazione della conoscenza sulla risoluzione in questo momento, e mi sono imbattuto in < a href = "http://www.cs.toronto.edu/~sheila/384/w11/Lectures/csc384w11-Lecture-05-KR.pdf"> scivolo 05.KR, no77 .

Non si è detto che "la procedura è inoltre completa".

Credo che questa completezza non può significare che se una frase è comportato da KB, allora sarà il risultato di risoluzione. Ad esempio, la risoluzione non può derivare $ (q \ lor \ neg q) $ da KB con singola clausola $ \ neg p $. (Esempio da KRR, Brachman e Levesque, pagina 53).

Qualcuno potrebbe aiutarmi a capire cosa si intende in questa diapositiva? È la completezza della presentazione si riferiscono a essere refutaton-completi e non una procedura di prova completa?

Answer 1

La risoluzione è completo come un sistema di confutazione. Cioè, se $ S $ è un insieme contraddittorio di clausole, allora risoluzione può confutare $ S $, vale a dire $ S \ vdash \ bot $.

Questo è sufficiente dal momento che $ T \ vdash A $ è equivalente a tazza $ T \ \ {\ lnot A \} \ vdash \ bot $. Quindi, se vogliamo vedere una formula $ A $ è derivabile da $ T $, abbiamo solo bisogno di controllare se c'è una prova confutazione a $ T \ tazza \ {\ lnot A \} $ che può essere controllato tramite risoluzione.

Answer 2

La risoluzione è solo refutationally completa, come lei ha ricordato. Si tratta di destinato e molto utile, perché riduce drasticamente lo spazio di ricerca. Invece di dover eventualmente derivare ogni possibile conseguenza (per trovare una prova di qualche congettura), la risoluzione è solo cercando di ricavare la clausola vuota.

Answer 3

E 'anche implicationally completo nel senso seguente:

Se una serie di clausole di $ F $ comporta una clausola di non tautologico $ C $, allora è sempre possibile ricavare una singola clausola di $ C '$ che sussume $ C $ (Vale a dire $ C' \ subseteq C $).

Fonte:
Christian G. Fermüller, implicazionale Completezza delle Firmato Risoluzione 2002

Si noti che il risultato originale si riferisce a:
R.C.T. Lee. Un teorema di completezza e di un programma per computer per nding teoremi derivabile da trovati assiomi . Ph.D. Tesi, Università della California, Berkeley, 1967.