Lógica matemática

UNIVERSIDADE FEDERAL DE SANTA CATARINA ~ ^ PROGRAMA DE POS-GRADUACAO EM CIENCIA DA ~ COMPUTACAO

Fundamentos de Matematica Aplicada a Informatica
PROF. JORGE MUNIZ BARRETO PROF. MAURO ROISENBERG PROFa. MARIA APARECIDA FERNANDES ALMEIDA PROFa. KATIA COLLAZOS

FLORIANOPOLIS, 1998

Sumario
Sumario Lista de Figuras Lista de Tabelas 1 Historia da Matematica e da Computac~o a
1.1 1.2 1.3 1.4 1.5 1.6 1.7 Introduc~o . . . . . . . . . a As Origens . . . . . . . . . A Matematica na Grecia . Os Tempos de Escurid~o . a O Renascimento . . . . . . Os Tempos Modernos . . . A Era dos Computadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iv v 1 2
2 3 5 6 6 7 9

2 Logica

2.1 Notas Historicas . . . . . . . . . . . . . . . . . . . . 2.2 Logica de Primeira Ordem . . . . . . . . . . . . . . 2.3 Calculo Proposicional . . . . . . . . . . . . . . . . . 2.3.1 Sintaxe do Calculo Proposicional . . . . . . a 2.3.2 Sem^ntica do Calculo Proposicional . . . . . 2.3.3 Tabelas-Verdade . . . . . . . . . . . . . . . 2.3.4 Tautologia . . . . . . . . . . . . . . . . . . . 2.3.5 Formula Inconsistente ou Contradic~o . . . a 2.3.6 Equival^ncia de Formulas . . . . . . . . . . e 2.3.7 Regras de Infer^ncia . . . . . . . . . . . . . e 2.3.8 Tabelas-Verdade como Forma de Validac~o . a 2.4 Calculo de Predicados . . . . . . . . . . . . . . . . 2.4.1 Algumas De nic~es . . . . . . . . . . . . . . o i

12
12 14 14 15 16 16 18 18 19 20 27 28 28