Logica

Lógica Proposicional Introducción
1
Introducción
Los presentes apuntes contienen una introducción a la lógica proposicional y sus aplicaciones
orientada principalmente a carreras técnicas.
Los apuntes se utilizan en la primera parte de la asignatura “Lógica” de la Escuela Universitaria de
Ingeniería Técnica Informática de Oviedo impartida por los autores.
Para cualquier consulta osugenrencia, puede ponerse en contacto con los autores en:
labra@lsi.uniovi.es ó anaisabel@lsi.uniovi.es
J. E. Labra G
Ana I. Fernández M.
Octubre, 1998
Lógica Proposicional Introducción
2
Contenido
Introducción...............................................................................................................1
1. Lenguaje de la LógicaProposicional......................................................................3
1.1. Alfabeto de la Lógica Proposicional......................................................3
1.2. Sintaxis de la Lógica Proposicional.......................................................3
1.3. Semántica de la Lógica Proposicional...................................................4
2. Equivalencia lógica................................................................................................6
3. Consecuencia Lógica.............................................................................................7
4. Técnicas Semánticas de Estudio de Validez Proposicional......................................8
4.1. Tablas de Verdad ................................................................................8
4.2. ÁrbolesSemánticos .............................................................................8
4.3. Demostraciones por Contradicción.......................................................9
4.4. Resolución Proposicional....................................................................10
4.4.1. Formas Normales .............................................................10
4.4.2. Algoritmo deResolución Proposicional..............................12
4.4.3. Estrategias de resolución ...................................................16
4.4.3.1. Estrategias de Borrado.....................................16
4.4.3.1.1. Eliminación de cláusulas con literales puros.........16
4.4.3.1.2. Eliminación de tautologías ..................................16
4.4.3.1.3. Eliminación deSubsunciones..............................17
4.4.3.2. Resolución unitaria ...........................................17
4.4.3.3. Resolución de Entrada .....................................18
4.4.3.4. Resolución Lineal.............................................18
4.4.3.5. Resolución Ordenada.......................................19
5. Teoría de la Prueba: DeducciónNatural...............................................................22
6. Aplicación al diseño de Circuitos: Álgebra de Boole ............................................26
6.1. Introducción.......................................................................................26
6.2. Definición de álgebra de Boole y Teoremas ........................................26
6.3. PuertasLógicas..................................................................................31
6.4. Funciones Booleanas..........................................................................31
6.4.1. Formas Canónicas ............................................................32
Transformación en forma canónica .................................33
6.4.2. Simplificación de funciones lógicas.....................................35
Método deKarnaugh.....................................................36
Funciones incompletas ...................................................39
7. Ejercicios ............................................................................................................40
8. Soluciones...........................................................................................................45...