Satisfacible | Un conjunto Γ es SATISFACIBLE si existe v val tal que v satisface a Γ
v val SATISFACE a Γ si v(α)=1 ∀α∈Γ
v val satisface a α si v(α)=1 |
Insatisfacible | Un conjunto Γ es insatisfacible si no existe ninguna v val tal que v satisfaga a Γ |
Consecuencia | α es consecuencia de Γ si:
∀v val que satisface a Γ ---> v(α)=1 |
Finitamente satisfacible | Γ es f.s. si para cada conjunto finito Γ'⊆Γ, Γ' es satisfacible |
Axiomas | 1) ( α -> ( β -> α ))
2) (( α -> ( β -> γ )) -> (( α -> β ) -> ( α -> γ )))
3) (( ¬α -> ¬β ) -> (( ¬α -> β ) -> α )) |
Prueba | Una prueba de α es una sucesión de fórmulas α1,...,αn con:
- α = αn
- αi tiene dos opciones:
1) es una instancia de axioma
2) existen αj, αk con j,k<i tal que αj = αk->αi. Entonces αi se obtiene por Modus Ponens de αj y αk |
Demostrable | α es demostrable si existe una prueba de α |
Prueba a partir de Γ (Γ⊢α) | α se prueba a partir de Γ si existe una prueba α1,...,αn tal que:
- α = αn
- αi tiene dos opciones:
1) αi es una instancia de axioma
2) αi ∈ Γ
3) αi se obtiene por MP de αj, αk con j,k<i |
Inconsistente | Un conjunto Γ es inconsistente si existe φ tal que Γ⊢φ y Γ⊢¬φ |
Consistente | Un conjunto Γ es consistente si no es inconsistente |
Maximal consistente | Γ es m.c. si:
- Γ es consistente
- ∀φ∈Form: φ∈Γ ó {φ}uΓ es inconsistente |
Independiente | Γ es independiente si ∀α∈Γ, α∉C(Γ-{α}) |
Dependiente | Γ es dependiente si ∃α∈Γ tal que α∈C(Γ-{α}) |
Base | Γ es base si y solo si:
1) Γ es independiente
2) Si ∃Σ conjunto independiente tal que Σ⊆Γ ---> Σ = Γ |