domingo, 11 de julho de 2010

Estrutura Geral da Prova de Completude Lógica

Provar que  # |= A --> # |- A

1. Assuma # |= A
2. # U {~A} não tem modelo
3. @ é consistente --> @ tem modelo
4. @ não tem modelo --> @ é inconsistente
5. # U {~A} é inconsistente
6. # U {~A}|- Falso
7. # |- A

.................................................... 

Lema de Linderbaum [seja @ consistente, então existe um @' maximal consistente, tal que @ está contido em @']
1. @ é consistente
2. @ pode ser extendido a um @' max cons
3. @ está contido em @'
4. Existe um modelo para @'
5. Existe um modelo para @

....................................................

# é maximal consistente sse:

(1) # é consistente; e
(2) Para todo A não pertencente a #, # U {A} |- Falso; e
(3) Para todo A: A pertence a # ou A não pertence a #; e
(4) Para todo A: A pertence a # sse # |- A; e
(5) Para todo A: A pertence a # sse ~A não pertence a #; e
(6) Para todo A e B: A&B pertence a # sse A pertence a # e B pertence a #

....................................................

# é inconsistente sse:

(1) # |- Falso
(2) Existe A: # |- A e # |- ~A
(3) Para todo A: # |- A

.................................................... 

# é completo sse:

(1) # |= A --> # |- A