Logica Para Ciencias De La Computacion

Universidad Nacional del Comahue
Facultad de Econom´ y Administraci´n ıa o
Departamento de Ciencias de la Computaci´n o

Cuadernillo de la Materia

´ ´ Logica para Ciencias de la Computacion

Lic. Laura Andrea Cecchi Versi´n 5 o

´ Neuquen Marzo 2009

Argentina

´ Indice general
1. Introducci´n o 1.1. Organizaci´n del Apunte . . . . . . . . . . . . . . . . . . o 1.2. L´gicaFormal: Lenguaje y Razonamiento . . . . . . . . o 1.2.1. Argumentos . . . . . . . . . . . . . . . . . . . . . 1.2.2. Validez de los Argumentos . . . . . . . . . . . . 1.3. Una visi´n retrospectiva . . . . . . . . . . . . . . . . . . o 1.3.1. El origen de la l´gica . . . . . . . . . . . . . . . o 1.3.2. La l´gica simb´lica en siglo XIX . . . . . . . . . . o o 1.3.3. Siglo XX: La l´gica simb´lica y suconexi´n con la o o o 1.3.4. La Teor´ de la Computaci´n . . . . . . . . . . . ıa o 2. Teor´ Formales ıas 2.1. Sintaxis . . . . . . . 2.2. El aparato deductivo 2.3. Sem´ntica . . . . . . a 2.4. Computaci´n . . . . o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 4 5 6 9 10 10 11 12 13 1515 18 20 23 27 27 27 28 28 33 34 38 39 42 44 45 47 47 47 59 59 62 63

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . computaci´n o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

3. L´gica Proposicional o 3.1. Sintaxis: Lenguaje Formal . . . . . . . . . . . . . . . . . 3.1.1. Expresi´n en Lenguaje Natural . . . . . . . . . . o 3.2. Sem´ntica . . . . . . . . . . . . . . . . . . . . . . . . . . a 3.2.1. Sistema de Valuaci´n . . . . . . . . . . . . . . . . o 3.3. Tableaux . . . . . . . . . . . . . . . . . .. . . . . . . . . 3.3.1. M´todo Tableaux Proposicional . . . . . . . . . . e 3.3.2. Clasificaci´n de los Tableaux Proposicionales . . . o 3.3.3. Refutaci´n y B´squeda de Modelos por Tableaux o u 3.3.4. Sensatez y Completitud . . . . . . . . . . . . . . 3.3.5. Tableaux como procedimiento de decisi´n . . . . . o 3.3.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . 4. C´lculo de Predicados -L´gica Cl´sica a o a 4.1. Computaci´n . . . . . . . . . . . . . . . o 4.1.1. Resoluci´n: Estrategias . . . . . . o 4.2. F.b.f. libre de Skolem . . . . . . . . . . . 4.3. Resultados . . . . . . . . . . . . . . . . . 4.4. Tableaux . . . . . . . . . . . . . . . . . . 4.4.1. Tableaux con variables libres . . . i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . .

ii 5. C´lculo Lambda a 5.1. El Lenguaje . . . . . . . . . . . . . . . . . 5.2. Reducci´n . . . . . . . . . . . . . . . . . . o 5.2.1. Secuencias de reducci´n e Igualdad o 5.2.2. Estrategias de Reducci´n . . . . . . o 5.3. C´lculo Lambda Puro . . . . . . . . . . . a

´ Indice general 73 74 78 79 82 84 87 87 88 89 91 95 97 98 101 106 108 109 111 111 111 112 115 117 118 119120 123

. . . . .

. . . . .

. . . . .

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

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

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

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

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

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

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

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