LOGICA COMPUTACIONAL

L´gica Computacional
o
Notas para el curso An´lisis L´gico
a
o
Mat. Favio Ezequiel Miranda Perea

ii

Contenido
1 Sint´xis de la L´gica de Predicados
a
o
1.1 Conceptos B´sicos . . . . . . . . . . . .
a
1.2 Correspondencia con el lenguaje natural
1.2.1 La Negaci´n . . . . . . . . . . . .
o
1.2.2 La Disyunci´n . . . . . . . . . . .
o
1.2.3 La Conjunci´n . . . . . . . . . .
o1.2.4 La Implicaci´n . . . . . . . . . .
o
1.2.5 La Equivalencia . . . . . . . . . .
1.2.6 La Cuantificaci´n Universal . . .
o
1.2.7 La Cuantificaci´n Existencial . .
o
1.2.8 Algunos ejemplos de traducci´n .
o
1.3 Principios de Inducci´n y Recursi´n . . .
o
o
1.4 Conceptos Sint´cticos Importantes . . .
a
1.5 Sustituciones . . . . . . . . . . . . . . .
1.6 Unificaci´n . . . . . . . . .. . . . . . . .
o
1.6.1 Un Algoritmo de Unificaci´n . . .
o

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

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

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

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

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

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

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

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

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

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

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

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

1
1
5
5
5
5
6
6
6
7
7
12
15
16
24
25

2 Sem´ntica de la L´gica de Predicados
a
o
2.1 Interpretaci´nes y Estados . . . . . . .
o
2.2 Evaluaci´n deT´rminos . . . . . . . .
o
e
2.3 La definici´n de Satisfacci´n de Tarski
o
o
2.4 Modelos y Consecuencia L´gica . . . .
o
2.4.1 Validez Universal . . . . . . . .
2.4.2 Consecuencia L´gica . . . . . .
o
2.5 Formas Normales . . . . . . . . . . . .
2.5.1 Forma Normal Negativa . . . .
2.5.2 Forma Normal Prenex . . . . .
2.5.3 Forma Normal Conjuntiva . . .

.
.
.
.
.
.
.
.
.
.

..
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

31
31
35
38
44
47
51
56
57
58
59

iii.
.
.
.
.
.
.
.
.
.

iv

CONTENIDO

2.6

2.7

2.5.4 Forma Normal de Skolem . . . . . . . . . .
2.5.5 Forma Clausular . . . . . . . . . . . . . . .
Los Teoremas Fundamentales de la L´gica . . . . .
o
2.6.1 El Teorema de Herbrand . . . . . . . . . . .
2.6.2 El Teorema de Compacidad . . . . . . . . .
2.6.3 El Teorema de L¨wenheim-Skolem . . . . .
o
El Problema de laDecisi´n . . . . . . . . . . . . . .
o
2.7.1 Semidecidibilidad de la Consecuencia L´gica
o
2.7.2 Indecidibilidad de la Consecuencia L´gica .
o

Bibliograf´
ıa

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

60
64
66
66
70
72
74
75
77
81

Cap´
ıtulo 1Sint´xis de la L´gica de
a
o
Predicados
En este cap´
ıtulo estudiaremos los preliminares sint´cticos necesarios para el
a
resto del libro, s´lamente se supone un conocimiento de la l´gica proposio
o
cional, tema que no trataremos aqu´
ı.

1.1

Conceptos B´sicos
a

Definici´n 1.1 una signatura o tipo de semejanza es un conjunto Σ de
o
s´
ımbolos de alguna de las siguientes formas:(n1 )

• S´
ımbolos de funci´n o letras funcionales: f1
o

(nk )

, . . . , fk
(n1 )

• S´
ımbolos de predicado o letras predicativas: P1

,...
(nk )

, . . . , Pk

,...

• S´
ımbolos de constante: c1 , . . . , ck . . .
Cada s´
ımbolo tiene asociado un n´mero natural, denotado entre par´ntesis,
u
e
que es su aridad o n´mero de argumentos. Las constantes pueden...