Forma Normal En Logica

PD Tema 4: Formas normales

Lógica informática (2011–12)
Tema 4: Formas normales José A. Alonso Jiménez Andrés Cordón Franco María J. Hidalgo Doblado
Grupo de Lógica Computacional Departamento 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 deformas normales mediante tableros semánticos

2 / 20

PD Tema 4: Formas normales Forma normal conjuntiva

Tema 4: Formas normales
1. Forma normal conjuntiva Definición de forma normal conjuntiva Algoritmo de cálculo de forma normal conjuntiva Decisión de validez mediante FNC 2. Forma normal disyuntiva 3. Cálculo de formas normales mediante tableros semánticos

3 / 20

PD Tema 4: Formasnormales Forma normal conjuntiva Definición de forma normal conjuntiva

Forma normal conjuntiva
Átomos y literales:
Def.: Un átomo es una variable proposicional (p.e. p, q, . . . ). Def.: Un literal es un átomo o su negación (p.e. p, ¬p, q, ¬q, . . . ). Notación: L, L1 , L2 , . . . representarán literales.

Forma normal conjuntiva:
Def.: Una fórmula está en forma normal conjuntiva (FNC) si esuna conjunción de disyunciones de literales; es decir, es de la forma (L1,1 ∨ · · · ∨ L1,n1 ) ∧ · · · ∧ (Lm,1 ∨ · · · ∨ Lm,nm ). Ejemplos: (¬p ∨ q) ∧ (¬q ∨ p) está en FNC. (¬p ∨ q) ∧ (q → p) no está en FNC. Def.: Una fórmula G es una forma normal conjuntiva (FNC) de la fórmula F si G está en forma normal conjuntiva y es equivalente a F. Ejemplo: Una FNC de ¬(p ∧ (q → r )) es (¬p ∨ q) ∧ (¬p ∨ ¬r ).4 / 20

PD Tema 4: Formas normales Forma normal conjuntiva Algoritmo de cálculo de forma normal conjuntiva

Algoritmo de cálculo de forma normal conjuntiva
Algoritmo: Aplicando a una fórmula F los siguientes pasos se obtiene una forma normal conjuntiva de F , FNC(F ): 1. Eliminar los bicondicionales usando la equivalencia A ↔ B ≡ (A → B) ∧ (B → A) 2. Eliminar los condicionales usando laequivalencia A → B ≡ ¬A ∨ B 3. Interiorizar las negaciones usando las equivalencias ¬(A ∧ B) ≡ ¬A ∨ ¬B ¬(A ∨ B) ≡ ¬A ∧ ¬B ¬¬A ≡ A 4. Interiorizar las disyunciones usando las equivalencias A ∨ (B ∧ C ) ≡ (A ∨ B) ∧ (A ∨ C ) (A ∧ B) ∨ C ≡ (A ∨ C ) ∧ (B ∨ C ) (1) (2) (3) (4) (5) (6) (7)

5 / 20

PD Tema 4: Formas normales Forma normal conjuntiva Algoritmo de cálculo de forma normal conjuntivaEjemplos de cálculo de forma normal conjuntiva
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)] 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 Tema4: Formas normales Forma normal conjuntiva Algoritmo de cálculo de forma normal conjuntiva

Cálculo de forma normal conjuntiva
Ejemplo de cálculo de una FNC de (p ↔ q) → r : (p ↔ q) → r ≡ (p → q) ∧ (q → p) → r ≡ ¬((p → q) ∧ (q → p)) ∨ r ≡ ¬((¬p ∨ q) ∧ (¬q ∨ p)) ∨ r ≡ (¬(¬p ∨ q) ∨ ¬(¬q ∨ p)) ∨ r ≡ ((¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p)) ∨ r ≡ ((p ∧ ¬q) ∨ (q ∧ ¬p)) ∨ r ≡ (((p ∧ ¬q) ∨ q) ∧ ((p ∧ ¬q) ∨ ¬p)) ∨ r≡ (((p ∨ q) ∧ (¬q ∨ q)) ∧ ((p ∨ ¬p) ∧ (¬q ∨ ¬p))) ∨ r ≡ (((p ∨ q) ∧ (¬q ∨ q)) ∨ r ) ∧ (((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ r ) ≡ (((p ∨ q) ∨ r ) ∧ ((¬q ∨ q) ∨ r )) ∧ (((p ∨ ¬p) ∨ r ) ∧ ((¬q ∨ ¬p) ∨ r )) ≡ (p ∨ q ∨ r ) ∧ (¬q ∨ q ∨ r ) ∧ (p ∨ ¬p ∨ r ) ∧ (¬q ∨ ¬p ∨ r ) ≡ (p ∨ q ∨ r ) ∧ (¬q ∨ ¬p ∨ r )

7 / 20

PD Tema 4: Formas normales Forma normal conjuntiva Decisión de validez mediante FNCProcedimiento de decisión de validez mediante FNC
Literales complementarios:
El complementario de un literal L es Lc = ¬p p si L = p; si L = ¬p.

Propiedades de reducción de tautologías:
F1 ∧ · · · ∧ Fn es una tautología syss F1 , . . . , Fn lo son. L1 ∨ · · · ∨ Ln es una tautología syss {L1 , . . . , Ln } contiene algún par de literales complementarios (i.e. existen i, j tales que Li = Lc ). j...