Matematicas discretas
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...
Regístrate para leer el documento completo.