Diferencia entre revisiones de «Definiciones y Teoremas varios (Lógica y Computabilidad)»

De Cuba-Wiki
m (Arregla gramática)
 
m (formulas -> fórmulas)
 
Línea 18: Línea 18:


; Consecuencia sintáctica <math>\Gamma \vdash \phi</math>
; Consecuencia sintáctica <math>\Gamma \vdash \phi</math>
: <math>\phi</math> es consecuencia sintáctica de <math>\Gamma</math> si existe una cadena finita no vacía <math>\phi _1, \ldots, \phi _n</math> de formulas de P tal que <math>\phi _n = \phi</math> y para todo <math>\phi _i</math>,  
: <math>\phi</math> es consecuencia sintáctica de <math>\Gamma</math> si existe una cadena finita no vacía <math>\phi _1, \ldots, \phi _n</math> de fórmulas de P tal que <math>\phi _n = \phi</math> y para todo <math>\phi _i</math>,  
:* <math>\phi _i</math> es un axioma o
:* <math>\phi _i</math> es un axioma o
:* <math>\phi _i \in \Gamma</math> o
:* <math>\phi _i \in \Gamma</math> o
Línea 27: Línea 27:


; Conjunto maximal consistente
; Conjunto maximal consistente
: <math>\Gamma</math> conjunto de formulas es maximal consistente en SP o SQ si es consistente y para toda fórmula <math>\phi</math>, <math>\phi</math> pertenece a <math>\Gamma</math> o al agregar <math>\phi</math> a <math>\Gamma</math> este se vuelve inconsistente.
: <math>\Gamma</math> conjunto de fórmulas es maximal consistente en SP o SQ si es consistente y para toda fórmula <math>\phi</math>, <math>\phi</math> pertenece a <math>\Gamma</math> o al agregar <math>\phi</math> a <math>\Gamma</math> este se vuelve inconsistente.


; Lema de Lindenbaum
; Lema de Lindenbaum

Revisión actual - 02:31 16 nov 2017

Plantilla:Back

Correctitud
Completitud
Consistencia
es consistente sii no existe una fórmula tal que
Satisfacible
  • En proposicional es satisfacible sii existe una interpretación tal que para toda , o sea, .
  • En primer orden es satisfacible si existe una L-estructura y una valuación v de A tal que , o sea, para toda .
Consecuencia semántica
  • En proposicional es consecuencia semántica de si para toda interpretación v, si entonces .
  • En primer orden es consecuencia semántica de si para toda L-estructura A, si entonces .
Consecuencia sintáctica
es consecuencia sintáctica de si existe una cadena finita no vacía de fórmulas de P tal que y para todo ,
  • es un axioma o
  • o
  • se desprende de mediante una regla de inferencia (Modus Ponens)
Teorema de la deducción
Conjunto maximal consistente
conjunto de fórmulas es maximal consistente en SP o SQ si es consistente y para toda fórmula , pertenece a o al agregar a este se vuelve inconsistente.
Lema de Lindenbaum
Si es consistente, entonces existe un conjunto maximal consistente que lo incluye.