Licenciatura: Matemática (Ramo Científico – Especialização em Computação)

Ano Lectivo: 2002/03

Programa:

1. Lógica Proposicional tradicional com aplicações à análise de argumentos e circuítos eléctricos.
2. Tradução de problemas combinatórios para o Cálculo proposicional; relevância no estudo de problemas NP - completos.
3. Exemplos da sua aplicação do Teorema da compacidade.
4. Sistemas formais para o cálculo proposicional. Teoremas da dedução e Completude.
5. Máquinas de Turing. Funções computáveis.
6. Decidibilidade.
7. Problema da Paragem – um exemplo algoritmicamente indecidível.
8. A máquina universal de Turing.
9. Conjuntos e relações enumeráveis.
10. Caracterização da decidibilidade em termos da enumerabilidade; comportamento de decidibilidade e enumerabilidade sob quantificações.
11. Aritmética. Funções computáveis e relações enumeráveis são aritméticos.
12. Sistemas formais da aritmética.
13. Significado e demonstração do teorema da incompletude de Gödel.
14. O teorema de Tarski da não - aritmeticidade da validade de asserções.