Logica

Apostila de Lógica
Prof. Mário Benevides

[e-mail]
19 de Setembro de 2013
UFRJ

Motivação Prática
• Álgebra de Boole
• Programação em lógica (PROLOG)
• Sistemas especialistas
• Especificação de programas
• Verificação de programas
• Banco de dados:
BD’s dedutivos
Hipótese de mundo fechado
Default / prioridades
Ontologias
• Sistemas distribuídos:
Tempo
Conhecimento e crença
• Lei (Lógica deôntica)
• Linguagens de programação

Livros
• Lógica para a Computação - Thomson Learning - Flávio Soares Corrêa da
Silva, Marcelo Finger e Ana Cristina Vieira de Melo
• Lógica para a Ciência da Computação - Ed. Campus - João Nunes de Souza
• A Mathematical Introduction to Logic - Enderton
• Introduction to Mathematical Logic - Mendelson
• Introdução à Lógica Modal Aplicada a Computação - Marcos Mota Costa
• Programação em Lógica e a Linguagem PROLOG - Casanova
• Lógica - John Nolt e Linnes Rohatyn

Sumário

1 Introdução

1

2 Lógica Clássica Proposicional

5

2.1

Linguagem da Lógica Clássica Proposicional . . . . . . . . . . . . . .

6

2.2

Semântica da Lógica Clássica Proposicional . . . . . . . . . . . . . .

9

2.3

Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4

Sistemas Dedutivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.1

Dedução Natural . . . . . . . . . . . . . . . . . . . . . . . . . 26
Árvores de Prova . . . . . . . . . . . . . . . . . . . . . . . . . 37

2.4.2
2.4.3

Método de Resolução . . . . . . . . . . . . . . . . . . . . . . . 41

2.4.4

Provador de Dov Gabbay . . . . . . . . . . . . . . . . . . . . . 43

2.4.5

Sistema Axiomático . . . . . . . . . . . . . . . . . . . . . . . . 48

2.4.6
2.5

Método de Tableaux . . . . . . . . . . . . . . . . . . . . . . . 38

Relações entre Sintaxe e Semântica . . . . . . . . . . . . . . . 52

Aplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58