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

Ano Lectivo: 1999/00

Programa:

1. Lógica Proposicional: Fórmulas bem formadas da LP, formalização e análise de afirmações, circuitos eléctricos, aplicações na linguagem PROLOG. Um sistema formal para a LP, Teorema da Dedução, Teoremas da completude e compacidade para o sistema formal mencionado.
2. Computabilidade: A "exactificação" da ideia do "algoritmo" pelas máquina de Turing. Funções computáveis. Relações decidíveis. Relações enumeráveis. A máquina universal. O problema da Paragem. Abordagem alternativa da computabilidade por funções recursivas. Aritmética e Relações aritméticas. As inclusões entre as classes de relações decidíveis, enumeráveis e aritméticas. O teorema de incompletude de Godel com esboço de prova.