PDF de programación - Temas de Lógica Informática

Temas de “Lógica informática” (2010–11)

José A. Alonso Jiménez
Andrés Cordón Franco

María J. Hidalgo Doblado

Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e Inteligencia Artificial
Universidad de Sevilla
Sevilla, 7 de Febrero de 2010

Esta obra está bajo una licencia Reconocimiento–NoComercial–CompartirIgual 2.5 Spain
de Creative Commons.

Se permite:

copiar, distribuir y comunicar públicamente la obra

hacer obras derivadas

Bajo las condiciones siguientes:

-2cm-2cm

Reconocimiento. Debe reconocer los créditos de la obra de la manera especificada por
el autor.

-2cm-2cm

No comercial. No puede utilizar esta obra para fines comerciales.

-2cm-2cmCompartir bajo la misma licencia. Si altera o transforma esta obra, o genera una obra

derivada, sólo puede distribuir la obra generada bajo una licencia idéntica a ésta.

Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licen-
cia de esta obra.

Alguna de estas condiciones puede no aplicarse si se obtiene el permiso del titular
de los derechos de autor.

Esto es un resumen del texto legal (la licencia completa). Para ver una copia de esta
licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Índice general

1. Sintaxis y semántica de la lógica proposicional

1.1.

.

.

.

1.2. Sintaxis de la lógica proposicional

.

.

5
5
Introducción .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.1. Panorama de la lógica . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.1.2. Ejemplos de argumentos y formalizaciones . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . .
6
1.2.1. El lenguaje de la lógica proposicional
. . . . . . . . . . . . . . . . .
7
1.2.2. Recursión e inducción sobre fórmulas . . . . . . . . . . . . . . . . .
8
1.2.3. Árboles de análisis (o de formación) . . . . . . . . . . . . . . . . . .
8
1.2.4. Eliminación de paréntesis . . . . . . . . . . . . . . . . . . . . . . . .
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2.5. Subfórmulas .
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3.1. Valores y funciones de verdad . . . . . . . . . . . . . . . . . . . . .
1.3.2.
Interpretaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.3. Modelos, satisfacibilidad y validez . . . . . . . . . . . . . . . . . . . 11
1.3.4. Algoritmos para satisfacibilidad y validez . . . . . . . . . . . . . . 12
1.3.5. Selección de tautologías . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.6. Equivalencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.7. Modelos de conjuntos de fórmulas . . . . . . . . . . . . . . . . . . . 15
1.3.8. Consistencia y consecuencia lógica . . . . . . . . . . . . . . . . . . . 15
1.3.9. Argumentaciones y problemas lógicos . . . . . . . . . . . . . . . . . 17

.

1.3. Semántica proposicional

2. Deducción natural proposicional

19
2.1. Reglas de deducción natural . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1. Reglas de la conjunción . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.2. Reglas de la doble negación . . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . . . . . 20
2.1.3. Regla de eliminación del condicional
2.1.4. Regla derivada de modus tollens (MT)
. . . . . . . . . . . . . . . . 20
2.1.5. Regla de introducción del condicional . . . . . . . . . . . . . . . . . 21
2.1.6. Reglas de la disyunción . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.7. Regla de copia .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.8. Reglas de la negación . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3

4

Índice general

.

. .

2.2. Reglas derivadas

2.1.9. Reglas del bicondicional . . . . . . . . . . . . . . . . . . . . . . . . . 25
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.1. Regla del modus tollens . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2.2. Regla de introducción de doble negación . . . . . . . . . . . . . . . 26
2.2.3. Regla de reducción al absurdo . . . . . . . . . . . . . . . . . . . . . 26
2.2.4. Ley del tercio excluido . . . . . . . . . . . . . . . . . . . . . . . . . . 26
. . . . . . . . . . . . . . . . . . . 28

2.3. Resumen de reglas de deducción natural

3. Tableros semánticos

.

.
.

31
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1. Búsqueda de modelos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2. Notación uniforme .
3.3. Procedimiento de completación de tableros . . . . . . . . . . . . . . . . . . 34
3.4. Modelos por tableros semánticos . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5. Consistencia mediante tableros . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.6. Teorema por tableros .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.7. Deducción por tableros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.8. Tableros en notación reducida . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4. Formas normales

39
4.1. Forma normal conjuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.1. Definición de forma normal conjuntiva . . . . . . . . . . . . . . . . 39
4.1.2. Algoritmo de cálculo de forma normal conjuntiva . . . . . . . . . . 39
4.1.3. Decisión de validez mediante FNC . . . . . . . . . . . . . . . . . . . 41
4.2. Forma normal disyuntiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.2.1. Definición de forma normal disyuntiva . . . . . . . . . . . . . . . . 42
4.2.2. Algoritmo de cálculo de forma normal disyuntiva . . . . . . . . . . 42
4.2.3. Decisión de satisfacibilidad mediante FND . . . . . . . . . . . . . . 43
4.3. Cálculo de formas normales mediante tableros semánticos . . . . . . . . . 44
4.3.1. Forma normal disyuntiva por tableros . . . . . . . . . . . . . . . . . 44
4.3.2. Forma normal conjuntiva por tableros . . . . . . . . . . . . . . . . . 44

.

5. Resolución proposicional
5.1. Lógica de cláusulas .

47
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.1. Sintaxis de la lógica clausal
. . . . . . . . . . . . . . . . . . . . . . . 47
5.1.2. Semántica de la lógica clausal . . . . . . . . . . . . . . . . . . . . . . 47
5.1.3. Equivalencias entre cláusulas y fórmulas . . . . . . . . . . . . . . . 48
5.1.4. Modelos, consistencia y consecuencia entre cláusulas . . . . . . . . 49
5.1.5. Reducción de consecuencia a inconsistencia de cláusulas . . . . . . 49
5.2. Demostraciones por resolución . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2.1. Regla de resolución proposicional
. . . . . . . . . . . . . . . . . . . 50
5.2.2. Demostraciones por resolución . . . . . . . . . . . . . . . . . . . . . 50

Índice general

5

5.3. Algoritmos de resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.3.1. Algoritmo de resolución por saturación . . . . . . . . . . . . . . . . 53
5.3.2. Algoritmo de saturación con simplificación . . . . . . . . . . . . . . 54
5.4. Refinamientos de resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4.1. Resolución positiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4.2. Resolución negativa . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.4.3. Resolución unitaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.4. Resolución por entradas . . . . . . . . . . . . . . . . . . . . . . . . . 57
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.5. Resolución lineal
5.5. Argumentación por resolución . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.5.1. Formalización de argumentación por resolución . . . . . . . . . . . 58
5.5.2. Decisión de argumentación por resolución . . . . . . . . . . . . . . 59

6. Sintaxis y semántica de la lógica de primer orden

61
6.1. Representación del conocimiento en lógica de primer orden . . . . . . . . 61
6.1.1. Representación de conocimiento geográfico . . . . . . . . . . . . . . 61
6.1.2. Representación del mundo de los bloques . . . . . . . . . . . . . . . 62
6.1.3. Representación de conocimiento astronómico . . . . . . . . . . . . 63
6.2. Sintaxis de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . . . 64
6.2.1. Lenguaje de primer orden . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2.2. Términos y fórmulas de primer orden . . . . . . . . . . . . . . . . . 66
6.2.3. Subfórmulas .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.2.4. Variables libres y ligadas . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.3. Semántica de la lógica de primer orden . . . . . . . . . . . . . . . . . . . . 70
6.3.1. Estructuras, asignaciones e interpretaciones
. . . . . . . . . . . . . 70
6.3.2. Evaluación de términos y fórmulas . . . . . . . . . . . . . . . . . . . 72
6.3.3. Modelo, satisfacibilidad y validez de fórmulas . . . . . . . . . . . . 75
6.3.4. Modelo y consistencia de conjuntos de fórmulas . . . . . . . . . . . 77
6.3.5. Consecuencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.3.6. Equivalencia lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

.

.

.

.

.

.

7. Deducción natural en lógica de primer orden

7.1. Sustituciones .

81
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
7.1.1. Definición de sustitución . . . . . . . . . . . . . . . . . . . . . . . . 81
. . . . . . . . . . . . . . . . 81
7.1.2. Aplicación de sustituciones a términos
7.1.3. Aplicación de sustituciones a fórmulas
. . . . . . . . . . . . . . . . 82
7.1.4. Sustituciones libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.2. Reglas de deducción natural de cuantificadores . . . . . . . . . . . . . . . . 83
. . . . . . . . . . . . . . . . . . . 83
. . . . . . . . . . . . . . . . . . 84
. . . . . . . 85

7.2.1. Reglas del cuantificador universal
7.2.2. Reglas del cuant