Logica

Disponível somente no TrabalhosFeitos
  • Páginas : 34 (8275 palavras )
  • Download(s) : 0
  • Publicado : 14 de janeiro de 2013
Ler documento completo
Amostra do texto
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 deGraduaçã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.
33f.
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 daSilva.

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 daComplexidade. Tal estudo relaciona a capacidade expressiva de uma Lógica de Descrição
com a complexidade inerente de raciocínio neste formalismo.

Palavras-chave:
mático.

Lógica de Descrições; Complexidade Computacional; Raciocínio Auto-

Abstract
The present work addresses the complexity of reasoning about satisfatibilty in some
(fairly expressive) Description Logics through the logicalframework of Complexity Theory.
Such study relates the expressive power of such an Description Logic with the ineherent
complexity of reasoning in this formalism.

Keywords:

Description Logics; Computational Complexity; Automatic Reasoning.

Sumário
Introdução

1

1 Preliminares

3

1.1

Teoria da complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31.1.1

Máquinas de Turing

..........................

3

1.1.2

Complexidade no tempo . . . . . . . . . . . . . . . . . . . . . . . .

4

1.1.3

Complexidade no espaço . . . . . . . . . . . . . . . . . . . . . . . .

6

1.1.4

Complemento, reduções e completude . . . . . . . . . . . . . . . . .

7

2 Lógica de 1a ordem

8

2.1

Sintaxe e Semântica . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .

2.2

Decidibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1

2.3

8

Fragmentos decidíveis da LPO . . . . . . . . . . . . . . . . . . . . . 13

Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3 Lógicas de descrições

15

3.1

Sintaxe . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . 15

3.2

Semântica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.3

DL como sublinguagem de primeira ordem . . . . . . . . . . . . . . . . . . 18

3.4

Raciocínio em DL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Complexidade de raciocínio em DL
4.1

24

Resultados...
tracking img