tema 4
TRANSCRIPT
PD Tema 4: Formas normales
Lógica informática (2012–13)Tema 4: Formas normales
José A. Alonso JiménezAndrés Cordón Franco
María J. Hidalgo Doblado
Grupo de Lógica ComputacionalDepartamento de Ciencias de la Computación e I.A.
Universidad de Sevilla
1 / 20
PD Tema 4: Formas normales
Tema 4: Formas normales
1. Forma normal conjuntiva
2. Forma normal disyuntiva
3. Cálculo de formas normales mediante tableros semánticos
2 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Tema 4: Formas normales
1. Forma normal conjuntivaDefinición de forma normal conjuntivaAlgoritmo de cálculo de forma normal conjuntivaDecisión de validez mediante FNC
2. Forma normal disyuntiva
3. Cálculo de formas normales mediante tableros semánticos
3 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Definición de forma normal conjuntiva
Forma normal conjuntivaI Átomos y literales:
I Def.: Un átomo es una variable proposicional (p.e. p, q, . . . ).I Def.: Un literal es un átomo o su negación (p.e. p,¬p, q,¬q, . . . ).I Notación: L, L1, L2, . . . representarán literales.
I Forma normal conjuntiva:I Def.: Una fórmula está en forma normal conjuntiva (FNC) si es
una conjunción de disyunciones de literales; es decir, es de la forma(L1,1 ∨ · · · ∨ L1,n1) ∧ · · · ∧ (Lm,1 ∨ · · · ∨ Lm,nm).
I Ejemplos: (¬p ∨ q) ∧ (¬q ∨ p) está en FNC.(¬p ∨ q) ∧ (q → p) no está en FNC.
I Def.: Una fórmula G es una forma normal conjuntiva (FNC) de lafórmula F si G está en forma normal conjuntiva y es equivalente aF .
I Ejemplo: Una FNC de ¬(p ∧ (q → r)) es (¬p ∨ q) ∧ (¬p ∨ ¬r).
4 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Algoritmo de cálculo de forma normal conjuntiva
Algoritmo de cálculo de forma normal conjuntivaAlgoritmo: Aplicando a una fórmula F los siguientes pasos se obtieneuna forma normal conjuntiva de F , FNC(F ):1. Eliminar los bicondicionales usando la equivalencia
A↔ B ≡ (A→ B) ∧ (B → A) (1)2. Eliminar los condicionales usando la equivalencia
A→ B ≡ ¬A ∨ B (2)3. Interiorizar las negaciones usando las equivalencias
¬(A ∧ B) ≡ ¬A ∨ ¬B (3)¬(A ∨ B) ≡ ¬A ∧ ¬B (4)¬¬A ≡ A (5)
4. Interiorizar las disyunciones usando las equivalenciasA ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) (6)(A ∧ B) ∨ C ≡ (A ∨ C) ∧ (B ∨ C) (7)
5 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Algoritmo de cálculo de forma normal conjuntiva
Ejemplos de cálculo de forma normal conjuntivaI Ejemplo de cálculo de una FNC de ¬(p ∧ (q → r)):
¬(p ∧ (q → r))≡ ¬(p ∧ (¬q ∨ r)) [por (2)]≡ ¬p ∨ ¬(¬q ∨ r) [por (3)]≡ ¬p ∨ (¬¬q ∧ ¬r) [por (4)]≡ ¬p ∨ (q ∧ ¬r) [por (5)]≡ (¬p ∨ q) ∧ (¬p ∨ ¬r) [por (6)]
I Ejemplo de cálculo de una FNC de (p → q) ∨ (q → p):(p → q) ∨ (q → p)
≡ (¬p ∨ q) ∨ (¬q ∨ p) [por (2)]≡ ¬p ∨ q ∨ ¬q ∨ p
6 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Algoritmo de cálculo de forma normal conjuntiva
Cálculo de forma normal conjuntivaI Ejemplo de cálculo de una FNC de (p ↔ q)→ r :
(p ↔ q)→ r≡ (p → q) ∧ (q → p)→ r [(1)]≡ ¬((p → q) ∧ (q → p)) ∨ r [(2)]≡ ¬((¬p ∨ q) ∧ (¬q ∨ p)) ∨ r [(2)]≡ (¬(¬p ∨ q) ∨ ¬(¬q ∨ p)) ∨ r [(3)]≡ ((¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p)) ∨ r [(4)]≡ ((p ∧ ¬q) ∨ (q ∧ ¬p)) ∨ r [(5)]≡ (((p ∧ ¬q) ∨ q) ∧ ((p ∧ ¬q) ∨ ¬p)) ∨ r [(6)]≡ (((p ∨ q) ∧ (¬q ∨ q)) ∧ ((p ∨ ¬p) ∧ (¬q ∨ ¬p))) ∨ r [(7)]≡ (((p ∨ q) ∧ (¬q ∨ q)) ∨ r) ∧ (((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ r) [(7)]≡ (((p ∨ q) ∨ r) ∧ ((¬q ∨ q) ∨ r)) ∧ (((p ∨ ¬p) ∨ r) ∧ ((¬q ∨ ¬p) ∨ r)) [(7)]≡ (p ∨ q ∨ r) ∧ (¬q ∨ q ∨ r) ∧ (p ∨ ¬p ∨ r) ∧ (¬q ∨ ¬p ∨ r)≡ (p ∨ q ∨ r) ∧ (¬q ∨ ¬p ∨ r)
7 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Decisión de validez mediante FNC
Procedimiento de decisión de validez mediante FNCI Literales complementarios:
I El complementario de un literal L es Lc =
{¬p si L = p;p si L = ¬p.
I Propiedades de reducción de tautologías:I F1 ∧ · · · ∧ Fn es una tautología syss F1, . . . , Fn lo son.I L1 ∨ · · · ∨Ln es una tautología syss {L1, . . . , Ln} contiene algún par
de literales complementarios (i.e. existen i , j tales que Li = Lcj ).
I Algoritmo de decisión de tautologías mediante FNCI Entrada: Una fórmula F .I Procedimiento:
1. Calcular una FNC de F .2. Decidir si cada una de las disyunciones de la FNC tiene algún par
de literales complementarios.
8 / 20
PD Tema 4: Formas normalesForma normal conjuntiva
Decisión de validez mediante FNC
Ejemplos de decisión de validez mediante FNCI ¬(p ∧ (q → r)) no es tautología:
FNC(¬(p ∧ (q → r))) = (¬p ∨ q) ∧ (¬p ∨ ¬r)Contramodelos de ¬(p ∧ (q → r)):
I1 tal que I1(p) = 1 y I1(q) = 0I2 tal que I2(p) = 1 y I2(r) = 1
I (p → q) ∨ (q → p) es tautología:FNC((p → q) ∨ (q → p)) = ¬p ∨ q ∨ ¬q ∨ p
I (p ↔ q)→ r no es tautología:FNC((p ↔ q)→ r) = (p ∨ q ∨ r) ∧ (¬q ∨ ¬p ∨ r)Contramodelos de (p ↔ q)→ r :
I1 tal que I1(p) = 0, I1(q) = 0 y I1(r) = 0I2 tal que I2(p) = 1, I2(q) = 1 y I2(r) = 0
9 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Tema 4: Formas normales
1. Forma normal conjuntiva
2. Forma normal disyuntivaDefinición de forma normal disyuntivaAlgoritmo de cálculo de forma normal disyuntivaDecisión de satisfacibilidad mediante FND
3. Cálculo de formas normales mediante tableros semánticos
10 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Definición de forma normal disyuntiva
Definición de forma normal disyuntivaI Def.: Una fórmula está en forma normal disyuntiva (FND) si es
una disyunción de conjunciones de literales; es decir, es de laforma(L1,1 ∧ · · · ∧ L1,n1) ∨ · · · ∨ (Lm,1 ∧ · · · ∧ Lm,nm).
I Ejemplos: (¬p ∧ q) ∨ (¬q ∧ p) está en FND.(¬p ∧ q) ∨ (q → p) no está en FND.
I Def.: Una fórmula G es una forma normal disyuntiva (FND) de lafórmula F si G está en forma normal disyuntiva y es equivalentea F .
I Ejemplo: Una FND de ¬(p ∧ (q → r)) es ¬p ∨ (q ∧ ¬r).
11 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Algoritmo de cálculo de forma normal disyuntiva
Algoritmo de cálculo de forma normal disyuntivaAlgoritmo: Aplicando a una fórmula F los siguientes pasos se obtieneuna forma normal disyuntiva de F , FND(F ):1. Eliminar los bicondicionales usando la equivalencia
A↔ B ≡ (A→ B) ∧ (B → A) (1)2. Eliminar los condicionales usando la equivalencia
A→ B ≡ ¬A ∨ B (2)3. Interiorizar las negaciones usando las equivalencias
¬(A ∧ B) ≡ ¬A ∨ ¬B (3)¬(A ∨ B) ≡ ¬A ∧ ¬B (4)¬¬A ≡ A (5)
4. Interiorizar las conjunciones usando las equivalenciasA ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) (6)(A ∨ B) ∧ C ≡ (A ∧ C) ∨ (B ∧ C) (7)
12 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Algoritmo de cálculo de forma normal disyuntiva
Ejemplos de cálculo de forma normal disyuntivaI Ejemplo de cálculo de una FND de ¬(p ∧ (q → r)):
¬(p ∧ (q → r))≡ ¬(p ∧ (¬q ∨ r)) [por (2)]≡ ¬p ∨ ¬(¬q ∨ r) [por (3)]≡ ¬p ∨ (¬¬q ∧ ¬r) [por (4)]≡ ¬p ∨ (q ∧ ¬r) [por (5)]
I Ejemplo de cálculo de una FND de ¬(¬p ∨ ¬q → ¬(p ∧ q)):¬(¬p ∨ ¬q → ¬(p ∧ q))
≡ ¬(¬(¬p ∨ ¬q) ∨ ¬(p ∧ q)) [por (2)]≡ ¬¬(¬p ∨ ¬q) ∧ ¬¬(p ∧ q) [por (4)]≡ (¬p ∨ ¬q) ∧ (p ∧ q) [por (5)]≡ (¬p ∧ (p ∧ q)) ∨ (¬q ∧ (p ∧ q)) [por (7)]≡ (¬p ∧ p ∧ q) ∨ (¬q ∧ p ∧ q)
13 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Decisión de satisfacibilidad mediante FND
Procedimiento de decisión de satisfacibilidad medianteFND
I Propiedades de reducción de satisfacibilidad:I F1 ∨ · · · ∨ Fn es satisfacible syss alguna de las fórmulas F1, . . . , Fn
lo es.I L1 ∧ · · · ∧ Ln es satisfacible syss {L1, . . . , Ln} no contiene ningún
par de literales complementarios.I Algoritmo de decisión de satisfacibilidad mediante FND:
I Entrada: Una fórmula F .I Procedimiento:
1. Calcular una FND de F .2. Decidir si alguna de las conjunciones de la FND no tiene un par
de literales complementarios.
14 / 20
PD Tema 4: Formas normalesForma normal disyuntiva
Decisión de satisfacibilidad mediante FND
Ejemplos de decisión de satisfacibilidad mediante FNDI ¬(p ∧ (q → r)) es satisfacible:
FND(¬(p ∧ (q → r))) = ¬p ∨ (q ∧ ¬r)Modelos de ¬(p ∧ (q → r)):
I1 tal que I1(p) = 0I2 tal que I2(q) = 1 y I2(r) = 0
I ¬(¬p ∨ ¬q → ¬(p ∧ q)) es insatisfacible:FND(¬(¬p ∨ ¬q → ¬(p ∧ q))) = (¬p ∧ p ∧ q) ∨ (¬q ∧ p ∧ q)
15 / 20
PD Tema 4: Formas normalesCálculo de formas normales mediante tableros semánticos
Tema 4: Formas normales
1. Forma normal conjuntiva
2. Forma normal disyuntiva
3. Cálculo de formas normales mediante tableros semánticosForma normal disyuntiva por tablerosForma normal conjuntiva por tableros
16 / 20
PD Tema 4: Formas normalesCálculo de formas normales mediante tableros semánticos
Forma normal disyuntiva por tableros
Forma normal disyuntiva por tablerosI Prop.: Sea F una fórmula. Si las hojas abiertas de un tablero
completo de {F} son {L1,1, . . . , L1,n1}, . . . , {Lm,1, . . . , Lm,nm},entonces una forma normal disyuntiva de F es(L1,1 ∧ · · · ∧ L1,n1) ∨ · · · ∨ (Lm,1 ∧ · · · ∧ Lm,nm).
17 / 20
PD Tema 4: Formas normalesCálculo de formas normales mediante tableros semánticos
Forma normal disyuntiva por tableros
Forma normal disyuntiva por tablerosI Ejemplo: Forma normal disyuntiva de ¬(p ∨ q → p ∧ q).
¬(p ∨ q → p ∧ q)
p ∨ q,¬(p ∧ q)
p,¬(p ∧ q)
p,¬p
⊥
p,¬q
q,¬(p ∧ q)
q,¬p q,¬q
⊥
Una forma normal disyuntiva de ¬(p ∨ q → p ∧ q) es(p ∧ ¬q) ∨ (q ∧ ¬p).
18 / 20
PD Tema 4: Formas normalesCálculo de formas normales mediante tableros semánticos
Forma normal conjuntiva por tableros
Forma normal conjuntiva por tablerosI Prop.: Sea F una fórmula. Si las hojas abiertas de un tablero
completo de {¬F} son {L1,1, . . . , L1,n1}, . . . , {Lm,1, . . . , Lm,nm},entonces una forma normal conjuntiva de F es(Lc
1,1 ∨ · · · ∨ Lc1,n1) ∧ · · · ∧ (Lc
m,1 ∨ · · · ∨ Lcm,nm).
I Ejemplo: Forma normal conjuntiva de p ∨ q → p ∧ q.I Un árbol completo ¬(p ∨ q → p ∧ q) está en la transparencia
anterior.I Una forma normal disyuntiva de ¬(p ∨ q → p ∧ q) es
(p ∧ ¬q) ∨ (q ∧ ¬p).I Una forma normal conjuntiva de p ∨ q → p ∧ q es
(¬p ∨ q) ∧ (¬q ∨ p).p ∨ q → p ∧ q ≡ ¬¬(p ∨ q → p ∧ q)
≡ ¬((p ∧ ¬q) ∨ (q ∧ ¬p))≡ ¬(p ∧ ¬q) ∧ ¬(q ∧ ¬p))≡ (¬p ∨ ¬¬q) ∧ (¬q ∨ ¬¬p))≡ (¬p ∨ q) ∧ (¬q ∨ p))
19 / 20
PD Tema 4: Formas normalesBibliografía
Bibliografía1. C. Badesa, I. Jané y R. Jansana Elementos de lógica formal.
(Ariel, 2000)Cap. 8 (Equivalencia lógica) y 10 (Formas normales).
2. M. Ben–Ari, Mathematical logic for computer science (2nd ed.).(Springer, 2001)
Cap. 2 (Propositional calculus: formulas, models, tableaux).3. J.A. Díez Iniciación a la Lógica, (Ariel, 2002)
Cap. 3 (Semántica formal. Consecuencia lógica).4. M. Huth y M. Ryan Logic in computer science: modelling and
reasoning about systems. (Cambridge University Press, 2000)Cap. 1 (Propositional logic).
5. E. Paniagua, J.L. Sánchez y F. Martín Lógica computacional(Thomson, 2003)
Cap. 4.4 (Formas normales).
20 / 20