Source: https://www.scribd.com/doc/52448200/LPROP
Timestamp: 2018-05-25 22:10:01+00:00

Document:
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 o sugenrencia, puede ponerse en contacto con los autores en:
J. E. Labra G
Ana I. Fernández M.
1. Lenguaje de la Lógica Proposicional......................................................................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. Á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..............................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 de Subsunciones..............................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ó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..................................................................................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 de Karnaugh.....................................................36
Funciones incompletas ...................................................39
7. Ejercicios............................................................................................................40
8. Soluciones...........................................................................................................45
Bibliografía...............................................................................................................48
Indice.......................................................................................................................49
Lógica Proposicional Lenguaje de la Lógica Proposicional
Nombre de la conectiva Representación Ejemplos de frases en las que aparece
p no obstante q
o p o q o ambos
al menos p o q
como mínimo p o q
para q es suficiente p
no p a menos que q
Constantes: V F
Variables o letras proposicionales: p, q, r, ...
Símbolos de Conectivas: ¬ ∧ ∨ → ↔
Signos de puntuación: ( )
2. Las letras de proposición p,q,r,.. pertenecen a LPROP
3. Si A y B pertenecen a LPROP entonces ( ) , ( ), ( ), ( ), ( ) , ( ) ¬ ¬ ∧ ∨ → ↔ A B A B A B A B A B
Con dicha tabla, la fórmula ¬p ∨ q → p ∧ r se reconocería como: ((¬p) ∨ q) → (p ∧ r)
La teoría semántica de la lógica proposicional trata de atribuir significados (Verdadero o Falso) a las
distintas fórmulas del lenguaje. Dichos significados dependen del contexto particular en el que se utilice la
fórmula. Cada contexto se denomina Interpretación.
{ ¦ V F , a cada una de las letras proposicionales de F. El valor de una proposición p bajo una
interpretación I se denota como V p
Definición 2: Dada una fórmula F y una interpretación I, el valor de F bajo I (denotado por V F
( ) ) es:
° Si F está formada por una proposición p, entonces V F V p
° Si F es de la forma ¬G entonces V F
si V G
° Si F es de la forma G H ∧ entonces V F
si V G V H
° Si F es de la forma G H ∨ entonces V F
V en caso contrario
° Si F es de la forma G H → entonces V F
° Si F es de la forma G H ↔ entonces V F
Ejemplo 1: Sea la fórmula ( ) F p q q p · → ↔¬ ∨ ¬ y la interpretación I que asigna ( ) V p
· F y
( ) V q
Definición 3: Una interpretación I es un modelo para una fórmula F si V F
( ) · V
Es posible establecer una clasificación de las fórmulas proposicionales en función de los valores que
tomen bajo las diferentes interpretaciones, de esta forma una fórmula F se clasifica en:
Válida ó Tautología: Todas las interpretaciones son un modelo (Para toda interpretación I, V F
( ) · V )
Satisfacible: Alguna interpretación es un modelo (Existe una interpretación I tal que V F
Insatisfacible: Ninguna interpretación es un modelo (No existe una interpretación I tal que V F
Una fórmula puede ser: satisfacible o insatisfacible. Un tipo especial de fórmula satisfacible, es
aquella que toma siempre valor V (es válida). Por tanto, las fórmulas válidas son un subconjunto de las
satisfacibles.
Teorema 1: Una fórmula F es válida si y sólo si su negación ¬F es insatisfacible.
Dem: F es válida
⇔ { Def. válida}
∀I V
(F)= V
⇔ { Def. Interpretación ¬ }
(¬F) = F
⇔ { Def. Insat. }
¬F es Insatisfacible
NOTA: A lo largo de estos apuntes se utilizará un formato lineal para las demostraciones promovido por E.
W. Dijkstra [Dijkstra, 90]. En este formato, las líneas impares contienen los principales pasos de la
demostración y las líneas pares, comentarios para pasar de un paso a otro.
Lógica Proposicional Equivalencia lógica
Definición 4: Se dice que dos fórmulas A y B son equivalentes lógicamente (se denota por A B ≡ ó
A B ⇔ ) si para toda interpretación I, se cumple que V A V B
Teorema 2: A ≡ B si y sólo si la fórmula A↔B es válida
Dem: A≡B
⇔ { Def. ≡ }
(A) = V
⇔ { Def. Interpretación ↔ }
(A↔B) = V
⇔ { Def. Válida }
A↔B es válida
Supresión de Implicación: A B A B → ≡ ¬ ∨
Contraposición: A → B ≡ ¬B → ¬ A
Supresión de Doble Implicación: ( ) ( ) A B A B B A ↔ ≡ → ∧ →
( ) A B A A ∧ ∨ ≡ ( ) A B A A ∨ ∧ ≡
A∧ ≡ F F A∨ ≡ V V
A A ∧ ≡ V A A ∨ ≡ F
E. Complementario Contradicción
A A ∧ ¬ ≡ F
Medio Excluido
A A ∨¬ ≡ V
A A A ∧ ≡ A A A ∨ ≡
A B B A ∨ ≡ ∨ A B B A ∧ ≡ ∧
( ) ( ) A B C A B C ∧ ∧ ≡ ∧ ∧ ( ) ( ) A B C A B C ∨ ∨ ≡ ∨ ∨
( ) ( ) ( ) A B C A B A C ∨ ∧ ≡ ∨ ∧ ∨ ( ) ( ) ( ) A B C A B A C ∧ ∨ ≡ ∧ ∨ ∧
( ) ¬ ∨ ≡ ¬ ∧ ¬ A B A B ( ) ¬ ∧ ≡ ¬ ∨ ¬ A B A B
¬¬ ≡ A A
Teorema 3: Si A es válida y A ≡ B entonces B es válida
Dem: A es válida
⇔ {Si A≡B entonces ∀I V
(B), Leibniz }
B es válida
≡ {...}
Lógica Proposicional Consecuencia Lógica
Definición 5: Sea C un conjunto de fórmulas { ¦ P P P
, ,L y sea Q una fórmula. Se dice que Q es
consecuencia lógica del conjunto C de premisas (se denotará C Q ⇒ ) si toda interpretación que es un
modelo de C es también un modelo de Q.
Es decir, si para toda interpretación I se cumple que si V P V P V P
· · · · L V entonces
( ) · V (Intuitivamente, se podría considerar cada interpretación como un "posible mundo". De esa
en cualquier mundo en el que las premisas tomen valor V ).
Una estructura de la forma { ¦ P P P Q
, ,L ⇒ se denomina razonamiento. Donde { ¦ P P P
, ,L es
Teorema 4: { ¦ P P P Q
, ,L ⇒ es correcto si y sólo si P P P Q
∧ ∧ ∧ → L es válida
Dem: {P
} ⇒ Q es correcto
⇔ { Def. Razonamiento }
∀I Si V
) = ... = V
) = V entonces V
(Q) = V
⇔ { Def. Interpretación de conjunción }
∧...∧ P
⇔ { Def. Interpretación de Implicación }
→ Q) = V
→ Q es válida
Lógica Proposicional Técnicas Semánticas de Estudio de Validez
Definición 6: Una tabla de verdad es una representación en forma de árbol del valor de una fórmula en
Por ejemplo, para calcular el valor de verdad de la fórmula F = p→q ↔ ¬p∨q , la tabla de verdad
consiste en representar las 4 posibles interpretaciones y evaluar la fórmula en dichas interpretaciones
p q p→q ↔ ¬p∨q
El número de posibles interpretaciones de una fórmula F es 2
donde n es el número de variables
proposicionales de F. Por tanto, este método tiene una complejidad exponencial que complica su
utilización para fórmulas complejas
Definición 7: Un árbol semántico es una técnica similar a las tablas de verdad que puede simplificar la
evaluación de algunas fórmulas.
Inicialmente, se forma el conjunto LP de letras proposicionales de la fórmula. Se construye un nodo inicial
del árbol que se tomará como nodo actual y se aplica el siguiente procedimiento:
2.- Si es posible asignar a F un valor { ¦ V F , se etiqueta el nodo con dicho valor y se finaliza el tratamiento
3.-En caso.contrario: - Se Selecciona la primera letra proposicional p del conjunto LP
(identificada como p) y la otra correspondiente a p con valor F (identificada
como ¬p).
Definición 8: Los nodos del árbol semántico en los que el conjunto de significados atribuidos hasta ellos
hacen Falsa la fórmula, se denominan nodos de fallo y los que la hacen verdadera, nodos de éxito
Ejemplo 2: Dada la fórmula (p→q) →(¬p→¬q). Seleccionando los literales por orden alfabético, se obtiene
el árbol semántico:
1.- Se supone que existe una interpretación I tal que V
(F) = F y se intentan calcular los diversos valores de
Entonces: ¬∃I V
(F) = F ⇒ ∀I V
(F) = V ⇒ F es válida
En Caso Contrario: ∃I V
(F) = F ⇒ F no es válida
Este tipo de demostraciones se suelen representar etiquetando la fórmula con valor F y evaluando
posibles valores hasta que se llegue la contradicción.
Ejemplo 3. A continuación se demuestra que la fórmula ¬p∨¬q→¬(p∧q) es válida
q p q p ) ( ∧ ¬ → ¬ ∨ ¬
{A ↔ B, B ↔ C) ⇒ (A ↔ C)
Para ello, basta con demostrar que la fórmula (A↔B)∧(B↔C)→(A↔C) es válida. En dicha
↔ → ↔ ∧ ↔
C A C B B A ↔ → ↔ ∧ ↔
Contradicción Contradicción
El método de resolución es un algoritmo fácilmente mecanizable propuesto por J.A. Robinson en
1965. La entrada del algoritmo no es una fórmula, sino un conjunto de cláusulas y el algoritmo chequea si
son insatisfacibles. Antes de presentar el algoritmo de resolución, se define qué es una cláusula y cómo
transformar una fórmula en un conjunto de cláusulas mediante las formas normales.
Definición 9: Una fórmula F es una conjunción si es de la forma F F F
∧ ∧ ∧ L n≥0
Definición 10: Una fórmula F es una disyunción si es de la forma F F F
∨ ∨ ∨ L n≥0
Definición 11: Un literal es una proposición ( ) p o una proposición negada ( ) ¬p .
∧ ∧ ∧ L donde cada F
es una disyunción de literales. Se representa como ∧ ∨
Ejemplo 5: La siguiente fórmula está en Forma Normal Conjuntiva: (¬p∨q) ∧ (¬p∨r∨¬s) ∧ p
∨...∨F
donde cada F
es una conjunción de literales. Se representa como ∨ ∧
Ejemplo 6: La siguiente fórmula está en Forma Normal Disyuntiva: (p ∧ ¬q ∧ r) ∨ ¬p ∨ (r ∧ ¬s)
Ejemplo 7: Obsérvese que la fórmula ¬p está a la vez en FNC y FND
Teorema 5: Toda fórmula de la lógica de proposiciones puede ser transformada en una fórmula
lógicamente equivalente a ella en Forma Normal Conjuntiva (Disyuntiva).
La demostración consiste en indicar los pasos del algoritmo de transformación a forma normal
conjuntiva. Puesto que estos pasos mantienen la equivalencia y dado que la equivalencia cumple la
propiedad transitiva (ejemplo 4), la fórmula resultante es equivalente a la fórmula original. Para demostrar
formalmente que el algoritmo termina, se requiere el estudio de sistemas de re-escritura de términos que
puede consultarse en [Abramsky, 92]. Los pasos de transformación son:
1. Eliminar conectiva ↔. A↔B≡(A→B)∧ (B→A)
2. Eliminar conectiva →. A B A B → ≡ ¬ ∨
( ) ¬ ∧ ≡ ¬ ∨ ¬ A B A B ( ) ¬ ∨ ≡ ¬ ∧ ¬ A B A B
4. Eliminar negaciones múltiples. ¬¬ ≡ A A
( ) ( ) ( ) A B C A B A C ∧ ∨ ≡ ∧ ∨ ∧ ( ) ( ) ( ) A B C A B A C ∨ ∧ ≡ ∨ ∧ ∨
Puesto que las fórmulas resultantes de aplicar cada uno de los pasos anteriores mantienen la
equivalencia, la fórmula obtenida será equivalente a la fórmula original.
6. Eliminar conjunciones/disyunciones con un literal y su opuesto.
(p∧ ¬p ∧ X) ∨ Y ≡ Y
(p∨ ¬p ∨ X) ∧Y ≡ Y
8. Eliminar subsunciones. Una subsunción se produce cuando una conjunción (o disyunción) C
está incluida en otra D. En dicho caso se elimina la cláusula D
(A ∨ B) ∧ A ≡ A
(A ∧ B) ∨ A ≡ A
Ejemplo 8: Para transformar la fórmula ¬(p→q)↔p∨r a Forma Normal Conjuntiva, se pueden emplear los
¬(p→q)↔p∨r
≡ { Eliminación ↔ }
(¬ (p → q) → p ∨ r) ∧ ( (p ∨ r) → ¬(p → q))
≡ { Eliminación → }
(¬ (¬ (¬p ∨ q) ∨ p ∨ r) ∧ ( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q))
≡ { Eliminación doble negación }
(¬p ∨ q ∨ p ∨ r ) ∧ ( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q))
≡ { Eliminación disyunción con literal y su opuesto }
( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q))
≡ { De Morgan }
(¬p ∧ ¬ r) ∨ (¬¬p ∧ ¬ q)
(¬p ∧ ¬ r) ∨ (p ∧ ¬ q)
≡ { Distributiva ∨ }
((¬p ∧ ¬ r) ∨ p) ∧ ((¬p ∧ ¬ r) ∨ ¬ q)
(¬p ∨ p) ∧(p ∨¬ r) ∧ (¬p∨¬q) ∧ (¬ q∨¬ r)
(p ∨¬ r) ∧ (¬p∨¬q) ∧ (¬ q∨¬ r)
La transformación de una fórmula en Forma Normal Conjuntiva a Forma Clausal es inmediata sustituyendo
las conectivas ∧ por comas y englobando las disyunciones entre llaves.
Ejemplo 9: La fórmula ( ) ( ) ( ) ¬ ∨ ∧ ¬ ∨ ∨ ¬ ∧ p q p q r p en Forma Normal Conjuntiva equivale a
{ ¦ ¬ ∨ ¬ ∨ ∨ ¬ p q p q r p , , en Forma Clausal
Definición 16: Una cláusula sin literales se denomina cláusula vacía, se representa por y su valor es
siempre Falso.
cláusula Horn será de la forma: A B B B
∨ ¬ ∨¬ ∨ ∨¬
Si n=0, se denomina hecho, si no existe literal positivo (no existe A) entonces se denomina objetivo y,
finalmente, si n>0 y existe literal positivo, se denomina regla.
El algoritmo se basa en una regla de inferencia sencilla y, a la vez de gran potencia: la regla de resolución.
Puesto que se utiliza una sola regla, el algoritmo es fácil de analizar e implementar.
La idea del principio de resolución es simple: Si se sabe que se cumple: "P ó Q" y también se sabe que se
cumple "no P ó R" entonces se puede deducir que se cumplirá "Q ó R".
Ejemplo 10: Si se tiene: "Gana o Pierde o Empata" y "Si Gana entonces da una Fiesta o Va de Viaje". Se
puede deducir que: "O Pierde o Empata o da una Fiesta o va de Viaje".
Formalizando, la primera frase sería: G P E ∨ ∨ y la segunda: G F V G F V → ∨ ≡ ¬ ∨ ∨
La regla de resolución inferirá: P E F V ∨ ∨ ∨
Definición 18: Dadas dos cláusulas C
tales que exista un literal l de forma que l C ∈
y ¬ ∈ l C
denomina resolvente de C
respecto a l a la cláusula:
{ ¦ ( ) { ¦ ( ) R C C C l C l
, 1 2 1 2
· − ∪ − ¬ .
Se dice que C
son cláusulas resolubles.
lógica de ellas. Es decir { ¦ ( ) C C R C C
, , ⇒
Sea C l l l l
m 1 11 12 1
· ∨ ∨ ∨ ∨ L y C l l l l
n 2 21 22 2
· ¬ ∨ ∨ ∨ ∨ L .
El resolvente de C
respecto a l será R C C l l l l l l
1 2 11 12 1 21 22 2
· ∨ ∨ ∨ ∨ ∨ ∨ ∨ L L
Por el teorema 2, probar que { ¦ ( ) C C R C C
, , ⇒ es equivalente a probar que ( ) C C R C C
∧ → , es
∨ ∨ ∨ ∧ ¬ ∨ ∨ ∨ → ∨ ∨ ∨ ∨ ∨
11 1 21 2 11 1 21 2
1 2 444444 3 444444
1 2 4444 3 4444
1 2 444444444444 3 444444444444
la fórmula es Válida. n
Teorema 7: Dadas dos cláusulas C
pertenecientes a un conjunto C y resolubles respecto un literal l,
, C C R C C
∪ ≡ .
Dem: Recordando que un conjunto de cláusulas equivale a forma normal conjuntiva, ( )
, C C R C
es lo mismo que ( )
∧ . La demostración es:
≡ { Absorción A ≡ A ∧ B }
Teorema 8: Si el resolvente de dos cláusulas C
pertenecientes a un conjunto C es la cláusula vacía,
entonces C es insatisfacible.
Dem: ( ) ·
≡ { Teorema 7, Leibniz }
C ≡ C ∧
≡ { Def. ≡ F }
C ≡ C ∧ F
≡ { El. Neutro, C ∧ F ≡ ≡ F }
C ≡ F
≡ { Def. Interpretación ≡ }
≡ { Def. Interpretación: V
(F) = F }
(C) = F
≡ { Def. Insatisfacible }
C es insatisfacible
A partir de los teoremas anteriores, se define el algoritmo de resolución que chequeará si un conjunto de
cláusulas es insatisfacible.
Entrada: Un conjunto de cláusulas C
Salida: Detecta si C es insatisfacible
1.- Buscar dos cláusulas C C C
, ∈ tales que exista un literal l que cumple que l C ∈
3.- Calcular R C C
4.- Si R C C
· Ì entonces SALIR indicando que C es insatisfacible.
Ejemplo 11: Sea C el siguiente conjunto de cláusulas { ¦ p p q r p q r , , , ¬ ∨ ¬ ¬ ∨ ¬ ∨ , se puede demostrar
- Se resuelve la tercera cláusula (¬r ) con la cuarta (¬ ∨¬ ∨ p q r ), obteniendo ¬ ∨¬ p q .
- Se resuelve ahora la cláusula anterior con la segunda cláusula (¬ ∨ p q ) obteniendo: ¬p
Teorema 9: Un razonamiento de la forma P P P Q
, , , L ⇒ es correcto si y sólo si el conjunto de
, , , L ¬ es insatisfacible. Cada P
es el resultado de transformar la premisa P
forma clausal y ¬Q
es el resultado de transformar la negación de la conclusión a forma clausal.
Dem: Q P P P
⇒ , , ,
⇔ { Teorema 4}
→ ∧ ∧ ∧ L
⇔ { Teorema 1}
¬( Q P P P
) es insatisfacible
⇔ { Pasando a Forma Normal Conjuntiva cada premisa y operando }
, , , L ¬ es insatisfacible
Ejemplo 12: Para estudiar si el razonamiento { ¦ p q r s p s p q ∧ → ∧ → ¬ ⇒ ¬ ∨ ¬ , es correcto por
negación de la conclusión a forma clausal. El conjunto obtenido sería
{ ¦ ¬ ∨ ¬ ∨ ¬ ∨¬ ∨ ¬ ∨ ¬ p q r p q s p s p q , , , , . Aplicando el algoritmo de resolución:
- Se resuelve la segunda cláusula (¬ ∨ ¬ ∨ p q s ) con la tercera (¬ ∨ ¬ p s), obteniendo ¬ ∨¬ p q
- Se resuelve ahora la cláusula anterior con la cuarta cláusula (p) obteniendo: ¬q
Puesto que se llega a la cláusula vacía, el conjunto de cláusulas es insatisfacible y el razonamiento es
Se presentan las ideas generales de la demostración de la completud del algoritmo de resolución
proposicional sin entrar en una demostración formal que se sale del ámbito de estos apuntes.
Ejemplo 13: Sea el conjunto de cláusulas { ¦ C p p q r p q r · ¬ ∨ ¬ ¬ ∨ ¬ ∨ , , , , para construir el árbol
semántico para C se recuerda que un conjunto de cláusulas equivale a una fórmula en Forma Normal
Conjuntiva, en este caso, ( ) ( ) ( ) p p q r p q r ∧ ¬ ∨ ∧ ¬ ∧ ¬ ∨ ¬ ∨ . En la siguiente figura se muestra el árbol
( ) ¬ ∨ p q
( ) ¬ ∨ ¬ ∨ p q r
( ) ¬r
Lema 1: Si un conjunto de cláusulas es insatisfacible, entonces el árbol semántico es finito y está limitado
por nodos de fallo, se denomina, en ese caso, árbol de fallo.
Lema 2: Cada nodo de fallo n falsifica al menos a una de las cláusulas del conjunto que será la cláusula
asociada a n.
Lema 3: La cláusula C asociada a un nodo de fallo n contiene un subconjunto de los complementos de los
literales que aparecen en la rama que va desde la raíz del árbol semántico hasta n.
Dem: Puesto que la cláusula C es falsificada en el nodo n, todos sus literales deben tener asignado un
valor en la interpretación parcial correspondiente a n. Además, el valor de esos literales debe ser F (puesto
que C es una disyunción). El valor asignado debe ser el complementario. n
Definición 19: Se denomina nodo de inferencia a un nodo del árbol semántico cuyos dos hijos son nodos
tendremos un último nodo desarrollado con dos hijos. n
Lema 5: Si el árbol semántico de un conjunto de cláusulas es de fallo y contiene un sólo nodo, entonces
dicho conjunto contiene la cláusula vacía.
Lema 6: Un nodo de inferencia i indica un paso de resolución de las cláusulas asociadas a sus dos hijos.
El resolvente de dichas cláusulas es falsificado por el nodo i y, ocasionalmente, por alguno de sus
( ) ¬
- Puesto que el nodo i no falsificó C
y lo único que cambia en el nodo j respecto a i es el valor de p, la
debe contener el literal ¬p (complementado para que sea Falso).
- Por la misma razón anterior, la cláusula C
debe contener el literal p (sin complementar para que sea
son resolubles respecto a p. El esquema será:
C p resto C
R C C resto C resto C
p j k j k
· ¬ ∨
· ∨
( , ) _ _
En el nodo j, C
toma valor Falso, por tanto resto C
_ tomará también valor Falso, como resto C
contiene el literal p también tomarán valor Falso en el nodo i. De la misma forma, resto C
_ tomará valor
Falso en el nodo i. Por tanto, R C C resto C resto C
( , ) _ _ · ∨ tomará valor Falso en el nodo i, es decir,
el nodo i, es un nodo de fallo para el resolvente de C
En ocasiones, puede ocurrir que el resolvente sea falsificado también por alguno de los padres del nodo de
inferencia, como ejemplo, considérese el conjunto de cláusulas { ¦ p p q r p r , , , ¬ ∨ ¬ ¬ ∨ , el árbol
( ) ¬ ∨ p r
( ) ¬p
( ) ¬r F
El resolvente de los nodos 6 y 7 es (¬p) que falsifica al nodo 4 pero también falsifica a su antecesor, el
nodo 2. n n
Teorema 10 (Completud del Algoritmo de Resolución Proposicional): Si un conjunto de cláusulas es
insatisfacible entonces, aplicando el algoritmo de resolución, se alcanza la cláusula vacía.
Dem: C es un conjunto de cláusulas insatisfacibles
⇔ {Lema 1}
⇔ {Lema 4}
∃ un nodo de inferencia i
⇔ {Lema 6, un nodo de inferencia indica un paso de resolución }
⇔ { Hipótesis, C es insatisfacible, Consistencia Resolución }
Repitiendo el proceso se llegará a un árbol semántico con un solo nodo que corresponderá a la
cláusula vacía {Lema 5} y, por tanto, queda demostrado que se alcanza la cláusula vacía por
El método de resolución es un algoritmo no determinista ya que pueden encontrarse múltiples
formas de alcanzar la cláusula vacía en un conjunto insatisfacible. Muchas veces, siguiendo un
determinado camino se alcanzará la cláusula vacía con muchos menos pasos de resolución que por otro
Durante el desarrollo del algoritmo es necesario responder las siguientes preguntas: ¿Qué dos
cláusulas se seleccionan? y ¿sobre qué literales se realiza la resolución?.
Las distintas estrategias de resolución tratan de responder a ambas preguntas de forma que se
mantenga la completud (si el conjunto es insatisfacible, alcanzar la cláusula vacía) y que se obtenga un
Una de las desventajas de la utilización de la reglas de resolución sin ninguna restricción consiste
en que se pueden seleccionar cláusulas cuyo resolvente no sea útil en el camino de búsqueda de la
cláusula vacía. Se observa que muchas veces los resolventes son redundantes o no aportan ninguna
utilidad para la búsqueda. A continuación se mencionan una serie de estrategias que servirán para eliminar
el trabajo inútil.
Una estrategia de borrado será una técnica en la cual se eliminan una serie de cláusulas antes de
que sean utilizadas. Si dichas cláusulas no van a aportar nada para la búsqueda de la cláusula vacía, su
eliminación permitirá un ahorro computacional.
Definición 20: Un literal es puro si y sólo si no existe un literal complementario a él en el conjunto de
Una cláusula que contenga un literal puro es inútil en la búsqueda de la cláusula vacía, puesto que el
literal puro no podrá ser eliminado nunca mediante resolución. Por tanto, una estrategia de borrado
consiste en la eliminación de cláusulas con literales puros.
Ejemplo 14: El conjunto { ¦ C p q r p s q s p q r · ¬ ∨ ¬ ∨ ¬ ∨ ¬ ∨ ¬ , , , , , es insatisfacible, sin embargo, para
Definición 20: Una tautología es una cláusula que contiene el mi smo literal en su forma directa e inversa.
Ejemplo 15: La cláusula p q r p ∨ ¬ ∨ ∨ ¬ es una tautología.
La presencia o ausencia de tautologías en un conjunto de cláusulas no afecta la condición de
satisfacibilidad del conjunto. Un conjunto de cláusulas permanecerá satisfacible independientemente de
que se le añadan tautologías. De la misma forma, un conjunto de cláusulas insatisfacible seguirá siendo
insatisfacible aunque se eliminen todas sus tautologías. Es posible, por tanto, eliminar las tautologías de
un conjunto de cláusulas para que no intervengan en el proceso de búsqueda sin alterar la satisfacibilidad
D, es decir, C D ⊆ .
Ejemplo 16: La cláusula p q ∨ ¬ subsume a la cláusula p q r ∨ ¬ ∨ .
Debido a la ley de absorción, un conjunto de cláusulas en el que se eliminan todas las cláusulas
subsumidas es equivalente al conjunto original. Las cláusulas subsumidas pueden ser, por tanto,
Es necesario observar que, durante el desarrollo del proceso de resolución, se pueden generar resolventes
de cláusulas que sean tautologías o cláusulas subsumidas. Las estrategias de borrado deberán chequear
el conjunto de cláusulas original así como los distintos resolventes generados en cada resolución.
Definición 22: Un resolvente unitario es un resolvente en el cual al menos uno de sus padres es una
cláusula unitaria (con un sólo literal).
Una estrategia de resolución unitaria es una aplicación del algoritmo de resolución en la cual todos los
resolventes son unitarios.
Ejemplo 17: Sea { ¦ C p q p r q r r · ∨ ¬ ∨ ¬ ∨ ¬ , , , . A continuación se aplicará la estrategia de resolución
1.- p q ∨
2.- ¬ ∨ p r
3.- ¬ ∨ q r
4.- ¬r
5.- ¬p R
( , ) 2 4
6.- ¬q R
( , ) 3 4
7.- q R
( , ) 1 5
8.- p R
( , ) 1 6
9.- r R
( , ) 3 7
10.- r R
( , ) 6 7
Obsérvese que los resolventes generados son un subconjunto de los que se podrían generar mediante la
resolución sin restricciones. Por ejemplo, las cláusulas 1 y 2 podrían haberse seleccionado para obtener
q r ∨ . Sin embargo ni esa cláusula ni sus descendientes podrán ser generados porque ninguna de las
cláusulas que la generan es unitaria.
Los procedimientos de resolución basados en resolución unitaria son sencillos de implementar y,
normalmente, bastante eficientes. Obsérvese que si una cláusula es resuelta con una cláusula unitaria, su
resolvente tiene menos literales que la cláusula original. De esa forma los procedimientos siguen una
búsqueda directa hacia la cláusula vacía ganando en eficiencia.
Desafortunadamente, los procedimientos de inferencia basados en resolución unitaria no son, en general,
completos. Por ejemplo, el conjunto { ¦ C p q p q p q p q · ∨ ¬ ∨ ∨ ¬ ¬ ∨ ¬ , , , es insatisfacible, sin embargo,
Por otro lado, restringiendo el formato de cláusulas a cláusulas Horn (cláusulas con un literal positivo
como máximo) se puede demostrar que si un conjunto de cláusulas Horn es insatisfacible, entonces se
llegará a la cláusula vacía aplicando la estrategia de resolución unitaria.
Definición 23: Un resolvente de entrada es un resolvente en el cual al menos uno de sus padres es una
cláusula del conjunto original de entrada.
Una estrategia de resolución de entrada es una aplicación del algoritmo de resolución en la cual todos los
resolventes son de entrada.
Ejemplo 18: Sea { ¦ C p q p r q r r · ∨ ¬ ∨ ¬ ∨ ¬ , , , . A continuación se aplicará la estrategia de resolución de
entrada, para ello, se seleccionan siempre dos cláusulas resolubles tales que una de ellas pertenezca al
conjunto inicial de cláusulas:
5.- q r ∨ R
( , ) 1 2
6.- p r ∨ R
( , ) 1 3
7.- ¬p R
8.- r R
( , ) 2 6
( , ) 4 8
Se puede demostrar que la resolución unitaria y la resolución de entrada tienen el mismo poder de
inferencia en el sentido de que si con una estrategia se puede alcanzar la cláusula vacía, con la otra
Una consecuencia de lo anterior es que la resolución de entrada es completa para cláusulas Horn, pero
incompleta en general. Como contraejemplo, se puede tomar el del apartado anterior.
4.4.3.4. Resolución Lineal
La resolución lineal (también conocida como resolución con filtrado de antepasados) es una ligera
generalización de la resolución de entrada. Se escoge una cláusula inicial o cláusula cabeza C
una cedena de resolventes R R R R
, , , , L donde:
R R R C C C C R
· ∈ · ≤
, tal que ó j i
La resolución lineal toma su nombre del aspecto lineal que presentan las inferencias realizadas. Una
resolución lineal comienza con una cláusula del conjunto inicial y produce una cadena lineal de
resoluciones como la que se muestra en la figura para el conjunto de cláusulas
{ ¦ C p q p q p q p q · ∨ ¬ ∨ ∨ ¬ ¬ ∨ ¬ , , , . Obsérvese que cada resolvente, después del primero, se obtiene
del resolvente anterior y de alguna otra cláusula del conjunto.
¬ ∨ p q p q ∨ ¬ ¬ ∨ ¬ p q
La resolucióon lineal evita muchas resoluciones inútiles centrándose en cada paso en los antepasados de
una cláusula y en los elementos del conjunto inicial.
Los resultados obtenidos aplicando resolución para una determinada cláusula cabeza se pueden mostrar
en forma de árbol de resolución. La raíz del árbol es la cláusula cabeza y se forman los nodos
descendientes según las cláusulas con las que se pueda resolver. El árbol de resolución para el ejemplo
anterior sería:
6: p 8:p
3p 4p 4p
9: p 10:
11: q 12:
2p 4q
13: q 14:
15: p 16:
En la figura se representan las resoluciones indicando el número de cláusula y el literal por el que se
resuelve. A cada resolvente se le asigna un nuevo número. Obsérvese que pueden existir caminos infinitos
(el camino más a la izquierda), caminos que llevan a tautologías y caminos de éxito que alcanzan la cláusula
Se puede demostrar que la resolución lineal es completa. Para cualquier conjunto de cláusulas
insatisfacibles, aplicando resolución lineal, se alcanza la cláusula vacía.
Debido al siguiente teorema, no siempre es necesario probar con todas las cláusulas del conjunto inicial
como cláusulas cabeza.
Teorema 11: Si un conjunto de cláusulas S es satisfacible y S C ∪ es insatisfacible, entonces se
encuentra la cláusula vacía mediante resolución lineal tomando como cláusula cabeza una cláusula del
El teorema anterior tiene aplicación al estudio de los razonamientos, en los cuales las premisas son, por lo
general, satisfacibles. Si al añadir las cláusulas resultantes de negar la conclusión el conjunto resultante es
insatisfacible (y el razonamiento es correcto) entonces, según el teorema anterior basta con probar como
cláusula cabeza con las que resultaron de negar la conclusión.
La resolución ordenada o selectiva es una estrategia de resolución muy restrictiva en la cual cada
cláusula se toma como un conjunto de literales ordenados. La resolución sólo se realiza con el primer literal
de cada cláusula. Los literales del resolvente mantienen el orden de las cláusulas padre con los literales del
padre positivo (la cláusula que contenía el literal por el que se resuelve afirmado) seguidos de los literales
del padre negativo (la cláusula que contenía el literal por el que se resuelve negado).
Ejemplo 19: Sea { ¦ C p q p r q r r · ∨ ¬ ∨ ¬ ∨ ¬ , , , . A continuación se aplicará la estrategia de resolución
ordenada (se han ordenado los literales de cada cláusula por orden alfabético):
6.- r R
( , ) 3 5
7.- r R
( , ) 4 6
La cláusula 5 es el único resolvente ordenado entre las cláusulas 1 y 4. Las cláusulas 1 y 3 no resuelven
puesto que sus literales complementarios no son los primeros. Por la misma razón tampoco resuelven las
cláusulas 2 y 4 ni las cláusulas 3 y 4. Una vez generada la cláusula 5, resuelve con la cláusula 3 para
producir la cláusula 6, la cual resuelve con la cláusula 4 para producir la cláusula vacía.
La resolución ordenada es la más eficiente (en el ejemplo, se obtuvo la cláusula vacía en el tercer paso de
resolución). Desafortunadamente, la resolución ordenada no es completa. Sin embargo, se ha demo strado
que la resolución ordenada sí es completa para cláusulas Horn.
Tras este breve repaso de las principales estrategias de resolución, cabe reseñar que los principales
sistemas de demostración automática basados en el principio de resolución (por ejemp lo, los sistemas
Prolog) utilizan una combinación de las dos últimas estrategias restringidas a conjuntos de cláusulas
Los sistemas Prolog utilizan la resolución lineal ordenada para cláusulas Horn en lógica de
predicados. Conocida como resolución SLD (Selective Linear Resolution for Definite Clauses).
Lógica Proposicional Teoría de la Prueba: Deducción Natural
En las secciones anteriores se han utilizado técnicas que estudian la corrección de los
razonamientos en base al significado de las fórmulas que contienen. Este conjunto de técnicas se
engloban en lo que se denomina teoría semántica. Por el contrario, existe otro conjunto de técnicas,
conocido como teoría de la prueba, que prescinde de los posibles valores de las fórmulas y se centra
únicamente en la manipulación sintáctica de fórmulas. Existen diversos estilos como el sistema de Hilbert,
la deducción natural, etc. Todos ellos utilizan un conjunto de axiomas y una serie de reglas de inferencia
que permiten obtener teoremas a partir de dichos axiomas o de otros teoremas previamente derivados.
En esta sección se presenta el estilo de deducción natural, desarrollado por Gentzen en 1935 y cuyo
principal objetivo es ofrecer un sistema que se acerque a las técnicas de demostración habituales. La
deducción natural no contiene axiomas y ofrece una serie de reglas de inferencia por cada tipo de
conectiva. Las reglas de inferencia se presentan en la siguiente tabla.
Reglas de Introducción Reglas de Eliminación
Dem. por Contradicción
Tabla 1: Reglas de Inferencia para Deducción Natural
Las reglas de la forma • - I se refieren a la inclusión del símbolo • y las reglas de la forma • - E se
refieren a la eliminación de dicho símbolo.
Ejemplo 20: Demostrar que p ∧ q → q ∧ p
1 p ∧ q Premisa
2 q ∧-E 1
3 p ∧-E 1
4 q ∧ p ∧-I 2,3
Para el estudio de razonamientos de la forma {P
} ⇒ Q se parte de las premisas y se intenta
llegar a la conclusión.
Ejemplo 21: Demostrar que p ∧ q ⇒ p ∧ (q ∨ r)
2 p ∧-E 1
3 q ∧-E 1
4 q ∨ r ∨-I 3
5 p ∧ (q ∨ r) ∧-I 2,4
La utilización de cuadros permite visualizar la idea de pruebas subordinadas. En una prueba
subordinada, se realiza un supuesto y, una vez llegado a un resultado, se descarta el supuesto (se cierra el
cuadro) obteniendo un resultado libre de supuestos. Un ejemplo es la regla de deducción:
Esta regla enuncia que, si se supone A y se llega a demostrar B, entonces, se puede deducir la
fórmula A → B.
Ejemplo 22: Demostrar que p → (q → r) ⇒ p ∧ q → r
1 p → (q → r) Premisa
2 p ∧ q Supuesto
3 p ∧-E 2
4 q → r → E 1,3
5 q ∧-E 2
6 r → E 4,5
7 p ∧ q → r → I 2-6
Ejemplo 23: Demostrar que p ∧ q → r ⇒ p → (q → r)
1 p ∧ q → r Premisa
2 p Supuesto
3 q Supuesto
4 p ∧ q ∧-I 2,3
5 r → E 1,4
6 q → r → I 3-5
7 p → (q → r) → I 2-6
Ejemplo 24: Demostrar que ¬p ⇒ p → q
1 ¬p Premisa
3 p∧¬p ∧-I 1,2
4 F F-I 3
5 q F-E 4
6 p → q → I 2,5
Ejemplo 25: Demostrar p ↔ ¬¬p
1 p Supuesto
2 ¬p Supuesto
3 p ∧ ¬p ∧-I 1,2
4 ¬¬p ¬I 2-3
5 p → ¬¬p → I 2-4
6 ¬¬p Supuesto
7 ¬p Supuesto
8 ¬p ∧ ¬¬p ∧-I 6,7
9 p ¬-E 7-8
10 ¬¬p → p →-I 6-9
11 p ↔ ¬¬p ↔-I 5,10
Ejemplo 26: Demostrar que ¬p∨q ⇒ p→q
1 ¬p∨q Premisa
3 ¬p Supuesto
4 p→q ¬A⇒A→B (Demostrado en Ej. 24)
5 ¬p → (p → q) → I 3-4
6 q Supuesto
7 p Supuesto
9 p → q →-I 7-8
10 q → (p → q) →-I 6-10
11 p→q ∨-E 1,5,10
Ejemplo 27: Demostrar que p → q ⇒ ¬p∨q
1 p → q Premisa
2 ¬ (¬p∨ q) Supuesto
4 ¬p∨q ∨-I 3
5 (¬p∨q) ∧ ¬(¬p∨q) ∧-I 4,2
6 p ¬-E 3-5
7 q →-E 1,6
8 ¬p ∨ q ∨-I 7
10 (¬p∨q) ∧ ¬(¬p∨q) ∧-I 8,2
11 ¬p∨q ¬-E 2-10
Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole
George Boole (1815-1864) presentó el primer tratamiento sistemático de la lógica y para ello,
desarrolló un sistema algebraico, conocido ahora como Álgebra de Boole. Además de sus aplicaciones al
campo de la lógica, el álgebra de Boole ha tenido dos aplicaciones importantes: el tratamiento de conjuntos
mediante las operaciones de unión e intersección que ha servido de base a la teoría de la probabilidad y el
diseño de circuitos digitales combinacionales.
6.2. Definición de álgebra de Boole y Teoremas
Definición 24: Un álgebra de Boole es una estructura de la forma {A, +, × × , -, 0,1} siendo A un conjunto en
el que se definen las siguientes operaciones:
+ y × son leyes de composición binaria sobre A: a + b ∈ A y a × b ∈ A ∀a,b ∈ A
- es una ley de composición unaria sobre A: A a ∈ ∀ a ∈ A
verificándose los postulados:
1. Conmutativa: a + b = b + a ∀a,b ∈ A {conmutativa +}
a × b = b × a ∀a,b ∈ A {conmutativa ×}
2. Distributiva: a + (b × c) = (a + b) × (a + c) ∀a,b,c ∈ A {distributiva +}
a × (b + c) = (a × b) + (a × c) ∀a,b,c ∈ A {distributiva ×}
3. Elemento neutro: a + 0=a ∀ a ∈ A {neutro +}
a × 1=a ∀ a ∈ A {neutro ×}
4. Elemento inverso: a a + · 1 ∀ a ∈ A {inverso +}
a a * · 0 ∀ a ∈ A {inverso ×}
En el caso más sencillo, el conjunto A tiene como únicos elementos a los neutros de las
operaciones, A={ 0 , 1 }. Esto quiere decir que las variables sólo pueden tomar los valores 0 o 1. En este
caso, el álgebra de Boole se dice que es bivaluada.
Ejemplo 28: La lógica proposicional LPROP, tiene estructura de álgebra de Boole.
Basta con demostrar que la tupla (LPROP, ∨, ∧, , F, V) cumple la definición de álgebra de Boole
Los elementos de LPROP, las fórmulas de la lógica proposicional, sólo pueden tomar los valores F
o V, o lo que es lo mismo, 0 o 1.
La disyunción y la conjunción son operaciones binarias (intervienen dos operandos) e internas.
El complementario es una operación unaria interna.
Como ya se ha demostrado, se cumplen los postulados del álgebra de Boole:
Commutativa: a ∨ b = b ∨ a y a ∧ b = b ∧ a ∀a,b∈A
Distributiva: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) ∀a,b∈A
Elemento neutro: a ∨ F = a
a ∧ V =a ∀a∈A
Elemento inverso: a ∨ ¬a = V (medio excluido) y a ∧ ¬a = F (contradicción) ∀a∈A
Ejemplo 29: Dado un conjunto C, la estructura {2
, ∪, ∩, -, C, ∅ }, donde 2
subconjuntos de C, ∪, ∩ y - son las operaciones de unión, intersección y complementario entre conjuntos
y ∅ es el conjunto vacío, tiene estructura de álgebra de Boole
Ejemplo 30: La estructura {A, ⊗, ⊕, ', 0, I} donde A contiene los elementos: {0, 1, S, S' } y las operaciones
se definen mediante las siguientes tablas, también tiene estructura de álgebra de Boole
⊗ 0 S S' I ⊕ 0 S S' I X X'
0 0 0 0 0 0 0 S S' I 0 I
S 0 S 0 S S S S I I S S'
S' 0 0 S' S' S' S' I S' I S' S
I 0 S S' I I I I I I I 0
Ejemplo 31: Dado un número natural n, la estructura {D
, mcm, mcd, (n/), n, 1 } donde D
divisores de n, mcm y mcd son el mínimo común múltiplo y (n/) x = n / x tiene estructura de álgebra de
A partir de la definición de álgebra de Boole, se deducen los teoremas siguientes:
Teorema 12 (Principio de dualidad): Cada identidad deducida de los postulados del álgebra de Boole
permanece válida si se intercambian las operaciones + y ×, y los valores 0 y 1.
De manera informal, este teorema puede demostrarse indicando que, puesto que los postulados son todos
simétricos y cumplen la propiedad de dualidad, todo lo que se deduzca de ellos, cumplirá también dicha
Teorema 13 (Dominación ó Elemento Cero) a + 1 = 1 ∀a ÎA
a × 0 = 0 [Dual]
= { inverso + }
= {neutro ×, a/ a }
a + a × 1
= { distributiva + }
(a + a ) × (a + 1)
1 × (a + 1)
= { neutro × }
A partir del teorema anterior se pueden construir las tablas de verdad de las operaciones boolenas + y ×
Teorema 14 (Idempotencia) a + a = a ∀a ÎA
a × a = a [Dual]
= { neutro + }
= { inverso ´ }
a + a ´ a
(a + a) × (a + a )
(a + a) ´ 1
Teorema 15 (Absorción) a + a × b = a ∀a,b ÎA
a × (a + b) = a [Dual]
= { dominación + }
(1 + b) × a
= { distributiva × }
1 × a + b × a
a + a ´ b
Teorema 16 (Asociativa). a + (b + c) = (a + b) + c = a + b + c "a,b,c ÎA
a ´ (b ´ c) = (a ´ b) ´ c = a ´ b ´ c [Dual]
Demostración: Se demostrarán dos teoremas auxiliares TA1 y TA2:
TA1: a × × ((a + b) + c) = a × × (a + (b + c))
a × ((a + b) + c)
a × (a + b) + a × c
= { absorción × }
a + a × c
= { absorción + }
= { absorción ×, b / b+c }
a × (a + (b + c))
TA2: a × × ((a + b) + c) = a × × (a + (b + c))
( a × a + a × b) + a × c
= { inverso × }
(0 + a × b) + a × c
= { neutro+ }
a × ( b + c)
0 + a × ( b + c)
a × a + a × ( b + c)
A partir de dichos teoremas auxiliares, la demostración se obitiene fácilmente:
= {neutro × }
((a + b) + c) × 1
((a + b) + c) × (a + a )
= { distributiva ×, conmutativa }
a × ((a + b) + c) + a × ((a + b) + c)
= { TA1 }
a × (a + (b + c)) + a × ((a + b) + c)
= { TA2 }
a × (a + (b + c)) + a × (a + (b + c))
(a + a ) × (a + (b + c))
1 × (a + (b + c))
Teorema 17. (Unicidad del complementario) El elemento a asociado a un elemento a en un álgebra de
Boole es único, es decir, existe un único elemento, x, que cumple la propiedad de elemento inverso, es
decir, que cumpla que : a + x = 1 y a ´ x = 0
Supóngase que existen dos elementos x e y que cumplen la propiedad:
a + x = 1 (H1)
a ´ x = 0 (H2)
a + y = 1 (H3)
a ´ y = 0 (H4)
= { H3 }
(a + y) × x
a × x + y × x
= { H2 }
0 + y × x
= { H4 }
a × y + y × x
= { distributiva ×, conmutativa × }
(a + x) × y
= { H1 }
Concluyendo que x e y son el mismo elemento
Teorema 18 (Involución). a a · ∀ a ÎA
Demostración: A partir del teorema anterior, cualquier x que cumpla que a + x = 1 y que a × x = 0 es
igual a a . Suponiendo que dicho x es a, se demuestra:
= { conmutativa + }
= { conmutativa × }
a ´ a
Por tanto, a = a
Teorema 19. (De Morgan) ... . .. × × × · + + + c b a c b a
... . .. + + + · × × × c b a c b a [Dual]
Se realizará en dos partes: En la primera parte se demostrará para dos variables, y la segunda parte,
se generaliza el resultado para n variables.
1.- Demostración para dos variables: b a b a × · +
Por la unicidad del complementario, el único x que cumple que (a + b) + x = 0 y (a + b) × x = 1 es b a + .
Si se demuestra que
a + b + b a × = 0
(a + b) × b a × = 1
entonces quedará demostrado
b a b a × · +
Las demostraciones de ambas igualdades son sencillas:
a + b + b a ×
(a + b +a ) × (a + b +b )
= { Conmutativa +, inverso + }
(1 + b) × (1 + a)
(a + b)´ b a ×
a´ b a × + b´ b a ×
= { conmutativa ×, inverso × }
0 × b + 0 × a
= { dominación × }
La demostración para n variables se realizaría de la siguiente forma:
. .. + + + c b a
= { Sea p = b + c+ ... }
= { De Morgan (2 variables) }
= { Deshaciendo }
a × . .. + + c b
= { repitiendo el proceso anterior hasta sacar todas las variables }
... × × × c b a
6.3. Puertas Lógicas
Un circuito digital es un circuito electrónico cuyas entradas y salidas sólo pueden tomar dos
niveles distintos de tensión. Desde el punto de vista del diseño, estos niveles de tensión se representan
como 1 (verdadero) ó 0 (falso). Un circuito combinacional se caracteriza por ser un sistema sin memoria:
el valor de las salidas en cada instante depende sólo del valor de las entradas en ese momento.
Un circuito de estas características puede representarse analíticamente, mediante una función
booleana, o gráficamente, mediante un diagrama de puertas lógicas. En estos diagramas se representan
las entradas, las salidas, las operaciones o puertas lógicas y sus conexiones.
Las diferentes conectivas pueden representarse mediante las siguientes puertas lógicas.
Puerta NO (Inversor)
Puerta XOR (O-Exclusiva)
a b ⊕
Mediante la utilización de puertas NAND ó NOR pueden implementarse el resto de operaciones. A modo
de ejemplo, se muestra cómo se implementa mediante puertas NAND las operaciones b a b a a × + , ,
= { idempotencia ×}
a a a × ·
= { involución }
= { De Morgan + }
= { { involución }
6.4. Funciones Booleanas
Definición 25. Una variable booleana es una variable que toma únicamente dos valores 0 ó 1.
Definición 26. Una función Booleana es una expresión algebraica que relaciona variables Booleanas por
medio de las operaciones +, ×, y −.
Ejemplo. 32: ) ( ) ( ) , , ( c b a c b a c b a f + × + × + ·
Definición 27. Un término canónico de una función booleana f es una expresión formada por el producto
(o la suma) de todas las variables de f en su forma directa o inversa. Cuando el término canónico es un
producto, se conoce como MINTERM o producto canónico. Cuando es una suma, se conoce como
MAXTERM o suma canónica.
Ejemplo.33 : c ab es un producto canónico de f(a,b,c), mientras que d c b a + + + es una suma canónica
de la función f(a,b,c,d)
Una función de n variables tiene a lo sumo 2
sumas canónicas y 2
productos canónicos distintos.
Para representar los términos canónicos de una función se utiliza el siguiente convenio: se asigna un 1 a
las variables en forma directa y un 0 a las variables en forma inversa. Cada término se representa utilizando
el valor decimal de la combinación binaria resultante.
Ejemplo. 34
6 0110 ≡ ≡ d bc a
9 1001 ≡ ≡ + + + d c b a
Definición 28. Una función está en forma canónica si es una suma de productos canónicos o un producto
de sumas canónicas.
Cuando la función es una suma de productos canónicos, se utiliza el símbolo ∑, mientras que para un
producto de sumas canónicas se utiliza el símbolo ∏.
Ejemplo. 35 : A continuación se presentan dos funciones en forma canónica:
) 0 , 6 , 2 ( ) , , ( c b a c ab c b a c b a f
) 7 , 5 , 0 ( ) )( )( ( ) , , ( c b a c b a c b a c b a g
Teorema 20. Toda función Booleana puede expresarse como:
( ) ( ) ,...) , , 1 ( ( ,...) , , 0 ( ,...) , , (
,...) , , 0 ( ...) , , , 1 ( ...) , , , (
c b f a c b f a c b a f
Puesto que una función booleana trabaja únicamente con variables Booleanas y estas variables sólo
pueden tomar los valores 0 ó 1, es suficiente demostrar la igualdad para a = 0 y luego para a = 1
1.- Sea a = 0
a ´ f(1,b,c...) + a × f(0,b,c...)
= { a = 0, a = 1 }
0´ f(1,b,c...) + 1× f(0,b,c...)
= { neutro ´, dominación ´ }
0 + f(0,b,c...)
f(0,b,c...)
= { a = 0 }
f(a,b,c...)
2.- Sea a = 1
= { a = 1, a = 0 }
1´ f(1,b,c...) + 0× f(0,b,c...)
f(1,b,c...)+ 0
f(1,b,c...)
= { a = 1 }
La otra igualdad se demuestra por dualidad
Multiplicando (o sumando) las expresiones anteriores por a (ó a ) se obtienen las siguientes igualdades:
a × f(a,b,c...) = a × f(1, b, c...)
a × f(a,b,c...) = a × f(0, b, c...)
a + f(a,b,c...) = a + f(0, b,c...)
Las anteriores igualdades tienen una aplicación importante para la simplificación de funciones
Ejemplo 36: La f(a,b,c,d)= abc + a (a × b + a × c + a × b × c ) puede simplificarse, utilizando la segunda
igualdad, resultando en:
abc + a (a × b + a × c + a × b × c )
= {a f(a,b,c...) = a f(0,b,c....) }
abc + a ( 0 × b + 0 × c + 0 × b × c )
= { neutro ×, 0 =1 }
abc + a ( 0 + 1× c + 0)
= { neutro +, neutro × }
abc + a c
Teorema 21. Toda función lógica puede transformarse en una función equivalente en forma canónica.
= { Teorema 20, sacando a}
= { Teorema 20, sacando b }
a ´ (b ´ f(1,1,c...) +b × f(1,0,c...) ) + a × (b ´ f(0,1,c...) + b × f(0,0,c...))
a ´ b ´ f(1,1,c...) +a ´ b × f(1,0,c...) + a × b ´ f(0,1,c...) + a × b × f(0,0,c...)
= ...{ repitiendo el proceso con el resto de variables }
a ´ b ´ c´ f(1,1,1...) + a ´ b ´ c × f(1,1,0...) +
a ´ b ´ c´ f(1,0,1...) + a ´ b ´ c × f(1,0,0...) +
a ´ b ´ c´ f(0,1,1...) + a ´ b ´ c × f(0,1,0...) +
a ´ b ´ c´ f(0,0,1...) + a ´ b ´ c × f(0,0,0...)
Las expresiones f(...) toman valores 0 ó 1 dependiendo de la función particular. Cuando toman valor 1,
el término canónico correspondiente permanece, mientras que si toman valor cero, el término desaparece.
Con lo cual, cualquier función puede expresarse en forma canónica.
La expresión de producto de sumas, dual de la anterior, sería:
f(a,b,c...) =
( a + b + c + f(0,0,0...)) ´ ( a + b + c + f(0,0,1...)) ´
( a + b + c + f(0,1,0...)) ´ (a + b + c + f(0,1,1...)) ´
( a + b + c + f(1,0,0...)) ´ ( a + b + c + f(1,0,1...)) ´
( a + b + c + f(1,1,0...)) ´ ( a + b + c + f(1,1,1...))
Obsérvese que en producto de sumas, los términos canónicos permanecen cuando la función toma valor
cero y desaparecen cuando toma valor 1. Además, los términos no corresponden de forma directa, sino
que cuando la variable está en forma directa, le corresponde un 0 y cuando está en forma inversa, un 1.
El teorema anterior ofrece un método para obtener la expresión canónica de una función a partir de la tabla
Suma de productos: Toman términos en los que la función vale 1 numerando de arriba abajo
Producto de Sumas: Tomar términos en los que la función vale 0 numerando de abajo a arriba
Ejemplo 37. A partir de la siguiente tabla de verdad, expresar en forma de suma de productos y producto
de sumas:
f(a,b,c)=∑
(2,5,6,7)= abc c ab c b a c b a + + +
f(a,b,c)=∏
(3,4,6,7)= ) )( )( )( ( c b a c b a c b a c b a + + + + + + + +
En ocasiones, desea obtenerse la expresión canónica de una función definida mediante una expresión
algebraica. Para ello, se transforma en suma de productos (o producto de sumas) y se multiplica (o suma)
cada término no canónico por la suma (o producto) de las variables que faltan y sus inversas.
Ejemplo 38: Se desea obtener la expresión canónica de f(a,b,c)=a ( b + c) + c
a ´ ( b + c) + c
a ´ b + a × c + c
= { neutro × , inverso + }
a ´ b × (c + c ) + a × c × (b + b ) + c × (a +a ) (b + b )
= { distributiva × , conmutativa ×}
a´b ×c + a´b × c + a×b×c + a´b ×c + a´b´ c +a ´ b´ c + a´b ´ c +a ´b ´ c
= { idempotencia +, conmutativa + }
a ´b ´ c + a ´ b´ c + a´b × c + a´b ×c + a × b × c
= { convenio }
(1,3,4,5,7)
En producto de sumas, el procedimiento sería:
(a + c) × ( b + c + c)
= { idempotencia }
(a + c) × ( b + c)
= { neutro +, inverso × }
(a + c + b× b ) × ( b + c + a × a )
= { distributiva +, conmutativa + }
(a + b + c)× ( a + b + c)× (a + b + c)×( a + b + c)
= { idempotencia ×, conmutativa }
( a + b + c) × ( a + b + c) × (a + b + c)
En el diseño de circuitos, se utilizan los siguientes pasos:
- Especificación del circuito
- Expresión analítica (normalmente, en forma de Tabla de verdad)
- Implementación del diseño.
En estos apuntes se tratan los tres primeros pasos, dejando las técnicas de implementación a otros
libros especializados. En cuanto a la simplificación, existen diversos métodos dependiendo del tipo de
puertas lógicas disponibles. Uno de los métodos de simplificación más comunes consiste en la aplicación
reiterada del siguiente teorema de simplificación
Teorema 22 (Simplificación) a ´ b´ c´ ... + a ´ b´ c´ ... = b× c× ...
(a + b + c + ...) × ( a + b + c + ...) = b + c + ... [Dual]
a ´ b´ c´ ... + a ´ b´ c´ ...
(a + a ) × b× c× ...
1 × b× c× ...
b× c× ...
Definición 29: Dos términos son adyacentes si sólo difieren en el valor de una variable. Su representación
binaria sólo diferirá en un bit.
A partir del teorema de simplificación, dos términos adyacentes pueden agruparse eliminando la variable
respecto a la que difieren y quedando únicamente la parte común.
Los principales métodos de simplificación reiteran este proceso de agrupamiento hasta obtener una
expresión que ya no contenga más términos adyacentes.
Ejemplo 39. d b f d c b a d c b a cd b a cd b a f
d c b cd b
4 4 3 4 4 2 1 4 43 4 42 1
Utilizando las representaciones binarias de los términos canónicos, los agrupaciones anteriores serían:
Grupos 11 - 1011
3-11 - X011
1-9 - X001
1-3-9-11 - X0X1 = d b
Uno de los métodos más utilizados para funciones de menos de 6 variables es el método de Karnaugh que
permite visualizar los términos adyacentes en una cuadrícula. Sin embargo, para funciones de un mayor
número de variables, el método algebraico más general es el método de Quine-McCluskey.
Es un método gráfico que visualiza los términos adyacentes en cuadrículas intentando que dos
términos adyacentes estén próximos entre sí. Los pasos del método son:
1. Construir una tabla de 2
casillas, siendo n el número de variables de la función. Cada casilla
corresponderá a un término canónico, producto o suma. Cada casilla se etiqueta con el término
asociado intentando que los términos adyacentes estén próximos entre sí. Cuando esto no es
posible (funciones de más de tres variables) se disponen los términos en los límites de la tabla
y se supone que los términos de un límite son adyacentes a los del límite opuesto. A
continuación aparecen las tablas para funciones entre 2 y 5 variables con el número decimal
asociado a los términos canónicos.
2 variables, f(a,b)
3 Variables, f(a,b,c)
4 Variables, f(a,b,c,d)
5 Variables, f(a,b,c,d,e)
Son cuadros adyacentes:
- Los que tienen un lado común.
- Los de la fila superior con los respectivos de la fila inferior.
- Los de la columna de la izquierda con los respectivos de la columna derecha.
- Los que están en la misma posición en ambas tablas (5 variables)
Ejemplo 40 Los términos adyacentes al 10 son 8,11, 14, 2, 26.
Los términos adyacentes al 13 son: 12, 5, 15, 9, 29.
2. En el caso de la expresión canónica en forma de suma de productos, las casillas asociadas a
términos que aparecen en ella se completan con 1 y el resto se dejan en blanco. O lo que es lo
mismo, aquellas casillas etiquetadas con una entrada de la tabla de verdad para la cual la
función toma el valor 1 se cubren con unos y el resto se deja vacío. Si la expresión está dada
en forma de productos de sumas las casillas se completan con 0 en vez de 1. Esta tabla es lo
que se conoce como mapa de Karnaugh de la función.
3. Proceso de simplificación. Se realizan agrupamientos reiterados de términos adyacentes hasta
que todos los términos hayan sido agrupados. Los grupos deben contener el mayor número
posible de términos (el número de términos en cada grupo será siempre potencia de 2).
4. Construir la expresión reducida. Por cada agrupamiento se obtiene una expresión formada por
las variables comunes a los términos adyacentes.
Nota 1: Para construir grupos mayores pueden utilizarse casillas que ya han sido previamente agrupadas.
Nota 2: Algunas funciones pueden agruparse de varias formas. En dichos casos, existe más de una
Ejemplo 41. Simplificar la función f(a,b,c,d)= ∑
(2,3,5,7,10,11,15)
El cuadro de Karnaugh correspondiente es:
00 0 1 1 3 1 2
01 4 1 5 1 7 6
11 12 13 115 14
10 8 9 111 1 10
Grupos 3 - 0011
3-7 - 0X11
15-11 - 1X11
3-7-15-11 - XX11 = cd
2-3 - 001X
10-11 - 101X
2-3-10-11 - X01X = c b
5-7 - 01X1 = bd a
El resultado es: cd c b bd a d c b a f + + · ) , , , (
Para simplificar en forma de producto de sumas, es necesario transformar la forma canónica a
producto de sumas. Para ello, puede construirse la tabla de verdad y tomar los elementos de valor cero
numerando de abajo a arriba. El resultado sería: f(a,b,c,d)= ∑
(1,2,3,6,7,9,11,14,15)
00 0 0 1 0 3 0 2
01 4 5 0 7 0 6
11 12 13 015 014
10 8 0 9 011 10
Grupos 1 - 0001
1-3 - 00X1
9-11 - 10X1
1-3-9-11 - X0X1 =
6-7 - 011X
2-3-6-7 - 0X1X = c a+
14-15 - 111X
6-7-14-15 - X11X = b+c
Resultado: ) ( ) ( ) ( ) , , , ( d b c b c a d c b a f + × + × + ·
Existen funciones que no están totalmente definidas, llamadas funciones incompletas. Las razones son:
1. Combinaciones de entrada imposibles, pudiendo ser su valor de salida 1 ó 0 indistintamente.
2. Con salidas inhibidas: el valor de salida es indiferente.
En la forma canónica de la función se representan de forma separada los términos indefinidos del resto.
Los términos indefinidos se agrupan mediante el símbolo ∅.
Ejemplo 42. Sea f(a,b,c,d) = ∑
(1,3,10,11)+∑
(0,2,4,13)
En la minimización de funciones incompletas los valores indefinidos se representan mediante X y
actúan como comodines. No es necesario agruparlos, pero, si al agruparlos se obtiene un grupo mayor, se
pueden agrupar.
00 X 0 1 1 1 3 X2
01 X4 5 7 6
11 12 X13 15 14
Grupos 0 - 0000
0-1 - 000X
0-1-2-3 - 00XX = b a
2-3-10-11 - X01X =
Resultado: b a c b d c b a f + · ) , , , (
Lógica Proposicional Ejercicios
Los siguientes ejercicios se han recopilado de diversas fuentes. Una de las fuentes fundamentales,
ha sido el "Boletín de Ejercicios" ofrecido en la asignatura "Lógica Informática" de la Escuela Universitaria
de Ingeniería Técnica Informática de Gijón.
[1] Formalizar las siguientes expresiones:
a) q si p
b) p pero q
c) como mínimo p
d) p no obstante q
e) q necesario para p
f) q suficiente para p
g) p a pesar de q
h) no p a menos que q
i) p sólo si q
j) p sin embargo q
k) p suficiente para q
l) p siempre que q
m) a veces p, siempre q
n) p a no ser que q
[2] Formalizar los razonamientos:
" Si el resultado obtenido es superior al previsto en 5 unidades, será debido a no haber realizado
el proceso a la temperatura adecuada o a la existencia de errores en los cálculos finales."
" El análisis realizado, innecesario si nos dejamos llevar por la precipitación, se torna necesario si
nos paramos a reflexionar sobre el mensaje que se pretende transmitir."
" El cáncer no logrará curarse a no ser que se logre determinar su causa y se consiga encontrar
fármacos adecuados o bien para prevenirlo o para curarlo."
[3] Simplificar mediante Karnaugh las siguientes funciones lógicas:
a) x xy y + +
b) ( ) xy xyz y x z y z + + + +
c) wx xy yz zw w xyz w x yz + + + + +
d) wxy z wxyz wxyz wxyz w xyz w xyz w x y z wxyz wxy z wxyz + + + + + + + + +
e) vw x y xz v xz wy x z vy ( ) ( ( )) + + + + +
[4] Demostrar las siguientes propiedades de la función lógica O-exclusiva:
c) Existencia de elemento neutro e tal que x e x ⊕ ·
d) Existencia de Inverso (A todo elemento x se le puede hacer corresponder un elemento $ x tal que
x x e ⊕ · $
e) Distributiva del Producto respecto a la O-exclusiva: x y z xy xz ( ) ⊕ · ⊕
f) que mediante la O-exclusiva y la función AND se pueden realizar las otras dos operaciones
fundamentales del álgebra de Boole: negación y suma (OR).
Nota: Calcular el valor de 1⊕ x y de ( )( ) ( ) 1 1 1 ⊕ ⊕ ⊕ x y
g) que x y x y ⊕ · ⊕
[5] Una función de tres variables f(a,b,c) debe tomar el valor cero cuando la variable b esté a uno y la
variable a no está en estado uno. En los demás casos posibles debe estar en estado uno.
a) Realizar la tabla de verdad de la función.
b) Obtener las formas canónicas en forma de suma de productos y producto de sumas.
c) Minimizar dichas expresiones.
[6] Obtener la expresión algebraica mínima de una función lógica de cuatro variables que toma el
valor uno cuando el número de variables que están en estado uno es superior al de las que se encuentran
en estado cero. Nunca pueden estar más de tres variables en estado uno. Realizar la expresión obtenida
con puertas NOR y NAND.
[7] Formalizar utilizando las conectivas { ¦ ¬ ∨ ∧ , , el siguiente enunciado:
" Si p entonces q y, en caso contrario, si p1 entonces q1 y, en caso contrario r1."
[8] Formalizar el siguiente enunciado donde hemos notado "si p entonces q y en caso contrario r" de
p q r → ;
- Normalizar dicho enunciado.
- Estudiar la validez de la siguiente fórmula en la que se emplea la notación anterior:
( ) p p r r s r w s p q t q t r w → ∨ ∨ ∧ → ¬ → ∧ ¬ ∧ ∧ → → ¬ → ; ;
[9] Determinar la validez de las siguientes fórmulas:
¬ ∧ ∨ ∨ ¬ → → ∨ → → p q p q p q r p r
b) ( ) ( ) p q p p ∧ → →
c) ( ) ( ) ( ) ¬ → → ∧ ¬ ∨ p q p q r
[10] Obtener la FND de:
a) ( ) ( ) p p q p q → → ∨ ∨
b) ( ) ( ) ¬ ∨ ¬ ∧ ¬ ∨ p q r s
[11] Obtener la FNC de:
a) ( ) ¬ → ∨ ∨ p q p q
b) ( ) ( ) p q r s → → →
[12] Probar, usando el algoritmo de resolución, la validez de los siguientes razonamientos:
a) { ¦ p q q r p r → → ⇒ , ,
b) ( ) ( ) { ¦
p q r s p s q → ¬ ∨ ∧ ¬ ⇒ ¬ , ,
[13] Compruébese si los siguientes razonamientos son correctos o no:
a.-" Si Antonio ganó la carrera, entonces Baltasar o Carlos fueron los segundos. Si Baltasar fue
segundo, entonces no ganó Antonio. Si Demetrio fue segundo, no lo fue Carlos. Antonio ganó la
carrera. Por tanto, Demetrio no fue segundo".
b.-" No llora, ríe. Si no llora, ríe sólo si tiene un juguete. Nunca tiene un juguete cuando se está riendo
si no come un caramelo. Luego come un caramelo."
c.-" Juan quiere a María si y sólo si María quiere a Juan y promete casarse con él. María no quiere a
Juan si Juan no quiere a María. María promete casarse con Juan si y sólo si Juan promete casarse con
María. Por tanto, Juan quiere a María y María no quiere a Juan".
d.-" Si ha nevado será difícil conducir. Si no es fácil conducir llegaré tarde si no salgo temprano. Ha
nevado. Luego saldré temprano. "
e.-" Si no llueve salgo al campo. Si salgo al campo respiro. Por tanto, respiro si y sólo si no llueve."
f.-" Si un monte se quema algo tuyo se quema. Algo tuyo se quema si y sólo si eres descuidado. Si eres
descuidado no mereces que te feliciten. Por tanto si no mereces que te feliciten entonces es que un monte
se quema."
g.-" El Ministro de Economía y Hacienda ha hecho las siguientes declaraciones:
A la prensa: " Si los impuestos suben, la inflacción bajará si y sólo si no se devalúa la peseta."
A la radio: " Si la inflacción baja o si l a peseta no se devalúa, los impuestos no subirán."
A la tele: " O bien baja la inflacción y se devalúa la peseta, o bien los impuestos deben subir."
Como consecuencia, publica un informe en el que asegura: "Los impuestos deben subir, pero la
inflación bajará y la peseta no se devaluará."
¿ Fue consecuente con sus declaraciones a los medios de comunicación?."
h.-" Es suficiente whisky para que chocolate. Chocolate si y solo si jamón. No ginebra a menos que
chocolate. Whisky. ¿ Es posible afirmar: (1) que bebió ginebra? (2) que no tomó chocolate?"
i.-" Si no especifico las condiciones iniciales mi programa no comenzará. habré programado un ciclo
infinito solo si mi programa no termina. Basta que el programa no comience o no finalice para que falle.
De ahí que sea necesario no solamente especificar las condiciones iniciales sino también no programar
un ciclo infinito para que el programa no falle."
j.-"Si 25 divisiones son suficientes, el general ganará la batalla; por otra parte, o se suministran 3 alas
de apoyo aéreo táctico, o el general no ganará la batalla. Además, no es cierto que sean suficientes 25
divisiones y que se vayan a suministrar 3 alas de apoyo aéreo táctico. Coclusión: no son suficientes 25
divisiones."
[14].-Le digo a un amigo:
Cuando salgo sin paraguas, llueve.
Cuando está despejado, no llueve.
Según el hombre del tiempo, mañana estará despejado o hará niebla.
De todos modos saldré sin paraguas.
Entonces mi amigo responde: Entonces mañana, además de llover, habrá niebla. ¿Cómo lo supo?
[15] Don Juan Tenorio, hizo las siguientes declaraciones, con respecto a las doncellas Inés, Juana y
María, que le costaron la vida. ¿Quién o quiénes son las asesinas?.
" Amo a la última de las tres"
" Si amo a Inés pero no a María, entonces también amo a Juana"
" O amo a María y a Juana o no amo a ninguna"
" Si amo a María, entonces amo a Inés"
(se supone que la asesina era aquélla a la que Don Juan no amaba)
[16].-En un juicio el fiscal argumenta:
" Si el acusado es culpable, entonces tenía un testigo".
A ello, el abogado defensor respondió inmediatamente:
" Eso es falso".
El acusado decidió cambiar de abogado defensor. ¿ Es lógico?.
[17].-Analizar la coherencia lógica - no teológica - del siguiente razonamiento:
- Si Dios existe es todo amor y omnipotencia.
- Si Dios es incapaz de erradicar el sufrimiento del mundo entonces no es omnipotente.
- Dios no es amor o está dispuesto a erradicar el sufrimiento del mundo.
- Dios es capaz de erradicar el sufrimiento del mundo y está dispuesto a ello solo si no existe
sufrimiento en el mundo.
- Existe sufrimiento en el mundo.
[18] Si la Bella Durmiente despierta, los habitantes del castillo también lo harán. Si el príncipe la besa,
despertará. El príncipe la besará si está de buen ver. O la besa o no se despierta nadie. Como esto es un
cuento, la princesa, a pesar de llevar 100 años dormida sigue de muy buen ver. Si la princesa se
despierta se casarán, vivirán felices y comerán perdices si no estamos en veda. Estamos en veda.
¿ Se casan? ¿ Son felices? ¿ Comen perdices?.
[19] Los dos carteles siguientes están colgados respectivamente a la puerta de las habitaciones 1 y
2. Uno dice la verdad y otro miente. Sabiendo que en la misma habitación no puede haber una dama y un
tigre y que puede haber dos damas y dos tigres, se pide decidir lógicamente qué puerta se debe abrir para
liberar a la dama si es que existe. Ambas habitaciones están ocupadas.
EN ESTA HABITACION HAY UNA DAMA Y EN LA OTRA UN TIGRE.
EN UNA DE ESTAS HABITACIONES HAY UNA DAMA Y EN UNA DE ESTAS HABITACIONES HAY
- Suponiendo que los dos carteles siguientes dicen ambos la verdad o mienten ambos. Deducir en qué
habitación hay una dama, sabiendo, como antes, que puede no haberla.
HAY UN TIGRE EN LA OTRA HABITACION
[20] Discurso sobre los estudios de Informática en clase de Lógica:
Es hora de que recapacitemos sobre los estudios de informática en vísperas del asentamiento
de la titulación en nuestra Universidad. Se sabe que si los ordenadores hablasen los informáticos no
existirían. Por otra parte, en la última reunión del Consejo de Universidades, éste afirmó que: "...la
Universidad titulará informáticos mientras los ordenadores no hablen ..."; afirmación que nos parece
muy correcta, si bien lo cierto es que los ordenadores no hablan pero los informáticos existen.
A la vista de todo ello nos preguntamos: ¿Es, por tanto, coherente que la Universidad expida
títulos de informática en la actualidad?.
Lógica proposicional Soluciones
[1] a) p q → h) p q →
b) p q ∧ i) p q →
c) p j) p q ∧
d) p q ∧ k) p q →
e) p q → l) q p →
f) q p → m) ( ) p p q q ∨ ¬ ∧ ≡
g) p q ∧ n) ¬ → q p
[2] p = Resultado obtenido menor al previsto en 5 unidades.
q = Haber realizado el proceso a la temperatura adecuada.
r = Existencia de errores en los cálculos finales.
( ) ¬ ∨ → q r p
p = Análisis realizado es necesario.
q = Nos dejamos llevar por la precipitación.
r = Nos paramos a reflexionar sobre el mensaje que se pretende transmitir.
( ) ( ) q p r p → ¬ ∧ →
p = El cáncer logrará curarse.
q = Se logra determinar su causa.
r = Se consigue encontrar fármacos adecuados para prevenirlo.
s = Se consigue encontrar fármacos adecuados para curarlo.
( ) ( ) ( ) ( ) ¬ ∧ ∨ → ¬ ≡ → ∧ ∨ q r s p p q r s
[3] a) x y +
b) x y z + +
c) xw xz wy + +
d) Habría tres posibles soluciones
xy w z xyz wyz
xy w z xyz wxz
xy w z w xz wyz
e) v xyz vwxz vwx vwy + + +
[4] Para realizar las demostraciones se parte de que x y xy xy ⊕ · + , y se desarrollan las expresiones
resultantes hasta llegar a la demostración deseada. A continuación se presentan los primeros pasos de la
demostración de asociatividad:
( ) ( ) ( ) ( ) ( ) x y z x y z x y z xy xy z xy xy z xy z xyz x yz xyz ⊕ ⊕ · ⊕ + ⊕ · + + + · · + + + L
Si desarrollásemos ( ) x y z ⊕ ⊕ obtendríamos la misma expresión, con lo cual habríamos demostrado la
Las demás demostraciones se realizarían de forma similar.
[5] La función, minimizada sería a b +
[6] La expresión mínima sería: bcd acd abd abc + + + .
[7] ( ) ( ) ( ) ( ) ( )
p q p p q p r → ∧ ¬ → → ∧ ¬ → 1 1 1 1
[8] ( ) ( ) p q p r → ∧ ¬ →
- Forma normal conjuntiva: ( ) ( ) ¬ ∨ ∧ ∨ p q p r
- El razonamiento NO es válido, pues podemos encontrar varias interpretaciones que lo hagan Falso, por
ejemplo, r=F, w = F, q = F, p = V, s = V, t= V.
[9] a) NO es válida, ejemplo p = V, q = V, r = F
b) SI es válida.
c) NO es válida, ejemplo p = V, q = V, r = F
[10] a) Al operar quedaría: ¬ ∨ ¬ ∨ ∨ ≡ p p q p V
b) ( ) ( ) ¬ ∧ ∧ ¬ ∨ ¬ ∧ ∧ p q r p q s
[11] a) p q ∨
b) ( ) ( ) ¬ ∨ ∨ ∧ ¬ ∨ p q s r s
[12] En ambos casos se llega a la cláusula vacía ⇒ Razonamiento correcto.
[13] a) SI es válido, Antonio ganó la carrera.
b) ES válido, come un caramelo.
c) El razonamiento NO es válido, ya que puede darse el caso de que ninguno de los dos quiera al
otro, y las premisas serían ciertas, pero la conclusión Falsa.
d) El razonamiento NO es válido porque puede darse el caso de NO salir temprano y llegar tarde
habiendo nevado y siendo difícil conducir. Cumpliéndose todas las premisas.
e) NO es válido, puedo salir al campo, lloviendo y respirar. Luego no se deduce que respire si y
solo si no llueve.
f) NO es válido.
g) NO es correcto.
h) NO se puede deducir ninguna de los dos, ni que bebiese Ginebra ni que no tomase chocolate.
i) El razonamiento ES correcto.
j) El razonamiento ES correcto.
[14] Ambas expresiones se deducen lógicamente suponiendo que todas las frases sean
Verdaderas, se puede comprobar que sólo existe esa posibilidad.
[15] Ninguna de ellas era la asesina, pues las amaba a las tres.
[16] Si es Falsa la sentencia "Si el acusado es culpable entonces tenía un testigo", por la
tabla de verdad de la implicación, el antecedente es Verdadero y el consecuente Falso, luego el
antecedente es Verdadero, es decir, el acusado sería culpable.
[17] El razonamiento es correcto en términos lógicos.
[18] Se casan, viven felices, pero no comen perdices porque estamos en veda.
[19] - La única forma de que un cartel diga la verdad y otro mienta es que el Cartel 1 mienta y el Cartel 2
diga la verdad. Con lo cual habría un tigre en la habitación 1 y una dama en la habitación 2.
- La única posibilidad es que los dos carteles digan la verdad y habría una dama en la habitación 2
y un tigre en la habitación 1.
[20] Sí, se sigue que la universidad expenda títulos de Informática a partir de las premisas. El
razonamiento es correcto.
Lógica proposicional Bibliografía
[Abramsky, 92] S. Abramsky, D.M. Gabbay, T.S. Maibaum
Oxford Science Publications (1992)
[Ben-Ari, 93] M. Ben-Ari
Prentice Hall Intl. (1993)
[Birkhoff, 70] G. Birkhoff, T. C. Bartee
McGraw-Hill (1970)
[Burke, 96] E. Burke, E. Foxley
Prentice Hall Intl. (1996)
[Dijkstra, 91] E. W. Dijkstra, C. S. Scholten
[Fitting, 96] M. Fitting
Springer-Verlag, 2
[Genesereth, 87] M. R. Genesereth, N.J. Nilsson
Morgan Kaufmann Publishers, Inc. (1987)
[Grassmann, 96] W. K. Grassmann, J. Tremblay
Prentice-Hall (1996)
[Gries, 94] D. Gries, F. B. Schneider
[Kelly, 97] J. Kelly
[Maier, 88] David Maier, David S. Warren
The Benjamin/Cummings Publishing Company, Inc. (1988)
[Mandado, 88] E. Mandado
Ed. Marcombo (1988)
[Sperschneider, 91] V. Sperschneider, G. Antoniou
Addison-Wesley Publishing Company (1991)
[Whitesitt, 61] J. E. Whitesitt
Addison-Wesley (1961)
Lógica proposicional Indice
Absorción, 24
Alfabeto, 2
álgebra de Boole, 21
Álgebra de Boole bivaluada, 22
Algoritmo de resolución proposicional,
árbol de resolución, 16
árbol semántico, 6
Asociativa, 24
circuito combinacional, 27
circuito digita, 26
circuitos digitales combinacionales, 21
cláusula, 8
cláusula cabeza, 15
cláusula Horn, 9
cláusula inicial, 15
cláusulas resolubles, 9
Commutativa, 22
Completud del Algoritmo de Resolución
Proposicional, 13
Conmutativa, 22
consecuencia lógica, 5
correcto, 5
De Morgan, 26
Distributiva, 22
Dominación, 23
Elemento inverso, 22
Elemento neutro, 22
equivalencia lógica, 4
Estrategias de resolución, 13
forma canónica, 28
Forma Clausal, 9
Forma Normal Conjuntiva, 8
Forma Normal Disyuntiva, 8
Formas Normales, 8
Fórmula Insatisfacible, 4
Fórmula Satisfacible, 4
Fórmula Válida, 3
función Booleana, 27
Idempotencia, 23
interpretación, 3
Involución, 25
literal puro, 14
MAXTERM, 28
MINTERM, 28
nodo de fallo, 6
nodo de inferencia, 12
nodos de éxito, 6
Principio de dualidad, 23
producto canónico, 28
pruebas subordinadas, 19
razonamiento, 5
regla de resolución, 9
Resolución Lineal, 15
Resolución proposicional, 8
resolvente, 9
resolvente de entrada, 15
Semántica, 3
Sintaxis, 2
subsunción, 14
suma canónica, 28
tabla de verdad, 6
tautología, 14
Tautología, 3
teoría de la prueba, 18
teoría semántica, 18
término canónico, 27
Unicidad del complementario, 25
valor de una fórmula, 3
variable booleana, 27
Contenido Introducción...............................................................................................................1 1. Lenguaje de la Lógica Proposicional......................................................................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. Á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..............................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 de Subsunciones..............................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ó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..................................................................................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 de Karnaugh.....................................................36 Funciones incompletas ...................................................39 7. Ejercicios............................................................................................................40 8. Soluciones...........................................................................................................45 Bibliografía...............................................................................................................48 Indice.......................................................................................................................49
La lógica Proposicional pretende estudiar las frases declarativas simples (enunciados o proposiciones) que son los elementos básicos de transmisión de conocimiento humano. De manera informal, una proposición se define como una frase que puede ser considerada Verdadera o Falsa y que no se puede descomponer en otras frases Verdaderas o Falsas. Para relacionar las distintas proposiciones se utilizan las siguientes conectivas: Nombre de la conectiva Negación Representación ¬p Ejemplos de frases en las que aparece no p es falso p no es cierto p p yq p pero q p sin embargo q p no obstante q p a pesar de q o p o q o ambos al menos p o q como mínimo p o q si p entonces q p sólo si q q si p q cuando p q es necesario para p para p es necesario q p es suficiente para q para q es suficiente p no p a menos que q p es necesario y suficiente para q p si y sólo si q
Condicional (Implicación)
Bicondicional (Equivalencia)
El lenguaje de la lógica proposicional trabajará con los siguientes conjuntos de símbolos: Constantes: VF Variables o letras proposicionales: p, q, r, ... Símbolos de Conectivas: ¬∧ ∨ →↔ Signos de puntuación: ()
Las reglas de formación de frases en el lenguaje de la lógica proposicional (LPROP) son: 1.- Las constantes V (Verdadero) y F (Falso) pertenecen a LPROP 2. Las letras de proposición p,q,r,.. pertenecen a LPROP
3. Si A y B pertenecen a LPROP entonces ( ¬ A) , ( ¬ B ), ( A ∧ B ), ( A ∨ B ), ( A → B ) , ( A ↔ B ) pertenecen a LPROP 4. Sólo pertenecen a LPROP las fórmulas que cumplan los requisitos 1, 2 y 3. Con el fin de evitar el exceso de paréntesis se establece la siguiente jerarquía de prioridades: ¬ ∧ ∨ →↔ Con dicha tabla, la fórmula ¬p ∨ q → p ∧ r se reconocería como: ((¬p) ∨ q) → (p ∧ r)
La teoría semántica de la lógica proposicional trata de atribuir significados (Verdadero o Falso) a las distintas fórmulas del lenguaje. Dichos significados dependen del contexto particular en el que se utilice la fórmu la. Cada contexto se denomina Interpretación. Definición 1: Una interpretación de una fórmula F en lógica proposicional es una asignación de valores {V, F} a cada una de las letras proposicionales de F. El valor de una proposición p bajo una interpretación I se denota como VI ( p ) . Definición 2: Dada una fórmula F y una interpretación I, el valor de F bajo I (denotado por VI ( F ) ) es: ° Si F está formada por una proposición p, entonces VI ( F ) = V I ( p ) ° Si
I F es de la forma ¬G entonces V I ( F ) =   F si V I ( G ) = V
si V ( G ) = F
F es de la forma G ∧ H entonces V I ( F ) = 
V F
si V I ( G ) = V I ( H ) = V en caso contrario si V I ( G ) = VI ( H ) = F en caso contrario si V I ( G ) = V y V I ( H ) = F en caso contrario si V I ( G ) = V I ( H ) en caso contrario
F es de la forma G ∨ H entonces V I ( F ) = 
F V F 
F es de la forma G → H entonces V I ( F ) =  V F es de la forma G ↔ H entonces V I ( F ) =  F
Ejemplo 1: Sea la fórmula F = ( p → q) ↔ ¬q ∨ ¬p y la interpretación I que asigna V I ( p) = F y
V I ( q) = V
Definición 3: Una interpretación I es un modelo para una fórmula F si VI ( F ) =
Es posible establecer una clasificación de las fórmulas proposicionales en función de los valores que tomen bajo las diferentes interpretaciones, de esta forma una fórmula F se clasifica en: Válida ó Tautología: Todas las interpretaciones son un modelo (Para toda interpretación I, VI ( F ) = Satisfacible: Alguna interpretación es un modelo (Existe una interpretación I tal que VI ( F ) =
Por tanto.Lógica Proposicional Lenguaje de la Lógica Proposicional Insatisfacible: Ninguna interpretación es un modelo (No existe una interpretación I tal que VI ( F ) = V ) Una fórmula puede ser: satisfacible o insatisfacible. Dem: F es válida ⇔ { Def. las fórmulas válidas son un subconjunto de las satisfacibles. válida} ∀I VI(F)= V ⇔ { Def. Insat. W. Dijkstra [Dijkstra. comentarios para pasar de un paso a otro. Un tipo especial de fórmula satisfacible. el comentario recurre a la regla de Leibniz que dice lo siguiente: Si se cumple F(X) y X = Y entonces también se cumple F(Y) 5 . es aquella que toma siempre valor V (es válida). En este formato. las líneas i pares contienen los principales pasos de la m demostración y las líneas pares. Teorema 1: Una fórmula F es válida si y sólo si su negación ¬F es insatisfacible. } ¬F es Insatisfacible NOTA: A lo largo de estos apuntes se utilizará un formato lineal para las demostraciones promovido por E. En algunas ocasiones. 90]. Interpretación ¬ } ∀I VI(¬F) = F ⇔ { Def.
. si se sabe que X es válida. Válida } B es válida Con el teorema anterior.. ≡ } ∀I VI(A) = VI(B) ⇔ { Def. Complementario Idempotencia Commutativa Asociativa Distributiva De Morgan Doble Negación (Involución) A ∧ ( B ∨ A) ≡ A A∧F ≡ F A∧V ≡ A Contradicción A ∨ ( B ∧ A) ≡ A A∨V ≡ V A∨F ≡ A Medio Excluido A ∨ ¬A ≡ V A∨ A ≡ A A∧ B ≡ B ∧ A A ∧ ¬A ≡ F A ∧ ( B ∧ C) ≡ ( A ∧ B) ∧ C A ∨ ( B ∧ C ) ≡ ( A ∨ B) ∧ ( A ∨ C) ¬( A ∨ B) ≡ ¬A ∧ ¬B ¬¬ A ≡ A A∧ A ≡ A A∨ B ≡ B ∨ A A ∨ ( B ∨ C ) ≡ ( A ∨ B) ∨ C A ∧ ( B ∨ C ) ≡ ( A ∧ B) ∨ ( A ∧ C) ¬( A ∧ B) ≡ ¬A ∨ ¬B Teorema 3: Si A es válida y A ≡ B entonces B es válida Dem: A es válida ⇔ { Def. para demostrar que Z es válida se podrá utilizar el formato: X ≡ {.} Y ≡ {.Lógica Proposicional Equivalencia lógica 2. se cumple que VI ( A ) = VI ( B ) Teorema 2: A ≡ B si y sólo si la fórmula A↔B es válida Dem: A≡B ⇔ { Def. Leibniz } ∀I VI(B) = V ⇔ { Def.. Interpretación ↔ } ∀I VI(A↔B) = V ⇔ { Def. Válida } A↔B es válida El teorema anterior reduce la demostración de equivalencia entre fórmulas a la demostración de validez de una fórmula. Válida } ∀I VI(A) = V ⇔ {Si A≡B entonces ∀I VI(A) = VI(B). Equivalencia lógica Definición 4: Se dice que dos fórmulas A y B son equivalentes lógicamente (se denota por A ≡ B ó A ⇔ B ) si para toda interpretación I..} Z 6 . A continuación se presenta una tabla con una serie de equivalencias de uso común y de fácil demostración Supresión de Implicación: A → B ≡ ¬ A ∨ B Contraposición: A → B ≡ ¬B → ¬ A Supresión de Doble Implicación: A ↔ B ≡ ( A → B ) ∧ ( B → A) Absorción Elemento neutro E.
Válida } P1 ∧ P2 ∧.. De esa forma... P .. Razonamiento } ∀I Si V I (P1) = V I (P2) = ..Pn} ⇒ Q es correcto ⇔ { Def. Una estructura de la forma { P . P2 . P2 . Se dice que Q es consecuencia lógica del conjunto C de premisas (se denotará C ⇒ Q ) si toda interpretación que es un modelo de C es también un modelo de Q .L P } 1 2 n y sea Q una fórmula..∧ Pn → Q es válida 7 .. P2. Teorema 4: { P . Donde { P .Lógica Proposicional Consecuencia Lógica 3. Consecuencia Lógica Definición 5: Sea C un conjunto de fórmulas {P .. la conclusión. = V I (Pn) = V entonces V I (Q) = V ⇔ { Def.L Pn } es 1 1 el conjunto de premisas y Q. decir que Q es consecuencia lógica de unas premisas es equivalente a pensar que Q toma valor V en cualquier mu ndo en el que las premisas tomen valor V ). se podría considerar cada interpretación como un "posible mundo".∧ Pn) = V entonces V I (Q) = V ⇔ { Def. Es decir. Interpretación de Implicación } ∀I V I (P1 ∧ P2 ∧. Se dice que un razonamiento es correcto si la conclusión es consecuencia lógica de las premisas. .. P2 .LPn } ⇒ Q se denomina razonamiento.LPn } ⇒ Q es correcto si y sólo si P ∧ P2 ∧L∧ Pn → Q es válida 1 1 Dem: {P1. si para toda interpretación I se cumple que si V I ( P ) = V I ( P2 ) =L = V I ( Pn ) = V entonces 1 VI ( Q ) = V (Intuitivamente.∧ Pn → Q) = V ⇔ { Def. Interpretación de conjunción } ∀I Si V I (P1 ∧ P2 ∧..
para calcular el valor de verdad de la fórmula F = p→q ↔ ¬p∨q .Se Selecciona la primera letra proposicional p del conjunto LP . 3. Técnicas Semánticas de Estudio de Validez Proposicional 4. se forma el conjunto LP de letras proposicionales de la fórmula. nodos de éxito Ejemplo 2: Dada la fórmula (p→q) →(¬p→¬q).Si es posible asignar a F un valor {V. Inicialmente. se denominan nodos de fallo y los que la hacen verdadera. q=V y p=V. . q=F. Árboles Semánticos Definición 7: Un árbol semántico es una técnica similar a las tablas de verdad que puede simplificar la evaluación de algunas fórmulas.Repetir el procedimiento por cada uno de los dos nuevos nodos.. F} se etiqueta el nodo con dicho valor y se finaliza el tratamiento del nodo actual.contrario: .Se Borra p de LP. se obtiene el árbol semántico: p V q F ¬p ¬q V Como puede observarse.Se intenta evaluar la fórmula en el nodo actual. Seleccionando los literales por orden alfabético.Se Construyen dos ramas. Tablas de Verdad Definición 6: Una tabla de verdad es una representación en forma de árbol del valor de una fórmula en todas las posibles interpretaciones. este método tiene una complejidad exponencial que complica su utilización para fórmulas complejas 4.1. una correspondiente a p interpretado con valor V (identificada como p) y la otra correspondiente a p con valor F (identificada como ¬p ). la tabla de verdad consiste en representar las 4 posibles interpretaciones y evaluar la fórmula en dichas interpretaciones p F F V V q F V F V p→q ↔ ¬p∨q V V V V El número de posibles interpretaciones de una fórmula F es 2n donde n es el número de variables proposicionales de F. .-En caso. 8 .2. Definición 8: Los nodos del árbol semántico en los que el conjunto de significados atribuidos hasta ellos hacen Falsa la fórmula. Por tanto. 2. no ha sido necesario evaluar las interpretaciones p=V. Se construye un nodo inicial del árbol que se tomará como nodo actual y se aplica el siguiente procedimiento: 1. Por ejemplo..Lógica Proposicional Técnicas Semánticas de Estudio de Validez 4.
Es decir que: {A ↔ B.. Demostraciones por Contradicción Para demostrar que una fórmula F es válida por contradicción se realiza lo siguiente: 1. 2.Lógica Proposicional Técnicas Semánticas de Estudio de Validez 4. A ↔ B∧B ↔C → A↔ C V V V V V V 123 123 123 V 42443 V V3 14 12 V 4 F3 14444 244444 F Contradicción A ↔ B∧B ↔C → A↔ C F F F F F F 123 123 123 V 42443 V V 3 14 12 V 4 F3 14444 244444 F Contradicción 9 . A continuación se demuestra que la transitividad de la equivalencia lógica. puede concluirse que la fórmula es válida. Ejemplo 3. B ↔ C) ⇒ (A ↔ C) Para ello. En dicha demostración aparecen dos alternativas y.3. A continuación se demuestra que la fórmula ¬p∨¬q→¬(p∧q) es válida ¬ p ∨ ¬ q → ¬( p ∧ q ) V V V 3 { { 12V F F 1 24 4 3 1 24 4 V3 F 1 24 4F 3 V 42444 144 3 F Contradicción A la hora de evaluar una conectiva pueden aparecer varias alternativas.Se supone que existe una interpretación I tal que VI(F) = F y se intentan calcular los diversos valores de la fórmula. basta con demostrar que la fórmula (A↔B)∧(B↔C)→(A↔C) es válida. como se llega a contradicción por ambas. Conviene recordar que: Para poder asegurar que F es válida debe llegarse a contradicción por todas las alternativas Si no se llega a contradicción por alguna alternativa se puede decir que F no es válida Ejemplo 4..Si se llega a una contradicción: Entonces: En Caso Contrario: ¬∃I VI(F) = F ⇒ ∀I VI(F) = V ⇒ F es válida ∃I VI(F) = F ⇒ F no es válida Este tipo de demostraciones se suelen representar etiquetando la fórmula con valor F y evaluando posibles valores hasta que se llegue la contradicción.
1.4. sino un conjunto de cláusulas y el algoritmo chequea si son insatisfacibles. A ∧ ( B ∨ C ) ≡ ( A ∧ B) ∨ ( A ∧ C) A ∨ ( B ∧ C ) ≡ ( A ∨ B) ∧ ( A ∨ C) Puesto que las fórmulas resultantes de aplicar cada uno de los pasos anteriores mantienen la equivalencia. 2. Robinson en 1965. Antes de presentar el algoritmo de resolución. A↔B≡(A→B)∧ (B→A) Eliminar conectiva →. Se representa como ∧  ∨ lij  i =1 j =1  Ejemplo 5: La siguiente fórmula está en Forma Normal Conjuntiva: (¬p∨q) ∧ (¬p∨r∨¬s) ∧ p Definición 13: Una fórmula F está en Forma Normal Disyuntiva (FND) si es una disyunción de la forma m  ni  F1∨F2∨. Aplicar propiedades distributivas para eliminar las posibles conjunciones (disyunciones) dentro de disyunciones (conjunciones) obteniendo Forma Normal Conjuntiva (Disyuntiva).4. En muchas ocasiones se añaden otros tres pasos que simplifican la fórmula resultante: 6. A → B ≡ ¬ A ∨ B Introducir negaciones hasta que afecten a literales mediante las leyes de Morgan. se requiere el estudio de sistemas de re-escritura de términos que puede consultarse en [Abramsky. la fórmula obtenida será equivalente a la fórmula original. 4. Para demostrar formalmente que el algoritmo termina. Eliminar literales repetidos p∧ p≡p p∨ p≡p 8.Lógica Proposicional Técnicas Semánticas de Estudio de Validez 4. Definición 12: Una fórmula F está en Forma Normal Conjuntiva (FNC) si es una conjunción de la forma m  ni  F1 ∧ F2 ∧L∧ Fn donde cada Fi es una disyunción de literales.A. la fórmula resultante es equivalente a la fórmula original. se define qué es una cláusula y cómo transformar una fórmula en un conjunto de cláusulas mediante las formas normales.. En dicho caso se elimina la cláusula D (A ∨ B) ∧ A ≡ A 10 . n≥0 n≥0 ¬( A ∧ B) ≡ ¬A ∨ ¬B ¬( A ∨ B) ≡ ¬A ∧ ¬B 4. Puesto que estos pasos mantienen la equivalencia y dado que la equivalencia cumple la propiedad transitiva (ejemplo 4). Formas Normales Definición 9: Una fórmula F es una conjunción si es de la forma F1 ∧ F2 ∧L∧ Fn Definición 10: Una fórmula F es una disyunción si es de la forma F1 ∨ F2 ∨L∨ Fn Definición 11: Un literal es una proposición ( p ) o una proposición negada ( ¬p) . Eliminar conectiva ↔. Eliminar subsunciones. 92]. ¬¬ A ≡ A 5. Se representa como ∨  ∧ lij  i =1 j =1  Ejemplo 6: La siguiente fórmula está en Forma Normal Disyuntiva: (p ∧ ¬q ∧ r) ∨ ¬p ∨ (r ∧ ¬s) Ejemplo 7: Obsérvese que la fórmula ¬p está a la vez en FNC y FND Teorema 5: Toda fórmula de la lógica de proposiciones puede ser transformada en una fórmula lógicamente equivalente a ella en Forma Normal Conjuntiva (Disyuntiva). Dem: La demostración consiste en indicar los pasos del algoritmo de transformación a forma normal conjuntiva. Resolución Proposicional El método de resolución es un algoritmo fácilmente mecanizable propuesto por J. Eliminar negaciones múltiples. La entrada del algoritmo no es una fórmula. Eliminar conjunciones/disyunciones con un literal y su opuesto. 3.. Una subsunción se produce cuando una conjunción (o disyunción) C está incluida en otra D. (p∧ ¬p ∧ X) ∨ Y ≡ Y (p∨ ¬p ∨ X) ∧Y ≡ Y 7.∨Fn donde cada Fi es una conjunción de literales. Los pasos de transformación son: 1.
Definición 15: Una fórmula está en Forma Clausal si se expresa como un conjunto de cláusulas. p} en Forma Clausal y su valor es Definición 16: Una cláusula sin literales se denomina cláusula vacía. finalmente. si no existe literal positivo (no existe A) entonces se denomina objetivo y. Si n=0. Puesto que se utiliza una sola regla. si n>0 y existe literal positivo. 4.4. se pueden emplear los siguientes pasos: ¬(p→q)↔p∨r ≡ { Eliminación ↔ } (¬ (p → q) → p ∨ r) ∧ ( (p ∨ r) → ¬(p → q)) ≡ { Eliminación → } (¬ (¬ (¬p ∨ q) ∨ p ∨ r) ∧ ( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q)) ≡ { Eliminación doble negación } (¬p ∨ q ∨ p ∨ r ) ∧ ( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q)) ≡ { Eliminación disyunción con literal y su opuesto } ( ¬ (p ∨ r) ∨ ¬(¬ p ∨ q)) ≡ { De Morgan } (¬p ∧ ¬ r) ∨ (¬¬p ∧ ¬ q) ≡ { Eliminación doble negación } (¬p ∧ ¬ r) ∨ (p ∧ ¬ q) ≡ { Distributiva ∨ } ((¬p ∧ ¬ r) ∨ p) ∧ ((¬p ∧ ¬ r) ∨ ¬ q) ≡ { Distributiva ∨ } (¬p ∨ p) ∧(p ∨¬ r) ∧ (¬p∨¬q) ∧ (¬ q∨¬ r) ≡ { Eliminación disyunción con literal y su opuesto } (p ∨¬ r) ∧ (¬p∨¬q) ∧ (¬ q∨¬ r) Definición 14: Una cláusula es una disyunción de literales. se denomina cláusula Horn.2.Lógica Proposicional (A ∧ B) ∨ A ≡ A Técnicas Semánticas de Estudio de Validez Ejemplo 8: Para transformar la fórmula ¬(p→q)↔p∨r a Forma Normal Conjuntiva. Definición 17: Una cláusula que tiene a lo sumo un literal positivo. el algoritmo es fácil de analizar e implementar. se denomina hecho. ¬p ∨ q ∨ ¬r. Algoritmo de Resolución Proposicional El algoritmo se basa en una regla de inferencia sencilla y. se representa por siempre Falso. 11 . Ejemplo 9: La fórmula ( ¬p ∨ q) ∧ ( ¬p ∨ q ∨ ¬r ) ∧ ( p) en Forma Normal Conjuntiva equivale a {¬p ∨ q. a la vez de gran potencia: la regla de resolución. Una cláusula Horn será de la forma: A ∨ ¬B1 ∨ ¬ B2 ∨L∨¬ Bn . se denomina regla. La transformación de una fórmula en Forma Normal Conjuntiva a Forma Clausal es inmediata sustituyendo las conectivas ∧ por comas y englobando las disyunciones entre llaves.
entonces C es insatisfacible. C2 ) es válida. Supóngase que existe una interpretación que la hace Falsa. probar que ( ) ( ) {C . Es decir {C1 . Dem: Rl (C1 . C2 ) = C1 − {l} ∪ C2 − {¬ l} . es decir. Dem: es lo mismo que C ∧ Rl (C1 . C ) es equivalente a probar que 1 2 1 2 C1 ∧ C2 → R(C1 . C2 ) = l11 ∨ l12 ∨L∨ l1m ∨ l21 ∨ l 22 ∨L∨l 2n Por el teorema 2. Leibniz } C≡C∧ ≡ { Def. la fórmula es Válida. C ∧ F ≡ F } C≡F ≡ { Def. C2 } ⇒ R(C1 . Interpretación ≡ } ∀I VI(C) = VI(F) 12 Recordando que un conjunto de cláusulas equivale a forma normal conjuntiva. ≡ F } C≡C∧ F ≡ { El. C 2 ) Teorema 8: Si el resolvente de dos cláusulas C1 y C2 pertenecientes a un conjunto C es la cláusula vacía.Lógica Proposicional Técnicas Semánticas de Estudio de Validez La idea del principio de resolución es simple: Si se sabe que se cumple: "P ó Q" y también se sabe que se cumple "no P ó R" entonces se puede deducir que se cumplirá "Q ó R". C ∪ Rl (C1 . la primera frase sería: G ∨ P ∨ E y la segunda: G → F ∨ V ≡ ¬G ∨ F ∨ V La regla de resolución inferirá: P ∨ E ∨ F ∨ V Definición 18: Dadas dos cláusulas C1 y C2 tales que exista un literal l de forma que l ∈ C1 y ¬ l ∈ C2 . C 2 ) . n Teorema 7: Dadas dos cláusulas C1 y C2 pertenecientes a un conjunto C y resolubles respecto un literal l. Ejemplo 10: Si se tiene: "Gana o Pierde o Empata" y "Si Gana entonces da una Fiesta o Va de Viaje". la asignación de valores será: l ∨ l11 ∨L∨ l1m ∧ ¬ l ∨ l21 ∨L∨ l2 n → l11 ∨L∨ l1m ∨ l21 ∨L∨ l2 n V V F F F F F F 14 244 { F 4 3 1444 24444 4 F 3 F V 1442443 F F 1442443 V 144444 2444444 4 3 V 144444444444 244444444444 3 4 4 F Contradicción Puesto que se llega a una contradicción. C 2 ) = ≡ { Teorema 7. Se dice que C1 y C2 son cláusulas resolubles. entonces: C ≡ C ∪ Rl (C1 . Se puede deducir que: "O Pierde o Empata o da una Fiesta o va de Viaje". C } ⇒ R(C . C 2 ) . la fórmula no puede ser Falsa y será siempre verdadera. Formalizando. Neutro. Teorema 6 (Consistencia de la regla de resolución): El resolvente de dos cláusulas es consecuencia lógica de ellas. El resolvente de C1 y C2 respecto a l será R l ( C1 . se denomina resolvente de C1 y C2 respecto a l a la cláusula: Rl ( C1. C2 ) Dem: Se demuestra por contradicción: Sea C1 = l ∨ l11 ∨ l12 ∨L∨l1m y C2 = ¬l ∨ l21 ∨ l22 ∨L∨ l2 n . La demostración es: C ≡ { Absorción A ≡ A ∧ B } C ∧ Rl (C1 . C 2 ) .
.Se resuelve ahora la cláusula anterior con la segunda cláusula (¬ p ∨ q ) obteniendo: ¬p .Lógica Proposicional ≡ { Def.Se resuelve ahora la cláusula anterior con la primera y se llaga a la cláusula vacía o Puesto que se llega a la cláusula vacía.Se resuelve la segunda cláusula (¬ p ∨ ¬q ∨ s ) con la tercera (¬ p ∨ ¬s). obteniendo ¬ p ∨ ¬q . q} . ¬r.Se resuelve la tercera cláusula (¬ r ) con la cuarta (¬ p ∨ ¬ q ∨ r ).. obteniendo ¬ p ∨ ¬q . L .. ¬p ∨ ¬s.Si no se encuentran: SALIR indicando que C no es insatisfacible.. C2 ) y añadirlo al conjunto C 4. El conjunto obtenido sería {¬p ∨ ¬q ∨ r. Aplicando el algoritmo de resolución: . Pn ⇒ Q es correcto si y sólo si el conjunto de 1 cláusulas { p.Si Rl ( C1 . L . Dem: ⇔ P1 . Volver a 1 3.Se resuelve ahora la cláusula anterior con la cuarta cláusula (p) obteniendo: ¬q 13 . ¬p ∨ q. C es insatisfacible. Insatisfacible } C es insatisfacible Técnicas Semánticas de Estudio de Validez A partir de los teoremas anteriores.Buscar dos cláusulas C1 . ¬p ∨ ¬q ∨ s.Calcular Rl ( C1 . Cada Pi c es el resultado de transformar la premisa Pi a forma clausal y ¬Q c es el resultado de transformar la negación de la conclusión a forma clausal.Si no. se puede demostrar {P . Teorema 9: Un razonamiento de la forma P . P c 1 c 2 . Pn ⇒ Q { Teorema 4} P ∧ P2 ∧ L ∧ Pn → Q es válida 1 ⇔ { Teorema 1} ¬( P ∧ P2 ∧ L ∧ Pn → Q ) es insatisfacible 1 ⇔ { Pasando a Forma Normal Conjuntiva cada premisa y operando } {P . p → ¬s} ⇒ ¬p ∨ ¬q es correcto por resolución. se define el algoritmo de resolución que chequeará si un conjunto de cláusulas es insatisfacible. 5. . es necesario transformar cada premisa a forma clausal y añadir el resultado de transformar la negación de la conclusión a forma clausal. ¬ Q c } es insatisfacible..Si se encuentran: 3. C2 ∈ C tales que exista un literal l que cumple que l ∈ C1 y ¬ l ∈ C2 2. P2 . Algoritmo de resolución proposicional Entrada: Salida: Un conjunto de cláusulas C Detecta si C es insatisfacible 1. ¬ Q c es insatisfacible } Ejemplo 12: Para estudiar si el razonamiento { p ∧ q → r ∧ s. P c 1 c 2 . P2 . C2 ) = Ì entonces SALIR indicando que C es insatisfacible. ¬p ∨ ¬q ∨ r} .. Para ello: . Interpretación: VI(F) = F } ∀I VI(C) = F ≡ { Def.L Pnc .L Pnc . Ejemplo 11: Sea C el siguiente conjunto de cláusulas que C es insatisfacible por resolución. p.
Lógica Proposicional Técnicas Semánticas de Estudio de Validez . el conjunto de cláusulas es insatisfacible y el razonamiento es correcto. entonces dicho conjunto contiene la cláusula vacía. ¬p ∨ ¬q ∨ r } . árbol de fallo. el valor de esos literales debe ser F (puesto que C es una disyunción). ocasionalmente. para construir el árbol semántico para C se recuerda que un conjunto de cláusulas equivale a una fórmula en Forma Normal Conjuntiva. entonces el árbol semántico es finito y está limitado por nodos de fallo. n Definición 19: Se denomina nodo de inferencia a un nodo del árbol semántico cuyos dos hijos son nodos de fallo. Lema 3: La cláusula C asociada a un nodo de fallo n contiene un subconjunto de los complementos de los literales que aparecen en la rama que va desde la raíz del árbol semántico hasta n. p ∧ ( ¬p ∨ q) ∧ ( ¬r ) ∧ (¬p ∨ ¬q ∨ r ) . Dem: Puesto que el árbol de fallo es finito y las ramas se desarrollan de dos en dos. Lema 4: En un árbol de fallo. Ejemplo 13: Sea el conjunto de cláusulas C = { p. ¬r . Dem: Puesto que la cláusula C es falsificada en el nodo n. Dem: En un nodo de inferencia i cualquiera. Además. El árbol semántico será: p ¬p ( p) q ¬q F F r F ¬r F ( ¬p ∨ ( ¬p ∨ q ) ( ¬r ) ¬q ∨ r ) Lema 1: Si un conjunto de cláusulas es insatisfacible. n Lema 5: Si el árbol semántico de un conjunto de cláusulas es de fallo y contiene un sólo nodo. Lema 2: Cada nodo de fallo n falsifica al menos a una de las cláusulas del conjunto que será la cláusula asociada a n. por alguno de sus antecesores.Se resuelve ahora la cláusula anterior con la quinta y se llega a la cláusula vacía o Puesto que se llega a la cláusula vacía. en este caso. se denomina. en ese caso. debe existir al menos un nodo de inferencia. salvo que sólo tenga un nodo. Lema 6: Un nodo de inferencia i indica un paso de resolución de las cláusulas asociadas a sus dos hijos. se tendrá un esquema como el que sigue: 14 . Demostración de la completud del algoritmo de resolución Se presentan las ideas generales de la demostración de la completud del algoritmo de resolución proposicional sin entrar en una demostración formal que se sale del ámbito de estos apuntes. El resolvente de dichas cláusulas es falsificado por el nodo i y. necesariamente tendremos un último nodo desarrollado con dos hijos. todos sus literales deben tener asignado un valor en la interpretación parcial correspondiente a n. En la siguiente figura se muestra el árbol semántico correspondiente marcando la cláusula falsificada en los nodos de fallo. El valor asignado debe ser el complementario. ¬p ∨ q.
Por la misma razón anterior. es decir. se alcanza la cláusula vacía. como resto_ C j no contiene el literal p también tomarán valor Falso en el nodo i.Puesto que el nodo i no falsificó C j y lo único que cambia en el nodo j respecto a i es el valor de p. ¬ p ∨ q. junto con los resolventes sería: p ¬p ( ¬ p) q ¬q F F (p) ( ¬ p ∨ q) r F (¬ r ) ¬r F (¬ p ∨ r ) El resolvente de los nodos 6 y 7 es ( ¬ p ) que falsifica al nodo 4 pero también falsifica a su antecesor. ¬ r. la cláusula Ck debe contener el literal p (sin complementar para que sea Falso) Por tanto C j y Ck son resolubles respecto a p. la cláusula C j debe contener el literal ¬ p (complementado para que sea Falso). . el nodo 2. puede ocurrir que el resolvente sea falsificado también por alguno de los padres del nodo de inferencia. por tanto resto_ C j tomará también valor Falso. el nodo i. considérese el conjunto de cláusulas { p.Lógica Proposicional Técnicas Semánticas de Estudio de Validez i ( p) p= V j F ( ¬ p) p= F k (C j ) F (C k ) . el árbol semántico. El esquema será: C j = ¬ p ∨ resto_ C j  Ck = p ∨ resto_ Ck   R p ( C j . Ck ) = resto_ C j ∨ resto_ Ck tomará valor Falso en el nodo i. es un nodo de fallo para el resolvente de C j y Ck En ocasiones. n Teorema 10 (Completud del Algoritmo de Resolución Proposicional): Si un conjunto de cláusulas es insatisfacible entonces. C j toma valor Falso. Ck ) = resto_ C j ∨ resto_ Ck En el nodo j. De la misma forma. como ejemplo. aplicando el algoritmo de resolución. Por tanto. un nodo de inferencia indica un paso de resolución } Se puede formar el resolvente con las cláusulas asociadas a los dos hijos i El resolvente puede añadirse al conjunto C y construir de nuevo el árbol semántico 15 . ¬ p ∨ r} . R p ( C j . resto_ Ck tomará valor Falso en el nodo i. Dem: C es un conjunto de cláusulas insatisfacibles ⇔ {Lema 1} El árbol semánttico de C será un árbol de fallo ⇔ {Lema 4} ∃ un nodo de inferencia i ⇔ {Lema 6.
siguiendo un determinado camino se alcanzará la cláusula vacía con muchos menos pasos de resolución que por otro camino. queda demostrado que se alcanza la cláusula vacía por resolución. Ejemplo 14: El conjunto C = { ¬ p ∨ ¬ q ∨ r. 4. C es insatisfacible. Una cláusula que contenga un literal puro es inútil en la búsqueda de la cláusula vacía. una estrategia de borrado consiste en la eliminación de cláusulas con literales puros. q.2. alcanzar la cláusula vacía) y que se obtenga un comportamiento eficiente. Es posible. Por tanto.1.3. sin embargo.3. ¬ q ∨ s. Eliminación de cláusulas con literales puros Definición 20: Un literal es puro si y sólo si no existe un literal complementario a él en el conjunto de cláusulas.1.4. su eliminación permitirá un ahorro computacional. puesto que el literal puro no podrá ser eliminado nunca mediante resolución. Consistencia Resolución } El nuevo árbol seguirá siendo insatisfacible. puesto que ambas contienen el literal puro s.Lógica Proposicional Técnicas Semánticas de Estudio de Validez ⇔ { Hipótesis. Muchas veces. 4. Se observa que muchas veces los resolventes son redundantes o no aportan ninguna utilidad para la búsqueda. Eliminación de tautologías Definición 20: Una tautología es una cláusula que contiene el mismo literal en su forma directa e inversa. para demostrarlo. eliminar las tautologías de 16 . Un conjunto de cláusulas permanecerá satisfacible independientemente de que se le añadan tautologías. Estrategias de resolución El método de resolución es un algoritmo no determinista ya que pueden encontrarse múltiples formas de alcanzar la cláusula vacía en un conjunto insatisfacible.3.3. ¬ p ∨ s. se puede ignorar la segunda y la tercera cláusula. por tanto. 4. Durante el desarrollo del algoritmo es necesario responder las siguientes preguntas: ¿Qué dos cláusulas se seleccionan? y ¿sobre qué literales se realiza la resolución?. La presencia o ausencia de tautologías en un conjunto de cláusulas no afecta la condición de satisfacibilidad del conjunto. Una de las desventajas de la utilización de la reglas de resolución sin ninguna restricción consiste en que se pueden seleccionar cláusulas cuyo resolvente no sea útil en el camino de búsqueda de la cláusula vacía. ¬ r} es insatisfacible.1. Estrategias de Borrado Una estrategia de borrado será una técnica en la cual se eliminan una serie de cláusulas antes de que sean utilizadas. Ejemplo 15: La cláusula p ∨ ¬ q ∨ r ∨ ¬ p es una tautología. por tanto. un conjunto de cláusulas insatisfacible seguirá siendo insatisfacible aunque se eliminen todas sus tautologías.4.4. Las distintas estrategias de resolución tratan de responder a ambas preguntas de forma que se mantenga la completud (si el conjunto es insatisfacible. De la misma forma.4. 4. p.1. Si dichas cláusulas no van a aportar nada para la búsqueda de la cláusula vacía. A continuación se mencionan una serie de estrategias que servirán para eliminar el trabajo inútil. pero contendrá menos nodos Repitiendo el proceso se llegará a un árbol semántico con un solo nodo que corresponderá a la cláusula vacía {Lema 5} y.
Resolución de Entrada Definición 23: Un resolvente de entrada es un resolvente en el cual al menos uno de sus padres es una cláusula del conjunto original de entrada. Los procedimientos de resolución basados en resolución unitaria son sencillos de implementar y. Por otro lado. las cláusulas 1 y 2 podrían haberse seleccionado para obtener q ∨ r .3.2.3. Sin embargo ni esa cláusula ni sus descendientes podrán ser generados porque ninguna de las cláusulas que la generan es unitaria.q R p (1. Ejemplo 17: Sea C = { p ∨ q. Desafortunadamente.r Rq (3. Resolución unitaria Definición 22: Un resolvente unitario es un resolvente en el cual al menos uno de sus padres es una cláusula unitaria (con un sólo literal). 4 ) Obsérvese que los resolventes generados son un subconjunto de los que se podrían generar mediante la resolución sin restricciones.r Rq (6. restringiendo el formato de cláusulas a cláusulas Horn (cláusulas con un literal positivo como máximo) se puede demostrar que si un conjunto de cláusulas Horn es insatisfacible. 4. se pueden generar resolventes de cláusulas que sean tautologías o cláusulas subsumidas. C ⊆ D. 7) 5.. entonces se llegará a la cláusula vacía aplicando la estrategia de resolución unitaria. durante el desarrollo del proceso de resolución.4. un conjunto de cláusulas en el que se eliminan todas las cláusulas subsumidas es equivalente al conjunto original. 7) 4. Una estrategia de resolución de entrada es una aplicación del algoritmo de resolución en la cual todos los resolventes son de entrada. Por ejemplo. en general. Una estrategia de resolución unitaria es una aplicación del algoritmo de resolución en la cual todos los resolventes son unitarios... Es necesario observar que. se seleccionan siempre dos cláusulas resolubles tales que una de ellas tenga un literal. sin embargo. 1. su resolvente tiene menos literales que la cláusula original. 17 . Ejemplo 16: La cláusula p ∨ ¬ q subsume a la cláusula p ∨ ¬ q ∨ r . Las estrategias de borrado deberán chequear el conjunto de cláusulas original así como los distintos resolventes generados en cada resolución. Eliminación de Subsunciones Definición 21: Una cláusula C subsume a una cláusula D si y sólo si todo literal de C pertenece también a D..Lógica Proposicional Técnicas Semánticas de Estudio de Validez un conjunto de cláusulas para que no intervengan en el proceso de búsqueda sin alterar la satisfacibilidad del conjunto. completos. ¬ p ∨ r ..¬ q ∨ r 9.3. 4.3. ¬ r } . por tanto. Por ejemplo.p ∨ q 7.3. Debido a la ley de absorción.¬ p ∨ r 8. A continuación se aplicará la estrategia de resolución unitaria. ¬ q ∨ r . los procedimientos de inferencia basados en resolución unitaria no son.p Rq (1.. 4.4.. eliminadas. ¬ p ∨ q. para ello.¬r 10. ¬ p ∨ ¬ q} es insatisfacible.¬ q Rr ( 3 . De esa forma los procedimientos siguen una búsqueda directa hacia la cláusula vacía ganando en eficiencia.¬ p Rr ( 2 . 5) 2..1. la resolución unitaria no encontrará la cláusula vacía porque ninguna de las cláusulas es unitaria.4. bastante eficientes. Las cláusulas subsumidas pueden ser. 4 ) 6. 6) 3. Obsérvese que si una cláusula es resuelta con una cláusula unitaria.. el conjunto C = { p ∨ q.. es decir. p ∨ ¬ q. normalmente.
. ¬ p ∨ q.p ∨ r Rq (1.q ∨ r Rp (1.¬ p ∨ r 8. p∨q ¬p∨ q p ∨ ¬q ¬p∨ ¬q q p ¬q q Ì Resolución Lineal La resolucióon lineal evita muchas resoluciones inútiles centrándose en cada paso en los antepasados de una cláusula y en los elementos del conjunto inicial. para ello... Resolución Lineal La resolución lineal (también conocida como resolución con filtrado de antepasados) es una ligera generalización de la resolución de entrada. 2) 6...4. ¬ q ∨ r . Se escoge una cláusula inicial o cláusula cabeza C0 y se forma una cedena de resolventes R0 . con la otra también.¬ p Rr ( 2 . p ∨ ¬ q. Una resolución lineal comienza con una cláusula del conjunto inicial y produce una cadena lineal de resoluciones como la que se muestra en la figura para el conjunto de cláusulas C = { p ∨ q. A continuación se aplicará la estrategia de resolución de entrada. 4. La r íz del árbol es la cláusula cabeza y se forman los nodos a descendientes según las cláusulas con las que se pueda resolver.. Obsérvese que cada resolvente.r R p ( 2. Ci ) tal que Ci ∈ C ó Ci = R j ( j ≤ i) La resolución lineal toma su nombre del aspecto lineal que presentan las inferencias realizadas. Una consecuencia de lo anterior es que la resolución de entrada es completa para cláusulas Horn. ¬ r } . Los resultados obtenidos aplicando resolución para una determinada cláusula cabeza se pueden mostrar en forma de árbol de resolución. 3) Se puede demostrar que la resolución unitaria y la resolución de entrada tienen el mismo poder de inferencia en el sentido de que si con una estrategia se puede alcanzar la cláusula vacía. El árbol de resolución para el ejemplo anterior sería: 18 . se obtiene del resolvente anterior y de alguna otra cláusula del conjunto.. ¬ p ∨ r .r Rr ( 4 . L..¬ q ∨ r 9. después del primero.3. ¬ p ∨ ¬ q} . 6) 3.4.¬r 5.Lógica Proposicional Técnicas Semánticas de Estudio de Validez Ejemplo 18: Sea C = { p ∨ q. 8) 4. R1 .p ∨ q 7. 4 ) 2. R3 . Rn donde: R0 = C 0 Ri + 1 = R( Ri . se puede tomar el del apartado anterior. se seleccionan siempre dos cláusulas resolubles tales que una de ellas pertenezca al conjunto inicial de cláusulas: 1.. pero incompleta en general. Como contraejemplo.
caminos que llevan a tautologías y caminos de éxito que alcanzan la cláusula vacía. en los cuales las premisas son.. no siempre es necesario probar con todas las cláusulas del conjunto inicial como cláusulas cabeza. ¬ r } . A cada resolvente se le asigna un nuevo número.. ¬ p ∨ r .r 7.¬r 5.¬ q ∨ r 4. Debido al siguiente teorema. satisfacibles. A continuación se aplicará la estrategia de resolución ordenada (se han ordenado los literales de cada cláusula por orden alfabético): 1.. por lo general. aplicando resolución lineal. según el teorema anterior basta con probar como cláusula cabeza con las que resultaron de negar la conclusión.Lógica Proposicional Técnicas Semánticas de Estudio de Validez 1: p ∨ q 2p 5: q 3p q 6: p 4p 4p 8:p ∨¬ p Tautología 7: q∨ ¬ q Tautología 4p 12: ¬ q 3q 9: p 4q 10: ¬ p 2p 11: q 2p 13: q 4q 14: ¬ q 1q 15: p 2q 16: ¬ p 5q r Árbol de resolución En la figura se representan las resoluciones indicando el número de cláusula y el literal por el que se resuelve. 2) Rq (3.q ∨ r 6. Obsérvese que pueden existir caminos infinitos (el camino más a la izquierda). Ejemplo 19: Sea C = { p ∨ q.. Resolución Ordenada La resolución ordenada o selectiva es una estrategia de resolución muy restrictiva en la cual cada cláusula se toma como un conjunto de literales ordenados.p ∨ q 2.4. entonces se encuentra la cláusula vacía mediante resolución lineal tomando como cláusula cabeza una cláusula del conjunto C. Los literales del resolvente mantienen el orden de las cláusulas padre con los literales del padre positivo (la cláusula que contenía el literal por el que se resuelve afirmado) seguidos de los literales del padre negativo (la cláusula que contenía el literal por el que se resuelve negado). 6 ) 19 . Si al añadir las cláusulas resultantes de negar la conclusión el conjunto resultante es insatisfacible (y el razonamiento es correcto) entonces.3..5. 4.r Rp (1.¬ p ∨ r 3. La resolución sólo se realiza con el primer literal de cada cláusula. Se puede demostrar que la resolución lineal es completa. Teorema 11: Si un conjunto de cláusulas S es satisfacible y S ∪ C es insatisfacible.. se alcanza la cláusula vacía. El teorema anterior tiene aplicación al estudio de los razonamientos.. Para cualquier conjunto de cláusulas insatisfacibles. 5) Rr ( 4 . ¬ q ∨ r .
la cual resuelve con la cláusula 4 para producir la cláusula vacía. Conocida como resolución SLD (Selective Linear Resolution for Definite Clauses). 1 20 . resuelve con la cláusula 3 para producir la cláusula 6. La resolución ordenada es la más eficiente (en el ejemplo.Lógica Proposicional Técnicas Semánticas de Estudio de Validez La cláusula 5 es el único resolvente ordenado entre las cláusulas 1 y 4. Las cláusulas 1 y 3 no resuelven puesto que sus literales complementarios no son los primeros. Sin embargo. Tras este breve repaso de las principales estrategias de resolución. Los sistemas Prolog utilizan la resolución lineal ordenada para cláusulas Horn en lógica de predicados. se obtuvo la cláusula vacía en el tercer paso de resolución). cabe reseñar que los principales sistemas de demostración automática basados en el principio de resolución (por ejemp lo. la resolución ordenada no es completa. Desafortunadamente. los sistemas Prolog) utilizan una combinación de las dos últimas estrategias restringidas a conjuntos de cláusulas Horn 1. Por la misma razón tampoco resuelven las cláusulas 2 y 4 ni las cláusulas 3 y 4. Una vez generada la cláusula 5. se ha demo strado que la resolución ordenada sí es completa para cláusulas Horn.
Lógica Proposicional Técnicas Semánticas de Estudio de Validez 21 .
En esta sección se presenta el estilo de deducción natural. Por el contrario. La deducción natural no contiene axiomas y ofrece una serie de reglas de inferencia por cada tipo de conectiva. Este conjunto de técnicas se engloban en lo que se denomina teoría semántica. Ejemplo 20: Demostrar que p ∧ q → q ∧ p 22 . Todos ellos utilizan un conjunto de axiomas y una serie de reglas de inferencia que permiten obtener teoremas a partir de dichos axiomas o de otros teoremas previamente derivados.E se refieren a la eliminación de dicho símbolo. Teoría de la Prueba: Deducción Natural En las secciones anteriores se han utilizado técnicas que estudian la corrección de los razonamientos en base al significado de las fórmulas que contienen.Lógica Proposicional Teoría de la Prueba: Deducción Natural 5. etc.I se refieren a la inclusión del símbolo • y las reglas de la forma • . conocido como teoría de la prueba. Reglas de Introducción ∧ Reglas de Eliminación A B ∧ -I A ∧ B -E A ∧ B A A ∧ B B ∨ A -I A ∨ B B A ∨ B Prueba por casos ∨ -E A ∨ B A → C C B → C Deducción A Modus Ponens → -E A B A → B B → -I A → B B → A ↔ B A ↔ ↔ -I A → B -E A ↔ B A → B A ↔ B B → A Dem. por Contradicción ¬ A -I ¬ ¬ ¬ B ∧ ¬ B -E A V A ∨ A F A A A ∨ A V V -I V -E ¬ F -I A ∧ ¬ A F F -E Tabla 1: Reglas de Inferencia para Deducción Natural Las reglas de la forma • . la deducción natural. Las reglas de inferencia se presentan en la siguiente tabla. desarrollado por Gentzen en 1935 y cuyo principal objetivo es ofrecer un sistema que se acerque a las técnicas de demostración habituales. que prescinde de los posibles valores de las fórmulas y se centra únicamente en la manipulación sintáctica de fórmulas. por Contradicción A B ∧ ¬ B ¬ Dem. Existen diversos estilos como el sistema de Hilbert. existe otro conjunto de técnicas.
si se supone A y se llega a demostrar B.4 → I 3-5 → I 2-6 23 .3 → E 1. Un ejemplo es la regla de deducción: A B → . se realiza un supuesto y.Pn} ⇒ Q se parte de las premisas y se intenta llegar a la conclusión. se puede deducir la fórmula A → B.. Ejemplo 22: Demostrar que p → (q → r) ⇒ p ∧ q → r 1 2 3 4 5 6 7 p → (q → r) p∧q p q→r q r p∧ q→r Premisa Supuesto ∧-E 2 → E 1. En una prueba subordinada. una vez llegado a un resultado.5 → I 2-6 Ejemplo 23: Demostrar que p ∧ q → r ⇒ p → (q → r) 1 2 3 4 5 6 7 p∧ q→r p q p∧q r q→r p → (q → r) Premisa Supuesto Supuesto ∧-I 2.4 La utilización de cuadros permite visualizar la idea de pruebas subordinadas.I A → B Esta regla enuncia que. se descarta el supuesto (se cierra el cuadro) obteniendo un resultado libre de supuestos. entonces. P2.3 ∧-E 2 → E 4.. .Lógica Proposicional p∧q q p q∧p Teoría de la Prueba: Deducción Natural 1 2 3 4 Premisa ∧-E 1 ∧-E 1 ∧-I 2. Ejemplo 21: Demostrar que p ∧ q ⇒ p ∧ (q ∨ r) 1 2 3 4 5 p∧q p q q∨r p ∧ (q ∨ r) Premisa ∧-E 1 ∧-E 1 ∨-I 3 ∧-I 2.3 Para el estudio de razonamientos de la forma {P1.
2 ¬I 2-3 → I 2-4 Supuesto Supuesto ∧-I 6.5 Teoría de la Prueba: Deducción Natural Ejemplo 25: Demostrar p ↔ ¬¬p 1 2 3 4 5 6 7 8 9 10 11 p ¬p p ∧ ¬p ¬¬p p → ¬¬p ¬¬p ¬p ¬p ∧ ¬¬p p ¬¬p → p p ↔ ¬¬p Supuesto Supuesto ∧-I 1. 24) → I 3-4 Supuesto Supuesto 6 →-I 7-8 →-I 6-10 ∨-E 1.5.Lógica Proposicional Ejemplo 24: Demostrar que ¬p ⇒ p → q 1 2 3 4 5 6 ¬p p p∧¬p F q p→q Premisa Supuesto ∧-I 1.2 F-I 3 F-E 4 → I 2.10 Ejemplo 26: Demostrar que ¬p∨q ⇒ p→q 1 3 4 5 6 7 8 9 10 11 ¬p∨q ¬p p→q ¬p → (p → q) q p q p→q q → (p → q) p→q Premisa Supuesto ¬A⇒A→B (Demostrado en Ej.10 24 .7 ¬-E 7-8 →-I 6-9 ↔-I 5.
Lógica Proposicional Teoría de la Prueba: Deducción Natural Ejemplo 27: Demostrar que p → q ⇒ ¬p∨q 1 2 3 4 5 6 7 8 10 11 p→q ¬ (¬p∨ q) ¬p ¬p∨q (¬p∨q) ∧ ¬(¬p∨q) p q ¬p ∨ q (¬p∨q) ∧ ¬(¬p∨q) ¬p∨q Premisa Supuesto Supuesto ∨-I 3 ∧-I 4.6 ∨-I 7 ∧-I 8.2 ¬-E 2-10 25 .2 ¬-E 3-5 →-E 1.
se cumplen los postulados del álgebra de Boole: Commutativa: Distributiva: a ∨ b = b∨ a y a ∧ b = b∧ a ∀a.b∈A ∀a∈A a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) Elemento neutro: a ∨ F= a a ∧ V =a Elemento inverso: a ∨ ¬a = V (medio excluido) y a ∧ ¬a = F (contradicción) ∀a∈A 26 . el álgebra de Boole ha tenido dos aplicaciones importantes: el tratamiento de conjuntos mediante las operaciones de unión e intersección que ha servido de base a la teoría de la probabilidad y el diseño de circuitos digitales combinacionales.b ∈ A ∀a. A={ 0 . tiene estructura de álgebra de Boole.b. Esto quiere decir que las variables sólo pueden tomar los valores 0 o 1.2.  .1} siendo A un conjunto en el que se definen las siguientes operaciones: + y × son leyes de composición binaria sobre A: . +. Conmutativa: a+b=b+a a × b = b× a 2. Elemento neutro: a + 0=a a × 1=a 4. el conjunto A tiene como únicos elementos a los neutros de las operaciones.b. 0 o 1. Basta con demostrar que la tupla (LPROP. Aplicación al diseño de Circuitos: Álgebra de Boole 6. el álgebra de Boole se dice que es bivaluada. o lo que es lo mismo. La disyunción y la conjunción son operaciones binarias (intervienen dos operandos) e internas. 6. × . ∧. Definición de álgebra de Boole y Teoremas Definición 24: Un álgebra de Boole es una estructura de la forma {A. sólo pueden tomar los valores F o V. Ejemplo 28: La lógica proposicional LPROP. ∨.b ∈ A ∀a∈A a∈ A ∀a. Como ya se ha demostrado. las fórmulas de la lógica proposicional.es una ley de composición unaria sobre A: verificándose los postulados: 1. 0. El complementario es una operación unaria interna. Introducción George Boole (1815-1864) presentó el primer tratamiento sistemático de la lógica y para ello. F. Distributiva: a + (b × c) = (a + b) × (a + c) a × (b + c) = (a × b) + (a × c) 3. Además de sus aplicaciones al campo de la lógica. conocido ahora como Álgebra de Boole.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole 6.c ∈ A ∀a∈A ∀a∈A ∀a∈A ∀a∈A {conmutativa +} {conmutativa ×} {distributiva +} {distributiva ×} {neutro +} {neutro ×} {inverso +} {inverso ×} En el caso más sencillo. V) cumple la definición de álgebra de Boole Los elementos de LPROP. -.c ∈ A ∀a.1. En este caso.b ∈ A ∀a. Elemento inverso: a+a=1 a*a = 0 a +b ∈A y a × b ∈A ∀a. 1 }. desarrolló un sistema algebraico.b∈A ∀a.
⊕. 1 } donde Dn es el conjunto de divisores de n. De manera informal. tiene estructura de álgebra de Boole Ejemplo 30: La estructura {A. S' } y las operaciones se definen mediante las siguientes tablas. la estructura {2C. '. puesto que los postulados son todos simétricos y cumplen la propiedad de dualidad. ∪. mcd. ∀a ÎA [Dual] Teorema 13 (Dominación ó Elemento Cero) Demostración: 1 = { inverso + } a +a = {neutro ×. ∪. a/ a } a+ a ×1 = { distributiva + } (a + a ) × (a + 1) = { inverso + } 1 × (a + 1) = { neutro × } a+1 a +1=1 a × 0=0 A partir del teorema anterior se pueden construir las tablas de verdad de las operaciones boolenas + y × Teorema 14 (Idempotencia) Demostración a = { neutro + } a+0 = { inverso ´ } 27 a +a =a a × a =a ∀a ÎA [Dual] . 1. mcm. S. y los valores 0 y 1. 0. C. (n/).son las operaciones de unión. este teorema puede demostrarse indicando que. ⊗. n.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Ejemplo 29: Dado un conjunto C. intersección y complementario entre conjuntos y ∅ es el conjunto vacío. -. ∩. se deducen los teoremas siguientes: Teorema 12 (Principio de dualidad): Cada identidad deducida de los postulados del álgebra de Boole permanece válida si se intercambian las operaciones + y ×. mcm y mcd son el mínimo común múltiplo y (n/) x = n / x tiene estructura de álgebra de Boole. I} donde A contiene los elementos: {0. cumplirá también dicha propiedad. ∩ y . la estructura {Dn. A partir de la definición de álgebra de Boole. también tiene estructura de álgebra de Boole ⊗ 0 S S' I 0 0 0 0 0 S 0 S 0 S S' 0 0 S' S' I 0 S S' I ⊕ 0 S S' I 0 0 S S' I S S S I I S' S' I S' I I I I I I X 0 S S' I X' I S' S 0 Ejemplo 31: Dado un número natural n. donde 2C es el conjunto de todos los subconjuntos de C. ∅ }. todo lo que se deduzca de ellos.
Lógica Proposicional a + a´a = { distributiva + } (a + a) × (a + a ) = { inverso + } (a + a) ´ 1 = { neutro × } a+a Teorema 15 (Absorción) Demostración a = { neutro × } 1× a = { dominación + } (1 + b) × a = { distributiva × } 1× a +b × a = { neutro × } a + a ´b a +a × b=a a × (a + b) = a Aplicación al diseño de Circuitos: Álgebra de Boole ∀a.b ÎA [Dual] Teorema 16 (Asociativa). la demostración se obitiene fácilmente: (a + b) + c 28 . a + (b + c) = (a + b) + c = a + b + c a ´ (b ´ c) = (a ´ b) ´ c = a ´ b ´ c Demostración: Se demostrarán dos teoremas auxiliares TA1 y TA2: TA1: a × ((a + b) + c) = a × (a + (b + c)) a × ((a + b) + c) = { distributiva × } a × (a + b) + a × c = { absorción × } a+a×c = { absorción + } a = { absorción ×. b / b+c } a × (a + (b + c)) TA2: a × ((a + b) + c) = a × (a + (b + c)) a × ((a + b) + c) = { distributiva × } a × (a + b) + a × c = { distributiva × } ( a × a + a × b) + a × c = { inverso × } (0 + a × b) + a × c = { neutro+ } a ×b+ a ×c = { distributiva × } a × ( b + c) = { neutro + } 0 + a × ( b + c) = { inverso × } a × a + a × ( b + c) = { distributiva × } a × (a + (b + c)) " a.b.c ÎA [Dual] A partir de dichos teoremas auxiliares.
es decir. que cumple la propiedad de elemento inverso. que cumpla que : a + x = 1 y a ´ x = 0 Demostración: Supóngase que existen dos elementos x e y que cumplen la propiedad: a+x=1 (H1) a ´x = 0 (H2) a+y=1 (H3) a ´y = 0 (H4) x = { neutro × } 1× x = { H3 } (a + y) × x = { distributiva × } a × x+y× x = { H2 } 0+ y× x = { H4 } a × y+y× x = { distributiva ×. cualquier x que cumpla que a + x = 1 y que a × x = 0 es a×a = { conmutativa × } a´a = { inverso × } 0 igual a a . conmutativa × } (a + x) × y = { H1 } 1× y = { neutro × } y Concluyendo que x e y son el mismo elemento Teorema 18 (Involución). x. es decir. (Unicidad del complementario) El elemento a asociado a un elemento a en un álgebra de Boole es único. se demuestra: a +a = { conmutativa + } a+ a = { inverso + } 1 Por tanto. conmutativa } a × ((a + b) + c) + a × ((a + b) + c) = { TA1 } a × (a + (b + c)) + a × ((a + b) + c) = { TA2 } a × (a + (b + c)) + a × (a + (b + c)) = { distributiva × } (a + a ) × (a + (b + c)) = { inverso + } 1 × (a + (b + c)) = { neutro × } a + (b + c) Aplicación al diseño de Circuitos: Álgebra de Boole Teorema 17. Demostración: a = a ∀ a ÎA A partir del teorema anterior. a = a 29 . existe un único elemento.Lógica Proposicional = {neutro × } ((a + b) + c) × 1 = { inverso + } ((a + b) + c) × (a + a ) = { distributiva ×. Suponiendo que dicho x es a.
30 .. inverso × } 0×b +0× a = { dominación × } 0+0 = { neutro + } 0 La demostración para n variables se realizaría de la siguiente forma: a + b + c + . y la segunda parte... Un circuito combinacional se caracteriza por ser un sistema sin memoria: el valor de las salidas en cada instante depende sólo del valor de las entradas en ese momento.. = { Sea p = b + c+ . 1.Demostración para dos variables: a + b = a × b Por la unicidad del complementario... (De Morgan) a + b + c + . se generaliza el resultado para n variables.. } a+ p = { De Morgan (2 variables) } a × p = { Deshaciendo } a × b + c + .. = { repitiendo el proceso anterior hasta sacar todas las variables } a × b × c × . Si se demuestra que a +b + a ×b =0 y que (a + b) × a × b = 1 entonces quedará demostrado a +b = a×b Las demostraciones de ambas igualdades son sencillas: a +b + a ×b = { Distributiva + } (a + b + a ) × (a + b + b ) = { Conmutativa +. Puertas Lógicas Un circuito digital es un circuito electrónico cuyas entradas y salidas sólo pueden tomar dos niveles distintos de tensión.. a × b × c ×... [Dual] Demostración Se realizará en dos partes: En la primera parte se demostrará para dos variables..Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Teorema 19. el único x que cumple que (a + b) + x = 0 y (a + b) × x = 1 es a + b ... Desde el punto de vista del diseño. 6.3... = a + b + c +. estos niveles de tensión se representan como 1 (verdadero) ó 0 (falso). = a × b × c ×. inverso + } (1 + b) × (1 + a) = { dominación + } 1× 1 = { neutro × } 1 (a + b)´ a × b = { distributiva × } a´ a × b + b´ a × b = { conmutativa ×..
Una variable booleana es una variable que toma únicamente dos valores 0 ó 1. se conoce como MAXTERM o suma canónica. se muestra cómo se implementa mediante puertas NAND las operaciones a .4. En estos diagramas se representan las entradas. Ejemplo.a × b a = { idempotencia ×} a×a a+b = { involución } a+b = { De Morgan + } a a = a× a a b a a× b a×b a×b = { { involución } a×b a b a× b b b b 6. las operaciones o puertas lógicas y sus conexiones.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Un circuito de estas características puede representarse analíticamente. Definición 26. A modo de ejemplo. mediante una función booleana.1. ×. 31 . a + b . Una función Booleana es una expresión algebraica que relaciona variables Booleanas por medio de las operaciones +. mediante un diagrama de puertas lógicas. se conoce como MINTERM o producto canónico. Cuando es una suma. las salidas. Un término canónico de una función booleana f es una expresión formada por el producto (o la suma) de todas las variables de f en su forma directa o inversa. Formas Canónicas Definición 27. o gráficamente. Puerta AND a b Puerta NAND Puerta OR Puerta NO (Inversor) a× b a b a+ b a b a+b a b a a Puerta NOR Puerta XOR (O-Exclusiva) a b a× b a b a⊕ b Mediante la utilización de puertas NAND ó NOR pueden implementarse el resto de operaciones. Funciones Booleanas Definición 25. Cuando el término canónico es un producto. b.4. c) = (a + b) × c + a × (b + c) 6. y −. Las diferentes conectivas pueden representarse mediante las siguientes puertas lógicas. 32: f (a.
b..) + a × f(0.c.) ={a=0} f(a..c.) + a × f ( 0.b.. Una función está en forma canónica si es una suma de productos canónicos o un producto de sumas canónicas.. c..b.b.c)...c.) La otra igualdad se demuestra por dualidad 32 .b. Cada término se representa utilizando el valor decimal de la combinación binaria resultante.b.)+ 0 = { neutro + } f(1. b .c.c.b.) + 0× f(0.7) 3 Teorema 20... b..b.. mientras que a + b + c + d es una suma canónica de la función f(a. Toda función Booleana puede expresarse como: f ( a .. a = 0 } 1´ f(1. c.. Ejemplo...) = { neutro + } f(0.) = { a = 1....0) 3 g ( a..Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Ejemplo.c. dominación ´ } f(1.c.c.) = { neutro ´..) = (a + f (0 .) f ( a ...5..) = a × f (1. c..) = { neutro ´.d) Una función de n variables tiene a lo sumo 2n sumas canónicas y 2n productos canónicos distintos..b. 35 : A continuación se presentan dos funciones en forma canónica: f ( a .c.Sea a = 1 a ´ f(1.. c.Sea a = 0 a ´ f(1.. se utiliza el símbolo ∑.. Cuando la función es una suma de productos canónicos..b.c......) ={a=1} f(a. es suficiente demostrar la igualdad para a = 0 y luego para a = 1 1.. b.c. b..) 2.. b .b.. b.) + a × f(0.) = { a = 0.. b ... c.b.6. a = 1 } 0´ f(1. Para representar los términos canónicos de una función se utiliza el siguiente convenio: se asigna un 1 a las variables en forma directa y un 0 a las variables en forma inversa. dominación ´ } 0 + f(0.. c.) ) Demostración: Puesto que una función booleana trabaja únicamente con variables Booleanas y estas variables sólo pueden tomar los valores 0 ó 1.b.) + 1× f(0.c.. 34 a bcd ≡ 0110 2 ≡ 6 10 a + b + c + d ≡ 1001 2 ≡ 910 Definición 28.c.) )× (( a + f (1. c ) = ( a + b + c )( a + b + c)( a + b + c) = ∏ (0.b. Ejemplo.b. b .c..b...33 : ab c es un producto canónico de f(a. c) = a bc + abc + a b c = ∑ ( 2. mientras que para un producto de sumas canónicas se utiliza el símbolo ∏..c..
.c.1. resultando en: abc + a (a × b + a × c + a × b × c ) = { a f(a... Con lo cual.1.b...... c.)) ´ ( a + b + c + f(1..1....Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Multiplicando (o sumando) las expresiones anteriores por a (ó a ) se obtienen las siguientes igualdades: a × f(a.b.1..c..1.c.. La expresión de producto de sumas.b... sería: f(a.b.) a × f(a.c. c..b..) + b × f(1.1..)) = { Distributiva × } a ´ b ´ f(1.1.c.0..) a + f(a.)) ´ ( a + b + c + f(0.. el término desaparece. dual de la anterior.... b. sacando a} a ´ f(1. Toda función lógica puede transformarse en una función equivalente en forma canónica..1..0..c. Demostración.) = a + f(0.c..0..{ repitiendo el proceso con el resto de variables } a ´ b ´ c´ f(1..c..) + a ´ b ´ c × f(1.1..) + a ´ b ´ c´ f(0.) = a × f(0. Cuando toman valor 1.c.. sacando b } a ´ (b ´ f(1...) + b × f(0.) = { Teorema 20..1.0.0.b.) = a f(0.1.c..) + a ´ b ´ c × f(0.) + a × f(0..0..) Las expresiones f(.) ) + a × (b ´ f(0..0.1. f(a.c.b.) +a ´ b × f(1. neutro × } abc + a c Transformación en forma canónica Teorema 21....0...) = ( a + b + c + f(0.0.1..c...) a + f(a.) = a × f(1..0..c..)) 33 ..1.)) ´ ( a + b + c + f(0.0..) + a × b ´ f(0...1.. 0 =1 } abc + a ( 0 + 1× c + 0) = { neutro +..) + a ´ b ´ c´ f(1.c..c.b.1....0.) + a ´ b ´ c × f(1... b.b.c. cualquier función puede expresarse en forma canónica..b.) } abc + a ( 0 × b + 0 × c + 0 × b × c ) = { neutro ×. b....) + a × b × f(0..c..1.1.) = { Teorema 20.0.) = .c..) + a ´ b ´ c´ f(0.b.c.)) ´ ( a + b + c + f(1.c.)) ´ (a + b + c + f(0.0..) + a ´ b ´ c × f(0...c.0.) toman valores 0 ó 1 dependiendo de la función particular.0.0.1.. utilizando la segunda igualdad....0.) Las anteriores igualdades tienen una aplicación importante para la simplificación de funciones Ejemplo 36: La f(a.)) ´ ( a + b + c + f(1.0.1..) = a + f(0.0. mientras que si toman valor cero.d)= abc + a (a × b + a × c + a × b × c ) puede simplificarse..)) ´ ( a + b + c + f(1. el término canónico correspondiente permanece.. b.
los términos canónicos permanecen cuando la función toma valor cero y desaparecen cuando toma valor 1.4. el procedimiento sería: a ´ ( b + c) + c = { distributiva + } (a + c) × ( b + c + c) 34 .b.7)= (a + b + c )(a + b + c )(a + b + c )(a + b + c ) En ocasiones. Además.3. El teorema anterior ofrece un método para obtener la expresión canónica de una función a partir de la tabla de verdad Suma de productos: Toman términos en los que la función vale 1 numerando de arriba abajo Producto de Sumas: Tomar términos en los que la función vale 0 numerando de abajo a arriba Ejemplo 37.b.c) 0 0 1 0 0 1 1 1 7 6 5 4 3 2 1 0 f(a.c)=∑3(2. sino que cuando la variable está en forma directa. le corresponde un 0 y cuando está en forma inversa.4. de sumas: a b 0 0 0 1 0 0 2 0 1 3 0 1 4 1 0 5 1 0 6 1 1 7 1 1 A partir de la siguiente tabla de verdad.b. conmutativa + } a ´b ´ c + a ´ b´ c + a´b × c + a´b ×c + a × b × c = { convenio } ∑3(1. un 1. inverso + } a ´ b × (c + c ) + a × c × (b + b ) + c × (a + a ) (b + b ) = { distributiva × . conmutativa ×} a´b ×c + a´b × c + a×b×c + a´b ×c + a´b´ c + a ´ b´ c + a´b ´ c + a ´b ´ c = { idempotencia +. se transforma en suma de productos (o producto de sumas) y se multiplica (o suma) cada término no canónico por la suma (o producto) de las variables que faltan y sus inversas.6.5. Para ello.7)= a b c + a b c + ab c + abc f(a. expresar en forma de suma de productos y producto c 0 1 0 1 0 1 0 1 f(a.7) En producto de sumas.c)=a ( b + c) + c a ´ ( b + c) + c = { distributiva × } a´b + a×c+c = { neutro × .b. desea obtenerse la expresión canónica de una función definida mediante una expresión algebraica.6.c)=∏3(3.5.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Obsérvese que en producto de sumas. Ejemplo 38: Se desea obtener la expresión canónica de f(a. los términos no corresponden de forma directa.
2. existen diversos métodos dependiendo del tipo de puertas lógicas disponibles... Definición 29: Dos términos son adyacentes si sólo difieren en el valor de una variable. se utilizan los siguientes pasos: Especificación del circuito Expresión analítica (normalmente... en forma de Tabla de verdad) Simplificación. = { inverso + } 1 × b× c× . Demostración..5. los agrupaciones anteriores serían: 35 . A partir del teorema de simplificación.. Uno de los métodos de simplificación más comunes consiste en la aplicación reiterada del siguiente teorema de simplificación Teorema 22 (Simplificación) a ´ b´ c´ ..... dos términos adyacentes pueden agruparse eliminando la variable respecto a la que difieren y quedando únicamente la parte común.. (a + b + c + .4..) = b + c + .. En cuanto a la simplificación. = { neutro × } b× c× . conmutativa } ( a + b + c) × ( a + b + c) × (a + b + c) = { convenio } ∏3(1. conmutativa + } (a + b + c)× ( a + b + c)× (a + b + c)×( a + b + c) = { idempotencia ×. Los principales métodos de simplificación reiteran este proceso de agrupamiento hasta obtener una expresión que ya no contenga más términos adyacentes. inverso × } (a + c + b× b ) × ( b + c + a × a ) = { distributiva +. Su representación binaria sólo diferirá en un bit.. En estos apuntes se tratan los tres primeros pasos. Simplificación de funciones lógicas En el diseño de circuitos. f = ab 4 2a b4 + a b4 2a b4 ⇒ f = b d d 1 cd + 4 cd 4 3 1 c4+ 4 c d 3 b cd 442444c d 43 b4 1444 bd [Dual] Utilizando las representaciones binarias de los términos canónicos.. a ´ b´ c´ .. + a ´ b´ c´ .. = { distributiva × } (a + a ) × b× c× ... dejando las técnicas de implementación a otros libros especializados. = b× c× ..) × ( a + b + c + .Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole = { idempotencia } (a + c) × ( b + c) = { neutro +. Implementación del diseño..7) 6. + a ´ b´ c´ .. Ejemplo 39.
f(a.c. Los de la fila superior con los respectivos de la fila inferior.b. Método de Karnaugh Es un método gráfico que visualiza los términos adyacentes en cuadrículas intentando que dos términos adyacentes estén próximos entre sí. f(a.X0X1 = b d Uno de los métodos más utilizados para funciones de menos de 6 variables es el método de Karnaugh que permite visualizar los términos adyacentes en una cuadrícula.X001 1-3-9-11 .d. Cada casilla corresponderá a un término canónico.c. 3 Variables. producto o suma.X011 1-9 .0001 3-11 . f(a. 36 .b) b 0 0 1 0 2 1 3 a 1 01 1 5 11 3 7 10 2 6 4 Variables.1011 3 .b.e) de 00 00 01 11 10 de 00 00 01 11 10 16 20 28 24 0 4 12 8 01 1 5 13 9 11 3 7 15 11 10 2 6 14 10 bc 01 1 5 13 9 11 3 7 15 11 10 2 6 14 10 a=0 bc 01 17 21 29 25 11 19 23 31 27 10 18 22 30 26 a=1 Son cuadros adyacentes: Los que tienen un lado común.d) cd ab 00 00 01 11 10 0 4 12 8 5 Variables. Sin embargo.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole Grupos 11 .0011 9 .b.c) bc a 00 0 1 0 4 2 variables. Cada casilla se etiqueta con el término asociado intentando que los términos adyacentes estén próximos entre sí.1001 1 . para funciones de un mayor número de variables. f(a. el método algebraico más general es el método de Quine-McCluskey. Los pasos del método son: 1. siendo n el número de variables de la función. Construir una tabla de 2n casillas. A continuación aparecen las tablas para funciones entre 2 y 5 variables con el número decimal asociado a los términos canónicos. Cuando esto no es posible (funciones de más de tres variables) se disponen los términos en los límites de la tabla y se supone que los términos de un límite son adyacentes a los del límite opuesto.
b. Los grupos deben contener el mayor número posible de términos (el número de términos en cada grupo será siempre potencia de 2). En el caso de la expresión canónica en forma de suma de productos.11. Esta tabla es lo que se conoce como mapa de Karnaugh de la función. Ejemplo 40 2. O lo que es lo mismo.d)= ∑4(2. Construir la expresión reducida. 5. existe más de una solución. 15.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole - Los de la columna de la izquierda con los respectivos de la columna derecha.c. las casillas asociadas a términos que aparecen en ella se completan con 1 y el resto se dejan en blanco. 4. 14. 3. 9.7.5. En dichos casos. 29. Por cada agrupamiento se obtiene una expresión formada por las variables comunes a los términos adyacentes. Se realizan agrupamientos reiterados de términos adyacentes hasta que todos los términos hayan sido agrupados. Ejemplo: cd ab 00 01 00 01 11 10 0 4 12 8 11 10 1 5 1 1 1 1 3 7 2 6 14 13 9 1 15 1 11 1 10 Nota 2: Algunas funciones pueden agruparse de varias formas. Los términos adyacentes al 13 son: 12. Si la expresión está dada en forma de productos de sumas las casillas se completan con 0 en vez de 1. Ejemplo: cd ab 00 01 00 01 11 10 0 4 12 8 11 10 1 5 cd ab 00 01 2 6 11 10 1 5 1 1 1 3 7 00 01 11 10 0 4 12 8 1 1 1 3 7 2 6 14 1 13 1 15 1 9 11 14 1 13 1 15 1 9 11 1 10 1 10 Ejemplo 41. Nota 1: Para construir grupos mayores pueden utilizarse casillas que ya han sido previamente agrupadas. Simplificar la función f(a. 2. aquellas casillas etiquetadas con una entrada de la tabla de verdad para la cual la función toma el valor 1 se cubren con unos y el resto se deja vacío. 26.3.11. Proceso de simplificación. Los que están en la misma posición en ambas tablas (5 variables) Los términos adyacentes al 10 son 8.15) El cuadro de Karnaugh correspondiente es: 37 .10.
0011 7 .7.c.1011 2 .13) En la minimización de funciones incompletas los valores indefinidos se representan mediante X y actúan como comodines. b.101X 5-7 . Con salidas inhibidas: el valor de salida es indiferente.0001 3 . b. es necesario transformar la forma canónica a producto de sumas.01X1 = a bd bc 3-7-15-11 .3.0011 9 .1111 1-3 . llamadas funciones incompletas.3.0101 7 .001X 6-7 .00X1 9-11 . pudiendo ser su valor de salida 1 ó 0 indistintamente. Para ello. Los términos indefinidos se agrupan mediante el símbolo ∅.d) = ∑4(1.0111 14 .X11X = b+c Resultado: f (a.1011 2 . Ejemplo 42.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole cd ab 00 01 11 10 00 01 11 10 0 4 12 8 1 Grupos 1 3 7 12 6 14 3 . d ) = abd + b c + cd Para simplificar en forma de producto de sumas.9. 2.1111 11 .1001 11.0010 3 . c. No es necesario agruparlos.1011 10 . pero. d ) = (a + c) × (b + c) × (b + d ) Funciones incompletas Existen funciones que no están totalmente definidas. Combinaciones de entrada imposibles. El resultado sería: f(a.4.15) Grupos cd ab 00 01 11 10 00 01 11 10 0 4 12 8 1 .2.0110 7 .11)+∑∅(0.0110 7 .0111 6 . 38 . se pueden agrupar. En la forma canónica de la función se representan de forma separada los términos indefinidos del resto.1X11 2-3 .10.b.0X1X =a + c 0 15 0 14 10 0 9 0 11 6-7 .0111 3-7 .XX11 = cd 15 1 13 9 1 15 1 11 1 10 El resultado es: f (a. puede construirse la tabla de verdad y tomar los elementos de valor cero numerando de abajo a arriba.0011 11 . c .10X1 1-3-9-11 .0010 3 .011X 14-15 .b.111X 6-7-14-15 .6. Las razones son: 1.1110 15 .0111 15 .2.11.14.011X 0 2-3-6-7 .001X 2-3-10-11 .0X11 15-11 .0011 6 .X0X1 =b + d 01 0 5 13 3 7 02 06 2-3 .c.X01X = 10-11 . Sea f(a. si al agruparlos se obtiene un grupo mayor.d)= ∑4(1.1010 5 .
101X X13 9 1 11 1 10 2 .1011 10 .001X 2-3 .00XX = a b 2-3 .1010 Resultado: f (a. c.Lógica Proposicional Aplicación al diseño de Circuitos: Álgebra de Boole cd ab 00 01 11 10 00 X 0 1 1 1 01 X 4 11 10 12 8 5 3 7 15 Grupos X2 6 14 0 1 2 3 - 0000 0001 0010 0011 0-1 .001X b 2-3-10-11 . d ) = b c + ab 39 .000X 0-1-2-3 .X01X =c 10-11 . b.0010 3 .0011 11 .
Lógica Proposicional Ejercicios 7. siempre q n) p a no ser que q [2] Formalizar los razonamientos: " Si el resultado obtenido es superior al previsto en 5 unidades. innecesario si nos dejamos llevar por la precipitación. Una de las fuentes fundamentales." [3] Simplificar mediante Karnaugh las siguientes funciones lógicas: a) x + xy + y b) xy + xyz + y (x + z ) + y z c) wx + xy + yz + zw + w xyz + w x yz d) wxy z + wxyz + wxyz + wxyz + w xyz + w xyz + w x y z + w xyz + w xy z + w xyz e) vw( x + y + xz ) + v xz ( wy + x ( z + vy )) [4] Demostrar las siguientes propiedades de la función lógica O-exclusiva: a) Asociativa b) Conmutativa c) Existencia de elemento neutro e tal que x ⊕ e = x $ d) Existencia de Inverso (A todo elemento x se le puede hacer corresponder un elemento x tal que $ x⊕ x = e e) Distributiva del Producto respecto a la O-exclusiva: x ( y ⊕ z ) = xy ⊕ xz f) que mediante la O-exclusiva y la función AND se pueden realizar las otras dos operaciones fundamentales del álgebra de Boole: negación y suma (OR). será debido a no haber realizado el proceso a la temperatura adecuada o a la existencia de errores en los cálculos finales." " El cáncer no logrará curarse a no ser que se logre determinar su causa y se consiga encontrar fármacos adecuados o bien para prevenirlo o para curarlo. ha sido el "Boletín de Ejercicios" ofrecido en la asignatura "Lógica Informática" de la Escuela Universitaria de Ingeniería Técnica Informática de Gijón. se torna necesario si nos paramos a reflexionar sobre el mensaje que se pretende transmitir. Nota: Calcular el valor de 1 ⊕ x y de 1 ⊕ ((1 ⊕ x)(1 ⊕ y )) g) que x ⊕ y = x ⊕ y 40 . [1] Formalizar las siguientes expresiones: a) q si p b) p pero q c) como mínimo p d) p no obstante q e) q necesario para p f) q suficiente para p g) p a pesar de q h) no p a menos que q i) p sólo si q j) p sin embargo q k) p suficiente para q l) p siempre que q m) a veces p." " El análisis realizado. Ejercicios Los siguientes ejercicios se han recopilado de diversas fuentes.
Lógica Proposicional Ejercicios [5] Una función de tres variables f(a. c) Minimizar dichas expresiones. .∧ } el siguiente enunciado: " Si p entonces q y. ( s → p )) ∧ ( ¬ ( q ∧ t) ∧ ( q → t) )) → ¬ (r → w) ) [9] Determinar la validez de las siguientes fórmulas: a) (( ¬ p ∧ q ) ∨ ( p ∨ ¬ q )) → b) ( p ∧ ( q → p ) ) → p c) ( ¬ p → q ) → ( ( p ∧ ¬ q ) ∨ r ) ( ( p → ( q ∨ r ) ) → ( p → r )) [10] Obtener la FND de: a) ( p → ( p → q)) ∨ p∨ q b) ¬ ( p ∨ ¬ q) ∧ (¬ r ∨ s) [11] Obtener la FNC de: a) ¬ ( p → q ) ∨ p ∨ q b) (( p → q ) → r ) → s [12] Probar. b) Obtener las formas canónicas en forma de suma de productos y producto de sumas. En los demás casos posibles debe estar en estado uno. r . Nunca pueden estar más de tres variables en estado uno. p} ⇒ r b) [13] { p → (¬ q ∨ (r ∧ s)). [7] Formalizar utilizando las conectivas {¬ . si p1 entonces q1 y. la validez de los siguientes razonamientos: a) { p → q.b. a) Realizar la tabla de verdad de la función." [8] Formalizar el siguiente enunciado donde hemos notado "si p entonces q y en caso contrario r" de la siguiente forma: p → q. p . Realizar la expresión obtenida con puertas NOR y NAND. ∨ .c) debe tomar el valor cero cuando la variable b esté a uno y la variable a no está en estado uno. [6] Obtener la expresión algebraica mínima de una función lógica de cuatro variables que toma el valor uno cuando el número de variables que están en estado uno es superior al de las que se encuentran en estado cero. (r ∨ s )) ∧ ((r → ¬ w. en caso contrario. q → r . usando el algoritmo de resolución.Normalizar dicho enunciado. ¬ s} ⇒ ¬q Compruébese si los siguientes razonamientos son correctos o no: 41 .Estudiar la validez de la siguiente fórmula en la que se emplea la notación anterior: (( p → ( p ∨ r ). en caso contrario r1.
Si Demetrio fue segundo.-" Es suficiente whisky para que chocolate." A la radio: " Si la inflacción baja o si la peseta no se devalúa." c. Si eres descuidado no mereces que te feliciten. María promete casarse con Juan si y sólo si Juan promete casarse con María. publica un informe en el que asegura: "Los impuestos deben subir. o el general no ganará la batalla. Demetrio no fue segundo". No ginebra a menos que chocolate. Coclusión: no son suficientes 25 divisiones. Luego saldré temprano. Chocolate si y solo si jamón.-" Si Antonio ganó la carrera. entonces no ganó Antonio. Juan quiere a María y María no quiere a Juan". entonces Baltasar o Carlos fueron los segundos. los impuestos no subirán. Nunca tiene un juguete cuando se está riendo si no come un caramelo. respiro si y sólo si no llueve. no lo fue Carlos. 42 . Ha nevado. María no quiere a Juan si Juan no quiere a María. Si no llora." g." A la tele: " O bien baja la inflacción y se devalúa la peseta." Como consecuencia. habré programado un ciclo infinito solo si mi programa no termina. Algo tuyo se quema si y sólo si eres descuidado. Basta que el programa no comience o no finalice para que falle. por otra parte." h. Whisky. ríe sólo si tiene un juguete.-" El Ministro de Economía y Hacienda ha hecho las siguientes declaraciones: A la prensa: " Si los impuestos suben." [14]." j. Por tanto.-" No llora. De ahí que sea necesario no solamente especificar las condiciones iniciales sino también no programar un ciclo infinito para que el programa no falle. Si Baltasar fue segundo. Antonio ganó la carrera. pero la inflación bajará y la peseta no se devaluará.-" Si no especifico las condiciones iniciales mi programa no comenzará.-Le digo a un amigo: Cuando salgo sin paraguas. la inflacción bajará si y sólo si no se devalúa la peseta. b.-" Si no llueve salgo al campo. llueve." ¿ Fue consecuente con sus declaraciones a los medios de comunicación?. Si no es fácil conducir llegaré tarde si no salgo temprano. o bien los impuestos deben subir.-" Juan quiere a María si y sólo si María quiere a Juan y promete casarse con él. ¿ Es posible afirmar: (1) que bebió ginebra? (2) que no tomó chocolate?" i. Además. Luego come un caramelo. Por tanto. S i salgo al campo respiro. Por tanto si no mereces que te feliciten entonces es que un monte se quema. no es cierto que sean suficientes 25 divisiones y que se vayan a suministrar 3 alas de apoyo aéreo táctico.-" Si un monte se quema algo tuyo se quema." f. ríe. o se suministran 3 alas de apoyo aéreo táctico. " e.-"Si 25 divisiones son suficientes.-" Si ha nevado será difícil conducir. el general ganará la batalla. Por tanto.Lógica Proposicional Ejercicios a. d.
despertará. Estamos en veda. Según el hombre del tiempo. Si el príncipe la besa. [18] Si la Bella Durmiente despierta. ¿Cómo lo supo? [15] Don Juan Tenorio. A ello.Si Dios existe es todo amor y omnipotencia. De todos modos saldré sin paraguas. vivirán felices y comerán perdices si no estamos en veda. se pide decidir lógicamente qué puerta se debe abrir para liberar a la dama si es que existe. [19] Los dos carteles siguientes están colgados respectivamente a la puerta de las habitaciones 1 y 2. O la besa o no se despierta nadie. entonces amo a Inés" (se supone que la asesina era aquélla a la que Don Juan no amaba) [16].Dios no es amor o está dispuesto a erradicar el sufrimiento del mundo. entonces también amo a Juana" " O amo a María y a Juana o no amo a ninguna" " Si amo a María. a pesar de llevar 100 años dormida sigue de muy buen ver. CARTEL 2 EN UNA DE ESTAS HABITACIONES HAY UNA DAMA Y EN UNA DE ESTAS HABITACIONES HAY 43 .Dios no existe. entonces tenía un testigo".-En un juicio el fiscal argumenta: " Si el acusado es culpable. Entonces mi amigo responde: Entonces mañana. además de llover. [17]. que le costaron la vida. mañana estará despejado o hará niebla. ¿ Es lógico?. Sabiendo que en la misma habitación no puede haber una dama y un tigre y que puede haber dos damas y dos tigres. Ambas habitaciones están ocupadas. El príncipe la besará si está de buen ver. . " Amo a la última de las tres" " Si amo a Inés pero no a María. los habitantes del castillo también lo harán. hizo las siguientes declaraciones. . Como esto es un cuento. ¿ Se casan? ¿ Son felices? ¿ Comen perdices?. no llueve. . la princesa. habrá niebla.Existe sufrimiento en el mundo.Si Dios es incapaz de erradicar el sufrimiento del mundo entonces no es omnipotente. . el abogado defensor respondió inmediatamente: " Eso es falso". Por tanto: . El acusado decidió cambiar de abogado defensor. CARTEL 1 EN ESTA HABITACION HAY UNA DAMA Y EN LA OTRA UN TIGRE.del siguiente razonamiento: . Juana y María. Uno dice la verdad y otro miente. Si la princesa se despierta se casarán.Dios es capaz de erradicar el sufrimiento del mundo y está dispuesto a ello solo si no existe sufrimiento en el mundo.-Analizar la coherencia lógica .Lógica Proposicional Ejercicios Cuando está despejado. ¿Quién o quiénes son las asesinas?.no teológica . con respecto a las doncellas Inés.
como antes. que puede no haberla. éste afirmó que: ".Lógica Proposicional Ejercicios UN TIGRE. 44 . .. A la vista de todo ello nos preguntamos: ¿Es. Por otra parte. si bien lo cierto es que los ordenadores no hablan pero los informáticos existen.". buenas tardes: Es hora de que recapacitemos sobre los estudios de informática en vísperas del asentamiento de la titulación en nuestra Universidad. en la última reunión del Consejo de Universidades. afirmación que nos parece muy correcta.la Universidad titulará informáticos mientras los ordenadores no hablen . Se sabe que si los ordenadores hablasen los informáticos no existirían. por tanto. CARTEL 1 AL MENOS EN UNA DE ESTAS HABITACIONES HAY UNA DAMA CARTEL 2 HAY UN TIGRE EN LA OTRA HABITACION [20] Discurso sobre los estudios de Informática en clase de Lógica: Señoras. señores. coherente que la Universidad expida títulos de informática en la actualidad?.Suponiendo que los dos carteles siguientes dicen ambos la verdad o mienten ambos.. sabiendo. Deducir en qué habitación hay una dama...
r = Nos paramos a reflexionar sobre el mensaje que se pretende transmitir. y se desarrollan las expresiones resultantes hasta llegar a la demostración deseada. r = Se consigue encontrar fármacos adecuados para prevenirlo. ( ¬ q ∨ r) → p p = Análisis realizado es necesario. q = Haber realizado el proceso a la temperatura adecuada. r = Existencia de errores en los cálculos finales. q = Se logra determinar su causa. s = Se consigue encontrar fármacos adecuados para curarlo. q = Nos dejamos llevar por la precipitación. ¬ ( q ∧ ( r ∨ s )) → ¬ p ≡ p → ( q ∧ ( r ∨ s) ) [3] a) x + y b) x + y + z c) xw + xz + w y  xy + w z + xyz + wyz  Habría tres posibles soluciones  xy + w z + xyz + wxz  xy + w z + w xz + wyz  d) e) v xyz + vwxz + vwx + vwy [4] Para realizar las demostraciones se parte de que x ⊕ y = xy + xy . (q → ¬ p) ∧ (r → p) p = El cáncer logrará curarse. A continuación se presentan los primeros pasos de la demostración de asociatividad: 45 . Soluciones [1] a) p → q b) p ∧ q c) p d) p ∧ q e) p → q f) q → p g) p ∧ q [2] h) p → q i) p → q j) p ∧ q k) p → q l) q → p m) ( p ∨ ¬ p) ∧ q ≡ q n) ¬ q → p p = Resultado obtenido menor al previsto en 5 unidades.Lógica proposicional Soluciones 8.
r=F. 46 . w = F. b) ES válido. pues podemos encontrar varias interpretaciones que lo hagan Falso. puedo salir al campo. p = V. [5] La función. c) El razonamiento NO es válido. come un caramelo. t= V. q = V. pero la conclusión Falsa. ya que puede darse el caso de que ninguno de los dos quiera al otro. q = V.Forma normal conjuntiva: ( ¬ p ∨ q) ∧ ( p ∨ r ) . r = F [10] a) Al operar quedaría: ¬ p ∨ ¬ p ∨ q ∨ p ≡ b) ( ¬ p ∧ q ∧ ¬ r ) ∨ ( ¬ p ∧ q ∧ s) V [11] a) p ∨ q b) ( ¬ p ∨ q ∨ s ) ∧ (¬ r ∨ s ) [12] En ambos casos se llega a la cláusula vacía ⇒ Razonamiento correcto. e) NO es válido. ejemplo p = V. [13] a) SI es válido. ejemplo p = V. s = V. q = F. minimizada sería a + b [6] La expresión mínima sería: bcd + acd + abd + abc .Lógica proposicional Soluciones (x ⊕ y ) ⊕ z = ( x ⊕ y ) z + ( x ⊕ y)z = ( xy + xy) z + ( xy + xy )z = L = xy z + xyz + x yz + xyz Si desarrollásemos x ⊕ ( y ⊕ z) obtendríamos la misma expresión. c) NO es válida.El razonamiento NO es válido. d) El razonamiento NO es válido porque puede darse el caso de NO salir temprano y llegar tarde habiendo nevado y siendo difícil conducir. Cumpliéndose todas las premisas. [7] ( p → q ) ∧ ( ¬ p → ( ( p1 → q1) ∧ ( ¬ p1 → r1)) ) [8] ( p → q) ∧ ( ¬ p → r ) . r = F b) SI es válida. [9] a) NO es válida. Luego no se deduce que respire si y solo si no llueve. lloviendo y respirar. por ejemplo. Antonio ganó la carrera. y las premisas serían ciertas. Las demás demostraciones se realizarían de forma similar. con lo cual habríamos demostrado la propiedad asociativa.
el acusado sería culpable. pues las amaba a las tres. . [18] Se casan. h) NO se puede deducir ninguna de los dos. i) El razonamiento ES correcto. [19] .Lógica proposicional Soluciones f) NO es válido. se sigue que la universidad expenda títulos de Informática a partir de las premisas. pero no comen perdices porque estamos en veda. g) NO es correcto. El razonamiento es correcto. ni que bebiese Ginebra ni que no tomase chocolate. j) El razonamiento ES correcto.La única posibilidad es que los dos carteles digan la verdad y habría una dama en la habitación 2 y un tigre en la habitación 1.La única forma de que un cartel diga la verdad y otro mienta es que el Cartel 1 mienta y el Cartel 2 diga la verdad. [16] Si es Falsa la sentencia "Si el acusado es culpable entonces tenía un testigo". [15] Ninguna de ellas era la asesina. [17] El razonamiento es correcto en términos lógicos. luego el antecedente es Verdadero. por la tabla de verdad de la implicación. viven felices. [14] Amb as expresiones se deducen lógicamente suponiendo que todas las frases sean Verdaderas. es decir. 47 . [20] Sí. el antecedente es Verdadero y el consecuente Falso. se puede comprobar que sólo existe esa posibilidad. Con lo cual habría un tigre en la habitación 1 y una dama en la habitación 2.
(1992) (1993) (1970) (1996) [Dijkstra. David S.S. Fitting First-Order Logic and Automated Theorem Proving Springer-Verlag. Nilsson Logical foundations of Artificial Intelligence Morgan Kaufmann Publishers. Mandado Sistemas Electrónicos Digitales Ed. Whitesitt Boolean Algebra and its Applications Addison-Wesley (1988) (1991) (1961) 48 . B. Abramsky. C. Maibaum Handbook of Logic in Computer Science Oxford Science Publications [Ben-Ari. F. E. Genesereth. 91] E. 87] M. Gries.M. T. Grassmann. [Grassmann. S. 97] (1997) [Maier. Birkhoff. Kelly The Essence of Logic Prentice Hall David Maier. Inc. Warren Computing with Logic The Benjamin/Cummings Publishing Company. Tremblay Matemática Discreta y Lógica Prentice-Hall [Gries. (1987) (1996) (1994) [Kelly. Marcombo [Sperschneider. W. R. Bartee Modern Applied Algebra McGraw-Hill [Burke. 70] G. T. Sperschneider. Schneider A Logical Approach to Discrete Math Springer-Verlag J. 93] M. G.J. Burke. K. (1990) (1996) [Genesereth. 91] V. 96] E. 88] E. [Birkhoff. D. C. 94] D.Lógica proposicional Bibliografía Bibliografía [Abramsky. Scholten Predicate Calculus and Program Semantics Springer-Verlag [Fitting. 96] W. 96] M. N. Dijkstra. E. 92] S. Gabbay. 61] J. J. Antoniou Logic: A foundation for Computer Science Addison-Wesley Publishing Company [Whitesitt. Foxley Logic and its Applications Prentice Hall Intl. Ben-Ari Mathematical Logic for Computer Science Prentice Hall Intl. 88] (1988) [Mandado. Inc. 2nd Ed.
6 Asociativa. 12 nodos de éxito. 18 teoría semántica. 22 Elemento neutro. 24 C circuito combinacional. 28 T tabla de verdad. 23 producto canónico. 4 Fórmula Válida. 5 D De Morgan. 18 término canónico. 26 Distributiva. 3 función Booleana. 14 M MAXTERM. 3 N nodo de fallo. 25 V valor de una fórmula. 21 Álgebra de Boole. 22 Completud del Algoritmo de Resolución Proposicional. 15 cláusula Horn. 27 circuito digita. 13 F forma canónica. 27 49 . 28 modelo. 19 R razonamiento. 5 correcto. 26 circuitos digitales combinacionales. 21 Álgebra de Boole bivaluada. 3 Sintaxis. 3 variable booleana. 22 equivalencia lógica. 10 árbol de resolución. 8 Formas Normales. 13 Conmutativa. 5 Involución. 8 Forma Normal Disyuntiva. 28 pruebas subordinadas. 16 árbol semántico. 2 álgebra de Boole. 9 cláusula inicial. 9 Commutativa. 3 teoría de la prueba. 14 suma canónica. 15 S Semántica. 14 Tautología. 23 E Elemento inverso. 3 Interpretación. 27 U Unicidad del complementario. 15 cláusulas resolubles. 8 Fórmula Insatisfacible. 24 Alfabeto. 23 interpretación. 8 cláusula cabeza. 28 MINTERM. 2 subsunción. 15 Resolución proposicional. 9 Forma Normal Conjuntiva. 27 I Idempotencia. 4 Fórmula Satisfacible. 5 regla de resolución. 8 resolvente. 22 Dominación. 9 Resolución Lineal. 9 resolvente de entrada. 6 tautología. 25 L literal puro. 6 P Principio de dualidad. 4 Estrategias de resolución. 21 cláusula.Lógica proposicional Indice Indice A Absorción. 22 consecuencia lógica. 28 Forma Clausal. 22 Algoritmo de resolución proposicional. 6 nodo de inferencia.
LOGICA-MATEMATICA (1)
Lógica T3 25-03-2013 (Revisado)
Anon - La Logica
1diapositivasdelgica-120823210234-phpapp02.ppt

References: Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución

 resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución

resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 

resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución

 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución

Resolución 

Resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 

Resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 Resolución 
 Resolución 
 Resolución 
 resolución