Lógica Matemática e Algoritmos

Curso B´asico de L´ogica Matem´atica
Renata de Freitas
Petrucio Viana
Vers˜ao preliminar

2

Conte´ udo 1 L´ ogica Sentencial
1.1 Motiva¸c˜ ao . . . . . . . . . . . . . . . . . . . . .
1.1.1 Um Exemplo . . . . . . . . . . . . . . .
1.1.2 Verdades L´ ogicas . . . . . . . . . . . . .
1.2 Sintaxe . . . . . . . . . . . . . . . . . . . . . .
1.2.1 Forma¸c˜ ao de Senten¸cas . . . . . . . . .
1.2.2 Reescrita de Senten¸cas . . . . . . . . . .
1.2.3 Simboliza¸c˜ ao de Senten¸cas . . . . . . . .
1.3 Semˆ antica . . . . . . . . . . . . . . . . . . . . .
1.3.1 Fun¸c˜ ao de Verdade . . . . . . . . . . . .
1.3.2 Regras de avalia¸ca˜o e tabelas de verdade
1.3.3 Interpreta¸c˜ oes . . . . . . . . . . . . . . .
1.4 Tautologias, Contingˆencias e Contradi¸c˜oes . . .
1.5 Equivalˆencia Tautol´ ogica . . . . . . . . . . . . .
1.6 Validade . . . . . . . . . . . . . . . . . . . . . .
1.6.1 Passos L´ ogicos . . . . . . . . . . . . . .
1.6.2 Validade de Argumentos . . . . . . . . .
1.6.3 O M´etodo das Tabelas de Verdade . . .
2 L´ ogica Mon´ adica 2.1 O C´ alculo Sentencial . . . . . . . . . . . . . .
2.1.1 O CS . . . . . . . . . . . . . . . . . .
2.1.2 Insuficiˆencia do CS . . . . . . . . . . .
2.2 Quantifica¸c˜ ao . . . . . . . . . . . . . . . . . .
2.2.1 Quantifica¸c˜ ao em Dom´ınios Finitos . .
2.2.2 Quantifica¸c˜ ao em Dom´ınios Infinitos .
2.3 Sintaxe . . . . . . . . . . . . . . . . . . . . .
2.3.1 Formas Sentenciais . . . . . . . . . . .
2.3.2 Constantes e Vari´ aveis . . . . . . . . .
2.3.3 Forma dos Enunciados Atˆomicos . . .
2.3.4 Propriedades e S´ımbolos de Predicado
2.3.5 Reescrita de S´ımbolos de Predicado .
2.3.6 Termos . . . . . . . . . . . . . . . . .
2.3.7 Reescrita e Simboliza¸c˜ao de Termos .
2.3.8 Simboliza¸c˜ ao de Enunciados . . . . . .
3

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

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . . dos conectivos
. . . . . . . . .
. . .