Lógica

Conhecimentos de Base Recomendados

Cursos básicos de Análise, Álgebra, Programação.

Métodos de Ensino

O ensino é ministrado em sessões de caráter expositivo, com demonstrações pormenorizadas dadas no quadro. As aulas incluem exercícios e trabalhos de casa voluntários.

Resultados de Aprendizagem

Transmitir os métodos da Lógica Matemática moderna, nomeadamente a formalização de afirmações da linguagem corrente, no que diz respeito a afirmações matemáticas, e consequente formalização do raciocínio. As ambiguidades da linguagem informal levaram a uma cada vez maior introdução da simbologia. É um dos objetivos refletir estes desenvolvimentos na unidade curricular nas partes dedicadas à Lógica Proposicional e à Lógica dos Predicados. A terceira parte da disciplina é uma introdução a questões da teoria da computação.

Espera-se que o curso aumente as capacidades de formalização de afirmações e argumentos; aumente a capacidade de discernimento entre raciocínios falaciosos e corretos; clarifique os papéis histórico e técnico da lógica simbólica na matemática e na computação e transmita conhecimentos de sistemas dedutivos e máquinas de Turing.

Estágio(s)

Não

Programa

Lógica Proposicional (CP) 1. Alfabeto, fórmulas, valuações, tautologia, contradição; teoremas da substituição; associatividade de conectivos; FND; álgebras e funções booleanas 2. Aplicações: análise de argumentos, circuitos elétricos e lógicos 3. Simplificação de fórmulas; ligação com a complexidade algorítmica 4. Compacidade do CP 5. Sistemas formais de dedução; sistema formal (Hilbert) para o CP; Teoremas da dedução e completude. Lógica de Primeira Ordem (LPO) Alfabeto, termos, fórmulas atómicas e primas. Aplicações. Teoremas da LPO. Computabilidade, Decidibilidade, Enumerabilidade 1. Algoritmos e máquinas de Turing; computabilidade; computações completa e parcial 2. Funções computáveis. Teoremas da composição, recursão e operador mínimo; computabilidade de funções correntes; existência de funções não computáveis 3. Decidibilidade de relações i.p. de ordem e igualdade 4. Indecidibilidade do problema da paragem 5. Listabilidade. Conj. listáveis mas indecidíveis.

Docente(s) responsável(eis)

Alexander Kovacec

Métodos de Avaliação

Avaliação continua
Mini Testes: 30.0%
Frequência: 70.0%

Avaliação final
Mini Testes: 30.0%
Exame: 70.0%

Bibliografia

J. Malitz, Introduction to Mathematical Logic, Springer, 1978.

B. Margaris, First Order Logic, Dover, 1970.

E. Mendelsson, Introduction to Mathematical Logic, v. Nostrand, 1966.

A. Kovacec, Lógica (notas de curso), Departamento de Matemática da FCTUC, 2007.

A.J. Franco de Oliveira, Lógica e Aritmética, Gradiva, 2003.

P.J. Davis, R. Hersh, A Experiência Matemática, Gradiva, 1995.