Logica Matematica

Temas de “Lógica matemática y
fundamentos” (2011–12)
José A. Alonso Jiménez
María J. Hidalgo Doblado

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

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:
Reconocimiento. Debe reconocer los créditos de la obra de la manera especificada por el autor.
No comercial. No puede utilizar esta obra para fines comerciales.
Compartir bajo la misma licencia. Si altera o transforma esta obra, o genera
una obra derivada, sólo puede distribuir la obra generada bajo unalicencia
idéntica a ésta.
Al reutilizar o distribuir la obra, tiene que dejar bien claro los términos de la licencia 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, visitehttp://creativecommons.org/licenses/by-nc-sa/2.5/es/ o envie una
carta a Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

2

Índice general

3

Índice general
I

Lógica proposicional

3

1 Sintaxis y semántica de la lógica proposicional
1.1 Introducción . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Panorama de la lógica . . . . . . . . . . . .
1.1.2 Ejemplos de argumentos y formalizaciones
1.2Sintaxis de la lógica proposicional . . . . . . . . . .
1.2.1 El lenguaje de la lógica proposicional . . .
1.2.2 Recursión e inducción sobre fórmulas . . .
1.2.3 Árboles de análisis (o de formación) . . . .
1.2.4 Eliminación de paréntesis . . . . . . . . . .
1.2.5 Subfórmulas . . . . . . . . . . . . . . . . . .
1.3 Semántica proposicional . . . . . . . . . . . . . . .
1.3.1 Valores yfunciones de verdad . . . . . . . .
1.3.2 Interpretaciones . . . . . . . . . . . . . . . .
1.3.3 Modelos, satisfacibilidad y validez . . . . .
1.3.4 Algoritmos para satisfacibilidad y validez .
1.3.5 Selección de tautologías . . . . . . . . . . .
1.3.6 Equivalencia lógica . . . . . . . . . . . . . .
1.3.7 Modelos de conjuntos de fórmulas . . . . .
1.3.8 Consistencia y consecuencia lógica . . . . .1.3.9 Argumentaciones y problemas lógicos . . .
2 Deducción natural proposicional
2.1 Reglas de deducción natural . . . . . . . . . .
2.1.1 Reglas de la conjunción . . . . . . . .
2.1.2 Reglas de la doble negación . . . . . .
2.1.3 Regla de eliminación del condicional .
2.1.4 Regla derivada de modus tollens (MT)
2.1.5 Regla de introducción del condicional
2.1.6 Reglas de la disyunción .. . . . . . .
2.1.7 Regla de copia . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

..
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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

.
.
.
.
.
.
.
.

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