¿Es la resolución proposicional un sistema de prueba completo?

Esta pregunta trata sobre la lógica proposicional y todos los casos de "resolución" deben leerse como "resolución proposicional".

Esta pregunta es algo extremadamente básico, pero me ha estado molestando por un tiempo. Veo personas afirmar que la resolución proposicional está completa, pero también veo personas afirmar que la resolución es incompleta. Entiendo el sentido en que la resolución es incompleta. También veo por qué las personas pueden afirmar que está completo, pero la palabra "completo" difiere de la forma en que se usa "completo" al describir la deducción natural o el cálculo posterior. Incluso el calificador "refutación completa" no ayuda porque las fórmulas tienen que estar en CNF y la transformación de una fórmula en una fórmula CNF equivalente o fórmula CNF no satisfactoria a través de la transformación Tseitin no se tiene en cuenta dentro del sistema de prueba.

Solidez e integridad

Supongamos la configuración de la lógica proposicional clásica con una relación entre algún universo de estructuras y un conjunto de fórmulas y la noción tarskiana clásica de verdad en una estructura. Escribimos si es verdadero en todas las estructuras consideradas. También asumiré un sistema para derivar fórmulas de fórmulas. $\models$ $\models \varphi$ $\varphi$ $\vdash$

El sistema es sólido con respecto a si cada vez que tenemos , también tenemos . El sistema está completo con respecto a si cada vez que tenemos , también tenemos . $\vdash$ $\models$ $\vdash \varphi$ $\models \varphi$ $\vdash$ $\models$ $\models \varphi$ $\vdash \varphi$

La regla de resolución

Un literal es una proposición atómica o su negación. Una cláusula es una disyunción de literales. Una fórmula en CNF es una conjunción de cláusulas. La regla de resolución afirma que

La regla de resolución afirma que si la conjunción de la cláusula con la cláusula es satisfactoria, la cláusula también debe ser satisfactoria. $C \lor p$ $\neg p \lor D$ $C \lor D$

No estoy seguro de si la regla de resolución sola puede entenderse como un sistema de prueba porque no hay reglas para la introducción de fórmulas. Supongo que al menos necesitamos una regla de hipótesis que permita la introducción de cláusulas.

Falta de resolución

Se sabe que la resolución es un sistema a prueba de sonido. Es decir, si podemos derivar una cláusula a partir de una fórmula usando resolución entonces . La resolución también es un significado completo de refutación si tenemos entonces podemos derivar de usando la resolución. $C$ $F$ $\models F \implies C$ $\models F \implies \bot$ $\bot$ $F$

Considera la fórmula

$\varphi := p \land q$ y . $\psi := p \lor q$

En el sistema LK de Gentzen o usando la deducción natural, puedo derivar la implicación completamente dentro del sistema de prueba. No puedo derivar esta implicación usando la resolución porque si comienzo con , no hay solventes. $\varphi \implies \psi$ $\varphi$

Veo cómo puedo probar la validez de esta implicación usando la resolución:

Considere la fórmula $\neg (\varphi \implies \psi)$
Convierta la fórmula anterior en CNF usando reglas de distributividad estándar o usando la transformación Tseitin
Derive de la fórmula transformada usando resolución. $\bot$

Este enfoque no me satisface porque requiere que realice los pasos (1) y (2) que están fuera del sistema de prueba de resolución. Por lo tanto, parece que hay un sentido muy claro en el que la resolución no está completa de la forma en que decimos que la deducción natural o los cálculos posteriores están completos.

Preguntas

Dado todo lo anterior, mis preguntas son:

¿Qué sistema de prueba se está considerando al discutir la resolución? ¿Es solo la regla de resolución? ¿Cuáles son las otras reglas?
Me parece muy claro que la resolución no está completa en el sentido de que la deducción natural y los cálculos posteriores están completos. ¿La literatura que afirma que la resolución es terminología de abuso completa solo porque el sentido en que se completa la resolución es más interesante que el sentido en que está incompleto?
¿Esta diferencia en las nociones de integridad aplicadas a la resolución y en otros lugares y cómo reconciliarlas se ha discutido con mayor profundidad en la literatura?
También me doy cuenta de que la resolución se puede formular dentro de los cálculos posteriores en términos de la regla de corte. ¿Es la visión teórica "correcta" de la resolución de la prueba solo que es un fragmento del cálculo consecuente que es suficiente para verificar la satisfacción de las fórmulas en CNF?

lo.logic terminology proof-complexity proof-theory resolution Vijay D
fuente

(1) fórmulas CNF con resolución justa (o, si hace QBF, entonces fórmulas QCNF con resolución y reducción total); (2) Sí, es una refutación completa, y aún tiene un significado ligeramente diferente, es decir, si

entonces

ψ ⊨ ⊥

$\psi\models\bot$

ψ ⊢ ⊥

$\psi\vdash\bot$

Radu GRIGore

pregunta más o menos similar aquí. Gracias por publicar. Básicamente, iiuc / afaik, la resolución se usa para sistemas mucho más que la lógica de primer orden, pero dentro de la lógica de primer orden es "sólida / completa", aunque eso no siempre se describe muy bien, porque a menudo solo se usa para pruebas de refutación. en los sistemas "más grandes", donde los términos no son meramente variables booleanas sino, por ejemplo, calificadores existenciales, etc., no están completos. el campo de la lógica no estandariza sus definiciones de terminología demasiado bien, hay mucha "sobrecarga" de términos, etc ...

vzn

Es por eso que algunas personas dicen que está " refutacionalmente completo", por ejemplo, L. Bachmair y H. Ganzinger, "Prueba de resolución del teorema", Manual de razonamiento automatizado, vol. 1, págs. 19–99, 2001.

Trylks

La pregunta discute la integridad refutacional.

Vijay D

Respuestas:

¿Qué sistema de prueba se está considerando al discutir la resolución? ¿Es solo la regla de resolución? ¿Cuáles son las otras reglas?

Discuto la resolución en el contexto de las "cláusulas", que son secuencias posteriores formadas únicamente por literales . Una cláusula clásica se vería como Pero también podemos escribirla como

{UN}_{1}, ..., {UN}_{norte} \to {si}_{1}, ..., {si}_{metro}

$A_1,\ldots,A_n \to B_1,\ldots,B_m$

funcionan con solo secuenciantes unilaterales. Es convencional tratar estas secuencias unilaterales comomultisetsde literales.

\to {\bar{UN}}_{1}, ..., {\bar{UN}}_{norte}, {si}_{1}, ..., {si}_{metro}

${} \to \bar{A}_1,\ldots,\bar{A}_n, B_1, \ldots, B_m$

LK restringido a cláusulas tiene solo cuatro reglas de inferencia:

identidad
corte (resolución proposicional)
contracción (factoring proposicional)
debilitamiento

Es obvio que estas cuatro reglas están completas para deducir cláusulas, es decir,

Proposición 1 $C$ ${\cal S}$ ${\cal S} \models C$ ${\cal S} \vdash C$

La prueba de refutación convierte el problema de en , donde ${\cal S} \vdash C$ ${\cal S} \cup N(C) \vdash \bot$ $N(C) = \{\{\bar{A}\} \mid A \in C\}$ $C$

${\cal S} \vdash C$ ${\cal S} \cup N(C) \vdash \bot$

Proposición 2 Para cualquier cláusula y conjunto de cláusulas $C$ ${\cal S}$ ${\cal S} \models C$ ${\cal S} \cup N(C) \vdash \bot$

El punto de convertir el problema en pruebas de refutación es doble:

$N(C)$
Tenemos un control de la lógica de predicados completa, cuyas fórmulas se pueden transformar a CNF hasta la satisfacción.

¿Es la visión teórica "correcta" de la resolución de la prueba solo que es un fragmento del cálculo consecuente que es suficiente para verificar la satisfacción de las fórmulas en CNF?

¡En efecto!

Uday Reddy
fuente

Gracias Uday Una pregunta: la regla de corte aún mantiene las cláusulas de la fórmula original en el consecuente. En resolución, estos se "optimizan" con una sola cláusula en el consecuente. ¿Estaría de acuerdo en que esa resolución es una regla mínima o local debido a que todas las cláusulas no aparecen en la regla?

Vijay D

@VijayD. Estamos utilizando precisamente la regla de corte, pero de manera diferente a Gentzen. Gentzen pruebas serían de la forma

⊢ C

${} \vdash C$

S ⊢ C

${\cal S} \vdash C$

¿podría agregar a su respuesta lo que cree que es una descripción precisa de una oración de la integridad de la resolución?

Vijay D

@VijayD. Había dos declaraciones de "si y solo si" en mi respuesta original, que eran las dos propiedades de integridad. Para mayor claridad, los he destacado como Propuestas para usted. (Todavía no estoy seguro de dónde reside su confusión. ¿Quizás tenga que ver con el idioma con el que estamos trabajando, como Kaveh ha implicado?)

Uday Reddy

@VijayD. No creo que pueda decir que la resolución es "incompleta". Todo lo que ha dicho en su pregunta original fue que las transformaciones necesarias para poner las fórmulas proposicionales en forma clausal son "insatisfactorias" para usted. Eso no significa que estén "incompletos".

Uday Reddy

1)

La única regla no estructural es la resolución (en los átomos).

\frac{φ \lor C, ψ \lor \bar{C}}{φ \lor ψ}

$\varphi\lor C, \psi\lor \overline{C} \over \varphi\lor \psi$

Sin embargo, una regla por sí sola no da un sistema de prueba. Ver parte 3.

2)

$\{\land, \lor, \lnot\}$ $\{\land, \lor, \lnot\}$

Mientras haya una traducción "agradable" de un idioma a otro, podemos hablar de integridad. Lo que importa esencialmente es que podemos traducir fórmulas de una a la otra y viceversa de manera eficiente. Puede consultar la tesis de Robert Reckhow donde trata el tema de la conectividad y muestra que para los sistemas Frege la longitud de las pruebas no cambia más que un polinomio, por lo que está bien, en cierto sentido, elegir cualquier conjunto de conectivos adecuados que desee.

La situación para la resolución es similar. Al reducir de SAT a 3SAT podemos restringir nuestra atención a los CNF y la transformación se puede hacer de manera muy eficiente.

Tenga en cuenta que la resolución no está sola aquí, el problema se aplica también a otros sistemas de prueba. Tomemos, por ejemplo, Frege de profundidad limitada donde la profundidad de las fórmulas debe estar limitada por una constante, por lo que, por definición, no puede probar ninguna familia de fórmulas de profundidad ilimitada.

3)

$P$ $\vdash_P$

$\vdash_P$ $\varphi$ $\pi$ $\pi$ $P$ $\varphi$
$P$ $\varphi$ $\varphi$ es cierto.
$\varphi$ $P$ $\varphi$

La definición es muy general y no habla sobre la estructura de la prueba en absoluto. Cualquier cosa que satisfaga estas condiciones es un sistema de prueba proposicional.

¿Qué clase de fórmula deberíamos considerar en estos ítems? Se han considerado diferentes clases de fórmulas y el primer tratamiento del problema que conozco es la tesis de Robert Reckhow, donde muestra que, siempre que uno se preocupe por los sistemas Frege, no importa qué conjunto adecuado de conectivos se use, todos ellos son equivalentes

Con respecto a la resolución, si uno realmente quiere tener integridad con respecto a todas las fórmulas y no solo a los CNF, puede incorporar una traducción de tiempo polinómico fijo de fórmulas arbitrarias a CNF en el sistema de prueba sin ningún problema, ya que la traducción es computable en tiempo polinomial.

$\pi$ $\bot$ $\lnot \varphi$

4)

La resolución está bien como está, sin embargo, también se puede pensar de la manera que mencionó, es decir, por supuesto, podemos pensar en ella como la regla de corte cuando la fórmula de corte es un átomo positivo al mover los átomos negativos al antecedente y mantener el los positivos en el siguiente:

\frac{\Rightarrow φ, C C \Rightarrow ψ}{\Rightarrow φ, ψ}

$\Rightarrow \varphi, C \hspace{1cm} C \Rightarrow \psi \over \Rightarrow \varphi, \psi$

$G$

ps: mi respuesta es principalmente desde la perspectiva teórica de la complejidad de la prueba. Es posible que desee comprobar otras perspectivas, como la teoría de la prueba estructural .

Referencias

Robert A. Reckhow, " Sobre las longitudes de las pruebas en el cálculo proposicional ", 1976.

Kaveh
fuente

Gracias por tu respuesta. Veo cómo Uday dice cosas similares, pero descubrí que podía seguir su respuesta más fácilmente.

Vijay D

@VijayD, claro, no hay problema. :)

Kaveh