18 - Decidibilidade, Corretude, Completude, Consistência

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Clique para editar o estilo do título mestre
Clique para editar o estilo do subtítulo mestre
*
*
*
Lógica de Predicados
Decidibilidade, Corretude, 
Completude, Consistência 
*
*
*
Como avaliar sistemas de dedução??
Avaliação do algoritmo
Finitude
Complexidade
Avaliação da capacidade de inferência
Qualidade: Consistência
Eficiência: Completude
*
*
*
Avaliação do algoritmo de dedução
Análise de lógicas
Finitude = Decidibilidade
Tem a ver com teoria da computação
Computabilidade, Máquinas de Turing, funções recursivas, ...
Análise para métodos de dedução 
Correção
Completude 
Consistência
*
*
*
Computabilidade
Intuitivamente uma função é dita computável se é possível calcular seu valor, dado qualquer elemento do seu domínio
Será toda função, bem definida, computável?
NEM SEMPRE!!!
*
*
*
Decidibilidade
Caso particular de computabilidade quando a função só admite dois valores
É possível resolver um problema algoritmicamente (insolubilidade)?
Quando se fala se um problema é solúvel tem-se um problema de decidibilidade
Trata-se de saber se um algoritmo acaba
Devolvendo uma resposta, no nosso caso, T ou F
Há lógicas que são assim!!
*
*
*
Complexidade
Computabilidade diz respeito a se um problema pode ou não ser resolvido
Complexidade diz respeito à quantidade de recursos necessários para resolver um problema
Os recursos (normalmente) são:
Memória
Tempo
Porém... Complexidade não será analisada nesse curso 
*
*
*
E para sistemas de dedução?
Desejamos que nossos sistemas de dedução tenham certas propriedades...
Quais??
Relembrando conceitos
Tautologia
Teorema
Contradição
*
*
*
Avaliando sistemas de dedução
Queremos que o nosso sistema de dedução hipotético SD seja correto, completo e consistente
Que danado é isso???
*
*
*
Correto
Correto: 
Toda sentença deduzida por SD 
a partir de um dado conjunto de sentenças S
inclusive o conjunto vazio de sentenças!
Seja realmente dedutível a partir de S!
Se as premissas são válidas, a conclusão também é válida!
*
*
*
Completo e Consistente
Completo: 
Toda sentença realmente dedutível a partir de S, seja também dedutível através de SD
Consistente:
Não seja possível gerar contradições usando SD
*
*
*
Teorema da corretude
Um sistema de dedução SD é correto se satisfaz à condição abaixo
Todas as condições são a mesma no fundo 
Se H é conseqüência lógica de um conjunto de hipóteses b a partir de SD, H é realmente conseqüência lógica de b
Se b├SD H, então b├ H
SD só deduz fórmulas corretas!!
*
*
*
Teorema da correção (cont.)
Outra forma de dizer:
Se H é um teorema em SD (├SD H) 
então H é uma tautologia
Intuitivamente, se H é dedutível a partir de nenhuma sentença, 
H não depende de nenhuma interpretação para ser sempre verdadeira!
*
*
*
Teorema da completude
Um sistema de dedução SD é completo se satisfaz à condição abaixo
Todas as condições são a mesma no fundo 
Se H é conseqüência lógica de um conjunto de hipóteses b, H também é conseqüência lógica de b a partir de SD
Se b├ H, então b├SD H
Toda fórmula dedutível também é dedutível por SD!! 
*
*
*
Teorema da completude (cont.)
Outra forma de dizer:
Se H é uma tautologia
então H é um teorema em SD (├SD H) 
Intuitivamente, se H é sempre verdadeira, ela deve ser dedutível sem nenhuma premissa
H não depende de nenhuma interpretação de nenhuma sentença para ser sempre verdadeira!
*
*
*
Teorema da Consistência
Um sistema de dedução SD é consistente sse não é possível deduzir usando SD duas fórmulas que se contradizem
Não é possível ├SD H e ├SD H
*
*
*
Prova de Consistência
Se ├SD H, pelo teorema da correção 
H é tautologia D H é contraditória
Não é possível ├SD H, 
pois H seria uma tautologia
Não é possível que H e H sejam tautologias
*
*
*
Consistência e satisfatibilidade
Um conjunto de fórmulas b é consistente sse não existir uma fórmula H de forma a 
b├ H e b├ H
Não é possível deduzir H e H a partir de b
Teorema da Consistência e satisfatibilidade
Um conjunto de fórmulas é consistente 
sse for satisfatível
*
*
*
Demonstração em 2 passos 
Se um conjunto de fórmulas b é consistente então não existe uma fórmula H de forma a b├ H e b├ H
Se não existir uma fórmula H de forma a b├ H e b├ H então b é consistente
*
*
*
Demonstração do passo 1
Se b é consistente então não é possível
b├ H e b├ H
Se, por absurdo, b for insatisfatível
Não existe I que satisfaz b e 
I[H] = F e I[H] = F 
Pelos teoremas da correção e completude
b├ H e b├ H, que é uma contradição!
*
*
*
Demonstração do passo 2
Se b é satisfatível então 
existe I que satisfaz b 
Se, por absurdo, b for inconsistente 
Existe H tal que b├ H e b├ H
Pelo teorema da correção
H e H são conseqüências lógicas de b
Como I que satisfaz b, 
I[H] = I[H] = T, que é uma contradição!
*
*
*
Métodos vistos
Dedução natural
Tableaux semânticos
Resolução
Corretude, completude e consistência?
*
*
*
A Dedução natural é Correta
Se H é um teorema em DN (├DN H) 
então H é uma tautologia. Isto é verdade?
Para toda interpretação I, 
se I satisfaz b e b├ H, então I[H]=T
Logo, não existe I que satisfaz b e I[H]=F
Se b é vazio (teorema), 
I satisfaz H e I[H]=T para todo I
Então H é uma tautologia 
*
*
*
Dedução natural
Consistente
Não é possível introduzir “passos inválidos” numa prova por DN 
Completa
Regras de introdução e eliminação são completas para Lógica Proposicional
*
*
*
Métodos por refutação
Tableaux semânticos e Resolução
Corretos:
Se H é um teorema em DN (├T H) 
então H é uma tautologia. Isto é verdade?
O próprio método de prova foi feito para provar tautologias 
*
*
*
Métodos por refutação
Consistência depende de corretude
Ver prova em [Fitting 90]
Um conjunto arbitrário de fórmulas proposicionais S pode ser uma propriedade consistente proposicional sse
Não contiver contradições
Não for vazio ou infinito
 ...
Uma fórmula de S é satisfatível
Tableaux semânticos e expansões por resolução são propriedades consistentes proposicionais