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

De Cuba-Wiki
m (Arregla gramática)
(Sin diferencias)

Revisión del 02:29 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 formulas 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 formulas 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.