52 votos

¿Cuál es la diferencia entre la Integridad y la Solidez en primer orden de la lógica?

La integridad se define como si se les da $\Sigma\models\Phi$$\Sigma\vdash\Phi$. Es decir, si para cada verdad de la colocación de $Z$ $\Sigma$ obtendríamos $T$, $\Phi$ también obtendría $T$. Si el anterior no existe, entonces podemos probar $\Phi$ usando las reglas en $\Sigma$.

La solvencia se define como: cuando se da ese $\Sigma\vdash\Phi$$\Sigma\models\Phi$, que es el opuesto.

¿Puede por favor explicar la diferencia básica entre los dos ?

Gracias ,Ron

91voto

Homer Puntos 198

En breve:

La solidez significa que usted no puede probar nada de lo que está mal.

Integridad significa que usted puede probar nada de lo que es correcto.

En ambos casos, estamos hablando de una fijos sistema de reglas para la prueba (la que se utiliza para definir la relación $\vdash$ ).

En más detalle: Creo que de $\Sigma$ como un conjunto de hipótesis, y $\Phi$ como una declaración de que estamos tratando de probar. Cuando decimos $\Sigma \models \Phi$, estamos diciendo que $\Sigma$ implica lógicamente $\Phi$, es decir, en cada circunstancia en la que $\Sigma$ es verdadera, entonces el $\Phi$ es cierto. De manera informal, $\Phi$ es "derecho" dado $\Sigma$.

Cuando decimos $\Sigma \vdash \Phi$, por otro lado, debemos tener algún conjunto de reglas de la prueba (a veces llamadas "reglas de inferencia") en la mente. Por lo general, estas reglas tienen la forma "si empiezas con algunas manifestaciones particulares, entonces usted puede obtener estas otras declaraciones". Si usted puede derivarse $\Phi$ a partir de $\Sigma$, entonces decimos que la $\Sigma \vdash \Phi$, o que $\Phi$ es demostrable a partir de $\Sigma$.

Estamos pensando en una prueba como algo que se usa para convencer a los demás, por lo que es importante que las reglas para $\vdash$ mecánica suficiente para que otra persona o un equipo puede comprobar un supuesto de prueba (esto es distinto a decir que la otra persona/equipo podría crear la prueba, lo que hacemos no requieren).

La solidez de los estados: $\Sigma \vdash \Phi$ implica $\Sigma \models \Phi$. Si usted puede probar $\Phi$$\Sigma$, $\Phi$ es cierto dado $\Sigma$. Dicho de otra manera, si $\Phi$ no es cierto (determinado $\Sigma$), entonces usted no puede probar su $\Phi$$\Sigma$. Informalmente: "no Se puede probar nada de lo que está mal."

La integridad de los estados: $\Sigma \models \Phi$ implica $\Sigma \vdash \Phi$. Si $\Phi$ es cierto dado $\Sigma$, entonces usted puede probar $\Phi$$\Sigma$. Informalmente: "Usted puede probar nada de lo que es correcto".

Idealmente, una prueba de sistema es sólido y completo.

11voto

Matt Dawdy Puntos 5479

Desde la perspectiva de tratar de escribir los axiomas de la lógica de primer orden que satisfacer tanto la integridad y solidez, solvencia es la dirección fácil: todo lo que tienes que hacer es asegurarse de que todos sus axiomas son verdaderos y que todas sus reglas de inferencia preservar la verdad. La integridad es el duro dirección: usted necesita para escribir lo suficientemente fuerte como axiomas para capturar la semántica de la verdad, y no es obvio desde el principio que esto es posible incluso en un no-trivial.

(Una forma trivial sería admitir todas las verdades como sus axiomas, pero el problema con este sistema lógico es que no se puede reconocer lo que cuenta como una prueba válida.)

8voto

Matty Puntos 1

Creo que esto sería mejor servir a los fines

http://www.cse.buffalo.edu/faculty/alphonce/.OldPages/CPSC312/CPSC312/Lecture/LectureHTML/CS312_7.html

Aplicación orientada a la respuesta

Permítanme en primer lugar caracterizar la solidez e integridad mediante un ejemplo tonto. Supongamos que usted está en el negocio de hacer máquinas que hacen los widgets, y supongamos que alguien viene y le dice: "necesito una máquina que hace de la red widgets que son ya sea redondo o cuadrado". Que ir y construir un widget de la producción de la máquina, y se la muestra a su cliente potencial. Para convertir a su potencial para un cliente real, debe convencerla de dos cosas: primero, que el widget de la máquina dejará de producir cuadrado o redondo rojo widgets, y no azul widgets, y segundo, que su máquina producirá rojos redondos y cuadrados de color rojo widgets, y no sólo de la plaza roja. Si su máquina cumple el primer requisito, es el sonido. Si la máquina cumple con el segundo requisito, entonces es completa. {Desde la misma página web se mencionó anteriormente}

3voto

bsamek Puntos 113

No puedo escribir comentarios, así que el post es una respuesta. Matt en su respuesta, los cambios de significado de "completar", aunque dijo que el grupo de teoría es incompleta. El OP le preguntó acerca de integridad semántica, Matt escribe acerca de la negación integridad, que es:

Una teoría de la $T$ es la negación completa de la fib para cada fórmula $A$$T$, $T\vdash A$ o $T\vdash\neg A$.

Como tal, el grupo de teoría es, de hecho, no completa (ver Matt ejemplo). Pero todavía es semánticamente completa, que es lo que hay de verdadero en cada grupo (en cada una de las estructuras que es un modelo de grupo de axiomas) es demostrable a partir de los axiomas de grupo.

0voto

Rudy the Reindeer Puntos 20855

Usted puede tener una teoría de la $T$ que es el sonido, pero incompleta. Como un ejemplo, considere el grupo de teoría donde $T$ son las tres propiedades de los grupos. A continuación, usted no puede probar o refutar $\forall x,y: xy = yx$ ya que no todos los grupos son abelian pero algunos son.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X