Bravo 2013

Carlos Ivorra Castillo

´
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: Lenguajes formales de primer
1.1 Introducci´n a los lenguajes formales .
o
1.2 Definici´n delenguaje formal . . . . .
o
1.3 Expresiones, 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 II: Sistemas deductivos formales
2.1 El c´lculo deductivo de primer orden . .
a
2.2 Reglas derivadasde inferencia . . . . . .
2.3 T´cnicas de deducci´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 III: 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 completitudsem´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
o
119
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

N´meros de G¨del . . . .
u
o
Funcionesparciales . . . .
M´quinas de Turing . . .
a
La tesis 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 teorema de 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

.
.
.
.
.
.
.

.
.
.
.
.
.
.

....