Logica y Programacion

Formas Normales

Antonia M. Chavez, Agustn Riscos, Carmen Graciani

Dpto. Ciencias de la Computacion e Inteligencia ArtificialUniversidad de Sevilla

Introduccion

Simplificar las formulas preservando su significado Reducir el numero de conectivas Cambiar la estructura de la formula

Objetivo: Resolver facilmente los problemas desatisfacibilidad, validez, consecuencia logica

Inconvenientes: Aumento del tamano de la formula Complejidad del proceso de normalizacion

Marco Teorico: Literales

Definiciones: Si F es un smbolo proposicional, entonces F es un literal

positivo Si F es un smbolo proposicional, entonces F es un literal

negativo F es un literal si y solo si F es literal positivo o negativo

Literales: L,L1,L2, . . .

Complementario de un literal: L =

{p si L = pp si L = p

Literales de una formula: lit(F )

Ejemplos: lit(p ((q) r)) = {p,q, r}

Implementacion

Equivalencia logica

F y G son equivalentes si se verifica |= F G

Representacion: F G

F G si y solo si para toda interpretacion I de {F ,G} setiene sig(F , I ) = sig(G , I )

Prueba: D-I: Si para toda interpretacion I ocurre sig(F , I ) = sig(G , I ),

entonces es cierto que para toda I tenemos: I |= F G . Y siesto es para toda I , entonces podemos afirmar que |= F G .Que es lo mismo que decir F G .

Equivalencia logica

F y G son equivalentes si se verifica |= F G

Representacion: F G

F G si y solo si para toda interpretacion I de {F ,G} setiene sig(F , I ) = sig(G , I )

Prueba: I-D: F G implica |= F G . Esto significa que para

cualquier interpretacion I , se tiene cierta F G . De esto,para cualquier interpretacion I , se tiene que I |= F G y, a lavez, I |= G F . Razonemos por reduccion al absurdo, si noocurriena que sig(F , I ) = sig(G , I ), se tendra uno de lossiguientes casos:

sig(F , I ) = True y sig(G , I ) = False, lo cual lleva aI 6|= F G

sig(F , I ) = False y sig(G , I ) = True, lo cual lleva aI |= G F .

Equivalencia logica

F y G son equivalentes si se verifica |= F G

Representacion: F G

F G si y solo si para toda interpretacion I de {F ,G} setiene sig(F , I ) = sig(G , I )

Ejemplos:p q (p q) (q p)p q (p) qp q ((p) (q))p q ((p) (q))

Propiedades de la equivalencia logica

Las conectivas preservan la equivalencia: Si F F , entonces F F

Si F F , G G y {,,,}, entoncesF G F G

Propiedad de las subformulas equivalentes: Sea G una subformula de F y F la obtenida sustituyendo una

ocurrencia de G en F por G . Si G G , entonces F F

Leyes de equivalencia logica

Idempotencia: F F F ,F F F

Conmutatividad: F G G F ,F G G F

Asociatividad: F (G H) (F G ) H,F (G H) (F G ) H

Distributividad: F (G H) (F G ) (F H),F (G H) (F G ) (F H)

Doble negacion: F F

Leyes de De Morgan: (F G ) F G ,(F G ) F G

Forma normal negativa

Definicion de forma normal negativa: Si F es atomica, entonces F y F son formas normales

negativas Si F y G son formas normales negativas, entonces (F G) y

(F G) tambien lo son.

Ejemplos (p q) (q p) es una forma normal negativa (p q) (q p) no es una forma normal negativa (p q) no es una forma normal negativa

Transformacion a forma normal negativa

Objetivo: Dada una formula F , obtener una formula en formanormal negativa G tal que F G .

Procedimiento fnn(F ) (Seguir el orden) Primero: Eliminacion de equivalencias

p q (p q) (q p) Segundo: Eliminacion de implicaciones

p q p q Tercero: Interiorizacion de negaciones

(p q) p q(p q) p qp p((p q)) p q((p) q) p q

Transformacion a forma normal negativa

Ejemplos:fnn(p q) = (p q) (q p)fnn((p (q)) r) = (p q) rfnn((p (q r)) s) = ((p (q r)) s)

Propiedades: fnn(F ) es una forma normal negativa fnn(F ) F

Forma normal conjuntiva

Disyunciones extendidas: Si F es un literal, entonces F es una disyuncion extendida Si F y G son disyunciones extendidas, entonces (F G)

tambien lo es Ejemplos:

p (q r) es una disyuncion extendida p (q r) no es una disyuncion extendida

Formulas en forma normal conjuntiva: Si F es una disyuncion extendida, entonces F es una forma

normal conjuntiva Si F y G son formas normales conjuntivas, entonces (F G)

tambien lo es Ejemplos: Ambas son equivalentes, pero una es FNC y otra no

(p q) (q p) es una forma normal conjuntiva (p q) (q p) no es una forma normal conjuntiva

Transformacion en forma normal

conjuntiva

Objetivo: Dada una formula F , obtener una formula en formanormal conjuntiva G tal que F G

Procedimiento fnc(F ) Transformacion a forma normal negativa Interiorizacion de las disyunciones

p (q r) (p q) (p r)(p q) r (p r) (q r)

Transformacion en forma normal

conjuntiva

Ejemplos:fnc(p (q r)) = p (q r)fnc((p (q r))) = (p q) (p r)

fnc((p r)) = (((p r) (pp)) ((r r) (r p)))

Propiedades: fnc(F ) es una forma normal conjuntiva fnc(F ) F

Forma normal disyuntiva

Conjunciones extendidas: Si F es un literal, entonces F es una conjuncion extendida Si F y G son conjunciones extendidas, entonces (F G)

tambien lo es Ejemplos:

p (q r) es una conjuncion extendida p (q r) no es una conjuncion extendida

Formulas en forma normal disyuntiva: Si F es una conjuncion extendida, entonces F esta en forma

normal disyuntiva Si F y G estan en forma normal disyuntiva, entonces (F G)

tambien lo esta Ejemplos:

(p q) (q p) esta una forma normal disyuntiva (p q) (q p) no esta una forma normal disyuntiva

Transformacion en forma normal

disyuntiva

Objetivo: Dada una formula F , obtener una formula en formanormal disyuntiva G tal que F G .

Procedimiento fnd(F ) Transformacion a forma normal negativa Interiorizacion de las conjunciones

p (q r) (p q) (p r)(p q) r (p r) (q r)

Transformacion en forma normal

disyuntiva

Ejemplos:fnd(p (q r)) = (p q) (p r)fnd((p (q r))) = (p (q r))

Propiedades: fnd(F ) es una forma normal disyuntiva fnd(F ) F

Ejercicios

Sea F = (p q) [(q r) (p s)]. Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

Sea F = [(p r) (q r)] (p q). Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

Ejercicios

Sea F = (p q) [(q r) (p s)]. Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

F (p q) [(q r) (p s)]

[(p q) (q p)] [(q r) (p s)]

[(p q) (q p)] [(q r) (p s)]

[(p q) (q p)] [(q r) (p s)]

(p q) (q p) [(q r) (p s)]

(p q) (q p) [(q r) (p s)]

Ejercicios

Sea F = (p q) [(q r) (p s)]. Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

fnn(F ) = (p q) (q p) [(q r) (p s)]

(p q) (q p) [(q (p s)) (r (p s))]

(p q) (q p) (q p) (q s)

(r p) (r s) (p q) (q p) (q s) (r p) (r s)

Ejercicios

Sea F = (p q) [(q r) (p s)]. Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

fnn(F ) = (p q) (q p) [(q r) (p s)]

[(p (q p)) (q (q p))] [(q r) (p s)]

[(p q) (p p) (q q) (q p)]

[(q r) (p s)] [(p q) (q p)] [(q r) (p s)]

Ejercicios

Sea F = (p q) [(q r) (p s)]. Se pide determinarformulas equivalentes a F en Forma Normal Negativa, FormaNormal Disyuntiva y Forma Normal Conjuntiva.

fnn(F ) = (p q) (q p) [(q r) (p s)]

[(p q) (q p)] [(q r) (p s)]

[(p q) ((q r) (p s))]

[(q p) ((q r) (p s))] [(p q) (q r)] [(p q) (p s)]

[(q p) ((q r) (p s))] (p q r) [(q p) ((q r) (p s))]

(p q r) [(q p) (q r)]

[(q p) (p s)]

(p q r) (q p s)

Bibliografa

Alonso Jimenez, J.A. Logica computacional (Univ. de Sevilla,1997) Cap. 5: Equivalencias y formas normales

Chang, C.L. y Lee, R.C.T. Symbolic Logic and MechanicalTheorem Proving. (Academic Press, 1973) Cap. 2: The propositional logic

Fitting, M. FirstOrder Logic and Automated TheoremProving (2nd, ed.) (Springer, 1996) Cap. 2: Propositional Logic

Genesereth, M.R. y Nilsson, N.J. Logical Foundations ofArtificial Intelligence. (Morgan Kaufmann, 1987) Cap. 2: Propositional Logic

Paulson, L. Logic and Proof (University of Cambridge, 2003)http://www.cl.cam.ac.uk/Teaching/2003/LogicProof Cap. 2: Propositional logic