Trabajo

Universidad de Oviedo
Escuela Universitaria de Ingeniería Técnica de Informática de Oviedo

Lógica Proposicional para Informática
Jose E. Labra G. Ana I. Fernández M. Área de Lenguajes y Sistemas Informáticos Departamento de Informática

Noviembre - 1998

Resolución Proposicional

Introducción

Introducción
Los presentes apuntes contienen una introducción a la lógicaproposicional 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 o sugenrencia, puede ponerse en contacto con los autores en: labra@lsi.uniovi.es ó anaisabel@lsi.uniovi.es J. E. Labra G Ana I. FernándezM. Octubre, 1998

1

Resolución Proposicional

Introducción

Contenido Introducción...............................................................................................................1 1. Lenguaje de la Lógica Proposicional......................................................................3 1.1. Alfabeto de la LógicaProposicional......................................................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. ConsecuenciaLógica.............................................................................................7 4. Técnicas Semánticas de Estudio de Validez Proposicional......................................8 4.1. Tablas de Verdad ................................................................................8 4.2. Árboles Semánticos .............................................................................8 4.3. Demostraciones porContradicción.......................................................9 4.4. Resolución Proposicional....................................................................10 4.4.1. Formas Normales .............................................................10 4.4.2. Algoritmo de Resolución Proposicional..............................11 4.4.3. Estrategias de resolución ...................................................164.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 de Subsunciones..............................17 4.4.3.2. Resolución unitaria ...........................................17 4.4.3.3. Resolución de Entrada.....................................17 4.4.3.4. Resolución Lineal.............................................18 4.4.3.5. Resolución Ordenada.......................................19 5. Teoría de la Prueba: Deducción Natural...............................................................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. Puertas Lógicas..................................................................................30 6.4. Funciones Booleanas..........................................................................316.4.1. Formas Canónicas ............................................................31 Transformación en forma canónica .................................33 6.4.2. Simplificación de funciones lógicas.....................................35 Método de Karnaugh.....................................................36 Funciones incompletas ...................................................38 7....