El programa del curso de Logica y Computaci on

´I

ndice general

1. Preliminares 1

1.1. Relaciones y Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. N´umeros Naturales y Numerabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Relaciones de Equivalencia y Relaciones de Orden . . . . . . . . . . . . . . . . . . . 6

1.4. Secuencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5. Alfabeto y Cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6. ´ Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.7. Conjuntos Inductivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.7.1. Funciones Recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. L´ogica y Computaci´on 23

2.1. Objetivo de la l´ogica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2. Tipos de L´ogicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3. Expectativas y Limitaciones de la L´ogica en Computaci´on . . . . . . . . . . . . . . 26

2.3.1. El Lenguaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2. La Sem´antica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.3. Teor´ıa de la Demostraci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.4. La Automatizaci´on de las Deducciones . . . . . . . . . . . . . . . . . . . . . . 35

2.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3. L´ogica Proposicional 39

3.1. El Lenguaje Lprop de la L´ogica Proposicional . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1. ´ Arbol Sint´actico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2. Sem´antica para la l´ogica cl´asica proposicional . . . . . . . . . . . . . . . . . . . . . . 44

3.2.1. Clasificaci´on sem´antica de las fbs: Satisfacibilidad y Validez . . . . . . . . . . 47

3.2.2. Relaci´on de igualdad sem´antica: Equivalencia L´ogica . . . . . . . . . . . . . . 49

3.3. Formas Normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.1. Forma Normal Negativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.3.2. Formas Normales Disyuntivas y Conjuntivas . . . . . . . . . . . . . . . . . . . 62

3.4. Propiedad de Compacidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.5. Consecuencia L´ogica . . . . . . . . . . . . . .

...