3
44350 palavras
178 páginas
12
Logica para a Ci^encia da Computac~ao
Benedito Melo Acioly
Benjam n Rene Callejas Bedregal
Universidade Federal do Rio Grande do Norte - UFRN
Departamento de Informatica e Matematica Aplicada - DIMAp
Indice
1 Linguagens Formais
1.1 Linguagens formais . . . . . . . . .
1.2 -algebras . . . . . . . . . . . . . .
1.3 Relac~ao entre Linguagens Formais e
1.4 Exerc cios . . . . . . . . . . . . . .
.......
.......
-algebras
.......
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
3
5
9
2 Logica Proposicional
13
3 A Teoria da Logica Proposicional
25
2.1 A Linguagem da Logica Proposicional . . . . . . . . . . . . . . . . . . . . . 14
2.2 Logica Proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Exerc cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1
3.2
3.3
3.4
Teorias Formais . . . . . . . . . . . . .
Teoria Formal da Logica Proposicional
Teorema da Deduc~ao . . . . . . . . . .
Exerc cios . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
25
27
28
32
4 Computac~ao na Logica Proposicional
33
5 A Linguagem de Predicados
49
4.1 Metodo de Eliminac~ao de Literais Complementares . . . . . . . . . . . . . 33
4.2 Resultados de Completude . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.1
5.2
5.3
5.4
5.5
Traduc~ao do Portugu^es para a Logica
Quanti cadores e Tipos . . . . . . .
Linguagem de 1a Ordem . . . . . . .
Verdade . . . . . . . . . . . . . . . .
Exerc cios . . . . . . . . . . . . . . . i .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
52
54
61
66