Logica

Universidade Federal da Bahia - UFBA
Instituto de Matemática - IM
Departamento de Matemática - DMAT
Colegiado do Curso de Matemática - COLMAT
Monografia de Graduação

Complexidade de raciocínio em Lógicas de
Descrições
Marlo Vieira dos Santos e Souza

Salvador
Julho de 2009

Complexidade de raciocínio em Lógicas de
Descrição
Marlo Vieira dos Santos e Souza

Monograa de Graduação apresentada ao
Colegiado do Curso de Graduação em Matemática da Universidade Federal da Bahia como requisito parcial para obtenção do título de Bacharel em Matemática.

Orientadora:
Santos.

Salvador
Julho de 2009

Prof. Dra . Débora Abdalla

Souza, Marlo Vieira dos Santos e.
Complexidade de raciocínio em Lógicas de Descrição / Marlo Vieira dos Santos e Souza.  Salvador, 2009.
33 f.
Orientadora: Prof. Dra . Débora Abdalla Santos.
Monograa (graduação)  Universidade Federal da Bahia, Instituto de
Matemática, Departamento de Matemática, 2009.
Referências bibliográcas.
1. Lógica matemática. 2. Teoria da complexidade. 3. Complexidade de dedução em sublinguagens de primeira ordem. I. Santos, Débora Abdalla. II. Universidade Federal da Bahia, Instituto de Matemática. III.
Título.

Complexidade de raciocínio em Lógicas de
Descrição
Marlo Vieira dos Santos e Souza
Monograa de Graduação apresentada ao Colegiado do Curso de Graduação em Matemática da Universidade Federal da Bahia como requisito parcial para obtenção do título de
Bacharel em Matemática.

Banca examinadora:

Prof. Dra . Débora Abdalla Santos (Orientadora).

Prof. Dr. Samuel Gomes da Silva.

Prof. Dr. Andreas Bernhard Michael Brunner

"Die Grenzen meiner Sprache bedeuten die Grenzen meiner Welt."
"Os limites da minha linguagem signicam os limites do meu mundo."
Ludwig Wittgenstein, 1921

Resumo
Este trabalho aborda a complexidade de provas de satisfazibilidade em algumas Lógicas de Descrição, medianamente expressivas, através do ferramental lógico da Teoria da