Matematicas discretas

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 GAna I. Fernández M.
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 por Contradicció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...................................................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 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 deBoole.............................................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. FuncionesBooleanas..........................................................................31
6.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...