Definiciones y Teoremas varios (Lógica y Computabilidad)

De Cuba-Wiki

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.