Fundamentos De Logica E Teoria Da Computacao

O livro faculta uma introduo autossuficiente lgica matemtica e teoria da computabilidade para alunos de matemtica ou de cincia da computao. Est organizado em trs partes volta dos sucessos e fracassos do programa de Hilbert de formalizao da Matemtica. A Parte I aborda a questo da formalizao e a computabilidade. A Parte II apresenta a lgica de primeira ordem, incluindo o teorema da completude de Gdel e o teorema da coerncia de Gentzen. A Parte III est focada na aritmtica, na representabilidade de aplicaes computveis, nos teoremas da incompletude de Gdel e na decidibilidade da aritmtica de Presburger. A Parte IV inclui respostas detalhadas a exerccios selecionados. Um curso de graduao poder ser baseado nas duas primeiras partes, excluindo o clculo de Gentzen e terminando com uma panormica do caminho para o primeiro teorema da incompletude. Num curso mais avanado poder-se- suprimir o material introdutrio j do conhecimento dos alunos e estabelecer os resultados positivos e negativos do programa de Hilbert, abordando, desta forma, a demonstrao da coerncia proposta por Gentzen e a Parte III na ntegra. Esta segunda edio alargada tambm incorpora as correes e muitas revises pontuais do texto preparadas desde a sua publicao original.