Definiciones y Teoremas varios (Lógica y Computabilidad)

Correctitud

$\Gamma \vdash \phi \Rightarrow \Gamma \models \phi$

Completitud

$\Gamma \models \phi \Rightarrow \Gamma \vdash \phi$

Consistencia

$\Gamma$ es consistente sii no existe una fórmula $\phi$ tal que $\Gamma \vdash \phi \wedge \Gamma \vdash \neg \phi$

Satisfacible

• En proposicional $\Gamma$ es satisfacible sii existe una interpretación $v$ tal que ${\tilde {v}}(\psi )=1$ para toda $\psi \in \Gamma$, o sea, ${\tilde {v}}(\Gamma )=1$.
• En primer orden $\Gamma$ es satisfacible si existe una L-estructura y una valuación v de A tal que $A\models \Gamma [v]$, o sea, $A\models \psi [v]$ para toda $\psi \in \Gamma$.

Consecuencia semántica $\Gamma \models \phi$

• En proposicional $\phi$ es consecuencia semántica de $\Gamma$ si para toda interpretación v, si $v(\Gamma )=1$ entonces $v(\phi )=1$.
• En primer orden $\phi$ es consecuencia semántica de $\Gamma$ si para toda L-estructura A, si $A\models \Gamma [v]$ entonces $A\models \phi [v]$.

Consecuencia sintáctica $\Gamma \vdash \phi$

$\phi$ es consecuencia sintáctica de $\Gamma$ si existe una cadena finita no vacía $\phi _{1},\ldots ,\phi _{n}$ de formulas de P tal que $\phi _{n}=\phi$ y para todo $\phi _{i}$,

• $\phi _{i}$ es un axioma o
• $\phi _{i}\in \Gamma$ o
• $\phi _{i}$ se desprende de $\phi _{k},\phi _{l},k,l<i$ mediante una regla de inferencia (Modus Ponens)

Teorema de la deducción

$\Gamma \cup \{\phi \}\vdash \psi \Longleftrightarrow \Gamma \vdash \phi \rightarrow \psi$

Conjunto maximal consistente

$\Gamma$ conjunto de formulas es maximal consistente en SP o SQ si es consistente y para toda fórmula $\phi$, $\phi$ pertenece a $\Gamma$ o al agregar $\phi$ a $\Gamma$ este se vuelve inconsistente.

Lema de Lindenbaum

Si $\Gamma$ es consistente, entonces existe un conjunto maximal consistente que lo incluye.