Edición de «Definiciones y Teoremas varios (Lógica y Computabilidad)»

{{Back|Lógica y Computabilidad}}
; Correctitud
: <math>\Gamma \vdash \phi \Rightarrow \Gamma \models \phi </math>

; Completitud 
: <math>\Gamma \models \phi \Rightarrow \Gamma \vdash \phi </math>

; Consistencia
: <math>\Gamma</math> es consistente sii no existe una fórmula <math>\phi</math> tal que <math>\Gamma \vdash \phi \wedge \Gamma \vdash \neg \phi</math>

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

; Consecuencia semántica <math>\Gamma \models \phi</math>
* En proposicional <math>\phi</math> es consecuencia semántica de <math>\Gamma</math> si para toda interpretación v, si <math>v( \Gamma ) = 1</math> entonces <math>v( \phi ) = 1</math>.
* En primer orden <math>\phi</math> es consecuencia semántica de <math>\Gamma</math> si para toda L-estructura A, si <math>A \models \Gamma [v]</math> entonces <math>A \models \phi [v]</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 _i</math> es un axioma o
:* <math>\phi _i \in \Gamma</math> o
:* <math>\phi _i</math> se desprende de <math>\phi _k, \phi _l, k,l < i</math> mediante una regla de inferencia (Modus Ponens)

; Teorema de la deducción
: <math>\Gamma \cup \{\phi \} \vdash \psi \Longleftrightarrow \Gamma \vdash \phi \rightarrow \psi</math>

; 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.

; Lema de Lindenbaum
: Si <math>\Gamma</math> es consistente, entonces existe un conjunto maximal consistente que lo incluye.

[[Category:Apuntes]]