procedimento de prova - Proof procedure
Na lógica , e em particular teoria da prova , um procedimento de prova para uma determinada lógica é um método sistemático para a produção de provas em algum cálculo prova de declarações (comprovados).
Tipos de cálculos prova usado
Existem vários tipos de cálculos prova. Os mais populares são dedução natural , cálculos sequent (ou seja, Gentzen sistemas do tipo), sistemas de Hilbert , e tableaux semântica ou árvores. Um determinado procedimento prova terá como alvo um cálculo prova específica, mas muitas vezes pode ser reformulado de modo a produzir provas em outros estilos de prova.
plenitude
Um procedimento de prova para uma lógica é completa se produzir uma prova para cada instrução provável. Os teoremas de sistemas lógicos são tipicamente recursivamente enumeráveis , o que implica a existência de um procedimento de prova completa, mas extremamente ineficiente; no entanto, um procedimento de prova é apenas de interesse se for razoavelmente eficiente.
Confrontados com uma afirmação improvável, um procedimento de prova completa pode às vezes ter sucesso na detecção e sinalização de sua indemonstrabilidade. No caso geral, onde provabilidade é um semidecidível propriedades, isto não é possível, e em vez disso o processo se desviará (não terminar).
Veja também
Referências
- W. Quine de 1982 (1950). Métodos de Logic . Harvard Univ. Pressione.