FenixEdu™

Disciplina

Fundamentos de Lógica e Teoria da Computação

Área

Área Científica de Lógica e Computação > Lógica e Computação

Activa nos planos curriculares

MMAC 2021 > MMAC 2021 > 2º Ciclo > Área Principal > Áreas de Especialização > Área de Especialização em Lógica e Computação > Área Científica de Lógica e Computação > Obrigatórias > Fundamentos de Lógica e Teoria da Computação

DEASegInf2007 > DEASegInf2007 > 3º Ciclo > Matemática > Lógica e Computação > Fundamentos de Lógica e Teoria da Computação

MMA 2006 > MMA 2006 > 2º Ciclo > Perfis > Matematica da Computação > Lógica e Computação > Fundamentos de Lógica e Teoria da Computação

MEIC-A 2006 > MEIC-A 2006 > 2º Ciclo > Área de Especialização Complementar > Teoria da Computação > Fundamentos de Lógica e Teoria da Computação

Nível

Exame final.

Tipo

Não Estruturante

Regime

Semestral

Carga Horária

1º Semestre

Aula Teórica (T): 4.0 h/semana

Trabalho Autónomo: 154.0 h/semestre

Créditos ECTS:

Objectivos

Dominar resultados e técnicas chave para estabelecer a decidibilidade de teorias de primeira ordem.

Programa

Breve revisão da lógica e teorias de primeira ordem. Cálculo de sequentes. Eliminação do corte. Coerência da lógica de primeira ordem por via simbólica. Analiticidade versus decidibilidade. Técnicas de eliminação de quantificadores. Decidibilidade da teoria das ordens lineares densas. Decidibilidade da aritmética de Presburger. Decidibilidade da teoria dos corpos algebricamente fechados. Decidibilidade da teoria de Tarski dos corpos reais fechados. Avanços recentes na algoritmia da teoria de Tarski. Caracterizações complementares da eliminação de quantificadores.