Quiero saber la diferencia entre y .
http://en.wikipedia.org/wiki/List_of_logic_symbols
significa "demostrable". Pero se utiliza exactamente igual:
A B ¬B ¬A
A B ¬B ¬A¿Puede presentar un buen ejemplo en el que sean diferentes? ¿Es como el teorema de incompletitud de los conjuntos recursivos que hay oraciones que son verdaderas i.e. pero no tienen la propiedad i.e. demostrable?
Gracias por cualquier información
$A \models B$ significa que $B$ es verdadera en cada estructura en la que $A$ es cierto. $A\vdash B$ significa $B$ puede demostrarse utilizando $A$ como los locales. (En ambos casos, $A$ es un conjunto no necesariamente finito de fórmulas y $B$ es una fórmula).
La lógica de primer orden goza simultáneamente de las siguientes propiedades: Existe un sistema de prueba para el que
Este último punto contrasta con este hecho: no existe ningún algoritmo de comprobación de la demostrabilidad. Puedes buscar una prueba de una fórmula de primer orden de forma tan sistemática que la encontrarás si existe, y buscarás eternamente si no existe. Pero si llevas un millón de años buscando y todavía no ha aparecido, no sabes si la búsqueda será eterna o terminará la semana que viene. Estos son resultados demostrados en los años 30. La inexistencia de un algoritmo para decidir si una fórmula es demostrable se llama teorema de Church, en honor a Alonzo Church.
Aprendí que $\models$ representa la vinculación semántica, mientras que $\vdash$ representa la demostrabilidad en un determinado sistema de pruebas.
Más concretamente: Dado un conjunto de fórmulas $\Gamma$ y una fórmula $\varphi$ en alguna lógica (por ejemplo, la lógica de primer orden), $\Gamma \models \varphi$ significa que cada modelo de $\Gamma$ también es un modelo de $\varphi$ . Por otro lado, fijar un sistema de prueba (por ejemplo, el cálculo secuencial) para esa lógica. Entonces $\Gamma \vdash \varphi$ significa que existe una prueba utilizando ese sistema de prueba de $\varphi$ asumiendo las fórmulas de $\Gamma$ .
La relación entre $\models$ y $\vdash$ describe en realidad dos propiedades importantes de un cálculo de pruebas: Si $\Gamma \vdash \varphi$ implica $\Gamma \models \varphi$ el sistema de pruebas es sonido y si $\Gamma \models \varphi$ implica $\Gamma \vdash \varphi$ Es decir, es completa . En el caso de la lógica proposicional y de primer orden, existen sistemas de prueba que son sólidos y completos, pero no es el caso de otras lógicas. Por ejemplo, la lógica de segundo orden no admite un sistema de prueba eficaz, sólido y completo (por ejemplo, el conjunto de reglas de un sistema de prueba sólido y completo no sería decidible).
Editar: No todos los cálculos de prueba para la lógica proposicional o de primer orden son completos y sólidos. Por ejemplo, considere el sistema con la siguiente regla: $\vdash \varphi \vee \neg \varphi$ donde $\varphi$ es una fórmula arbitraria. Esto es indudablemente correcto, pero también es incompleto, ya que no se pueden derivar afirmaciones trivialmente verdaderas como $\varphi \vdash \varphi$ . Por otro lado, el sistema $\Gamma \vdash \varphi$ para fórmulas arbitrarias $\varphi$ y conjuntos de fórmulas $\Gamma$ es completa, pero obviamente incorrecta.
Michael Hardy y Johannes Kloos ya han respondido a esta cuestión, pero he pensado que un ejemplo típico podría aclarar el punto. $\def\ra{\rightarrow}$
Consideremos la lógica proposicional y digamos que $S$ es alguna fórmula de la lógica proposicional, quizás $p\ra(p\ra q)\ra q$ o $p\ra q$ . Podemos hacer una tabla de verdad de los valores de $S$ para cada valoración posible de sus variables. Si la tabla de verdad dice que $S$ es verdadera independientemente de los valores que asignemos a las variables, entonces diremos que $S$ es un tautología y escribir $\vDash S$ .
Consideremos ahora el siguiente sistema de axiomas: $$ X\ra (Y\ra X) \\ (X\ra(Y\ra Z))\ra((X\ra Y)\ra(X\ra Z)) $$
donde $X$ , $Y$ y $Z$ puede ser cualquier fórmula bien formada, y la regla de deducción del modus ponens, que dice que si podemos demostrar $X$ y podemos demostrar $X\ra Y$ , entonces podemos demostrar $Y$ .
Si podemos probar alguna frase $S$ a partir de estos axiomas y esta regla de deducción, diremos que $S$ es un teorema y escribir $\vdash S$ .
Este sería un uso típico de $\vdash$ y $\vDash$ .
Debe quedar claro que no es en absoluto evidente que $\vdash$ y $\vDash$ significan lo mismo; se definen de forma muy diferente. Tal vez pueda imaginarse tratando de demostrar que significan lo mismo.
De hecho, tal y como los he definido, lo hacen no significan lo mismo. Es el caso que $\vDash p\vee\lnot p$ pero no he dado ningún axioma que permita deducir $\vdash p\vee\lnot p$ . Todo teorema deducible tiene un $\ra$ en alguna parte.
O para poner un ejemplo menos tonto, resulta que $\vDash ((p\ra q)\ra p)\ra p$ pero no $\vdash ((p\ra q)\ra p)\ra p$ .
Así las cosas, tenemos $\vdash T$ implica $ \vDash T$ pero no necesariamente a la inversa. Si añadimos $(p\ra q)\ra p)\ra p$ al conjunto de los esquemas de los axiomas, y coinciden en que $\vDash T$ se aplica sólo a las fórmulas cuyo único operador es $\ra$ , entonces el sistema de axiomas se fortalece y hay menos tautologías, y $\vdash T$ y $ \vDash T$ se convierten en equivalentes.
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.
