Logica

Y TEOR´ DE
IA
CONJUNTOS

No puedes encontrar la verdad con la l´gica si no
o
la has encontrado ya sin ella.
G.K. Chesterton

´
Indice General
1

L´gica de primer orden
o

1

Introducci´n a la l´gica matem´tica
o
o
a

3

Cap´
ıtulo I: Lengua jes formales de primer
1.1 Introducci´n a los lengua jes formales .
o
1.2 Definici´n de lengua je formal . . . . .
o
1.3Expresiones, t´rminos y f´rmulas . . .
e
o
1.4 Variables libres y ligadas . . . . . . . .
1.5 Sustituci´n de variables . . . . . . . .
o
1.6 Consideraciones finales . . . . . . . . .

orden
....
....
....
....
....
....

Cap´
ıtulo I I: Sistemas deductivos formales
2.1 El c´lculo deductivo de primer orden . .
a
2.2 Reglas derivadas de inferencia . . . . . .
2.3 T´cnicas dededucci´n . . . . . . . . . .
e
o
2.4 Teor´ axiom´ticas . . . . . . . . . . . .
ıas
a
2.5 Descriptores . . . . . . . . . . . . . . . .
2.6 Forma prenexa . . . . . . . . . . . . . .
2.7 Consideraciones finales . . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

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

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

17
17
23
26
30
32
35

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.39
40
45
53
60
66
70
71

Cap´
ıtulo I I I: Modelos
73
3.1 Conceptos b´sicos . . . . . . . . . . . . . . . . . . . . . . . . . . 73
a
3.2 Verdad y validez l´gica . . . . . . . . . . . . . . . . . . . . . . . . 81
o
3.3 Consistencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Cap´
ıtulo IV: La completitud sem´ntica
a
4.1 Completitud sint´ctica . . . . . . .. . . .
a
4.2 La prueba del teorema de completitud . .
4.3 Consecuencias del teorema de completitud
4.4 Consideraciones finales . . . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

95
. 96
. 100
. 106
. 116

Cap´
ıtulo V: Teor´ de la recursi´n
ıa
o119
5.1 Funciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2 Relaciones recursivas . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.3 Conjuntos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . 127
v

´
INDICE GENERAL

vi
5.4
5.5
5.6
5.7
5.8

Numeros de G¨del . . . .
´
o
Funciones parciales . . . .
M´quinas de Turing . . .
a
Latesis de Church-Turing
Consideraciones finales . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
..
.

.
.
.
.
.

128
137
139
145
150

Cap´
ıtulo VI: Teor´ aritm´ticas
ıas
e
153
6.1 Definici´n y propiedades b´sicas . . . . . . . . . . . . . . . . . . 153
o
a
6.2 Algunos teoremas en teor´ aritm´ticas . . . . . . . . . . . . . . 156
ıas
e
6.3 Expresabilidad y representabilidad . . . . . . . . . . . . . . . . . 163
Cap´
ıtulo VII: Incompletitud
7.1 El primer teoremade incompletitud .
7.2 El segundo teorema de incompletitud .
7.3 El teorema de Rosser . . . . . . . . . .
7.4 El teorema de Tarski . . . . . . . . . .
7.5 Otros resultados afines . . . . . . . . .
7.6 El teorema de Church . . . . . . . . .
7.7 Ecuaciones diof´nticas . . . . . . . . .
a

2

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
....