1.Que son formulas en forma normal conjuntiva y disyuntiva
Existen dos tipos de formas normales,
las disyuntivas y las conjuntivas. Las formas normales disyuntivas son
disyunciones de conjunciones de literales, mientras las formas normales
conjuntivas son conjunciones de disyunciones de literales.
Una fórmula A, está en forma normal disyuntiva (fnd) si es de la forma A1 ⅴ A2 ... ⅴ An donde n>=1 y A1, A2 , An son conjunciones de literales.
Una fórmula A, está en forma normal conjuntiva (fnc) si es de la forma A1 ᴧ A2 ... ᴧ An donde n>=1 y A1, A2 , An son disyunciones de literales.
Si A es un literal, puede ser considerado tanto disyunción de literales, como conjunción de literales.
2.Describa el algoritmo de transformacion de forma normal conjuntiva y forma normal disyuntiva
Algoritmo de disyuntiva: Aplicando a una formula F los siguientes pasos se obtiene una formula normal disyuntiva de F, FND(F):
1.Eliminar los bicondicionales aplicando la equivalencia
A<----->B=(A------->B ) ∧ (B--------->A)
Una fórmula A, está en forma normal disyuntiva (fnd) si es de la forma A1 ⅴ A2 ... ⅴ An donde n>=1 y A1, A2 , An son conjunciones de literales.
Una fórmula A, está en forma normal conjuntiva (fnc) si es de la forma A1 ᴧ A2 ... ᴧ An donde n>=1 y A1, A2 , An son disyunciones de literales.
Si A es un literal, puede ser considerado tanto disyunción de literales, como conjunción de literales.
2.Describa el algoritmo de transformacion de forma normal conjuntiva y forma normal disyuntiva
Algoritmo de disyuntiva: Aplicando a una formula F los siguientes pasos se obtiene una formula normal disyuntiva de F, FND(F):
1.Eliminar los bicondicionales aplicando la equivalencia
A<----->B=(A------->B ) ∧ (B--------->A)
2. Eliminar los condicionales usando la equivalencia
A------>B= (¬A V B)
¬(A ∧ B)= ¬A V ¬B
¬(A V B)= ¬A ∧ ¬B
¬¬A= A
4.Interiorizar las conjunciones usando equivalencias
A ∧(B V C)= (A ∧ B) V (A ∧ C)
(A V B ) ∧ C= (A ∧ C) V (B ∧ C)
Algoritmo de conjuntiva: Aplicando a una formula F los siguientes pasos se obtiene una formula normal conjuntiva de F, FND(F):
1.Eliminar los bicondicionales aplicando la equivalencia
A<----->B=(A------->B ) ∧ (B--------->A)
A<----->B=(A------->B ) ∧ (B--------->A)
2. Eliminar los condicionales usando la equivalencia
A------>B= (¬A V B)
¬(A ∧ B)= ¬A V ¬B
¬(A V B)= ¬A ∧ ¬B
¬¬A= A
4.Interiorizar las conjunciones usando equivalencias
A V(B ∧ C)= (A V B) ∧ (A V C)
(A ∧ B ) V C= (A V C)∧ (B V C)
3.Ejemplos
1.
¬(P∧(Q----->R))
¬(P∧(¬Q V R)
¬PV¬(¬Q V R)
¬PV(¬¬Q∧R)
¬PV(Q∧¬R)
(¬PVQ)∧(¬PV¬R)
2.
(P→ Q ∨ (Q→ P)
(¬P ∨ Q) ∨ (¬Q ∨ P) [por (2)]
¬P ∨ Q ∨ ¬Q ∨ P
3.
(p ↔ q) → r
(p → q) ∧ (q → p) → r [por (1)]
¬((¬p ∨ q) ∧ (¬q ∨ p)) ∨ r [por (2)]
(¬(¬p ∨ q) ∨ ¬(¬q ∨ p)) ∨ r [por (3)]
((¬¬p ∧ ¬q) ∨ (¬¬q ∧ ¬p)) ∨ r [por (4)]
((p ∧ ¬q) ∨ (q ∧ ¬p)) ∨ r [por (5)]
(((p ∧ ¬q) ∨ q) ∧ ((p ∧ ¬q) ∨ ¬p)) ∨ r [por (6)]
(((p ∨ q) ∧ (¬q ∨ q)) ∧ ((p ∨ ¬p) ∧ (¬q ∨ ¬p))) ∨ r [por (7)]
(((p ∨ q) ∧ (¬q ∨ q)) ∨ r) ∧ (((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ r) [por (7)]
(((p ∨ q) ∨ r) ∧ ((¬q ∨ q) ∨ r)) ∧ (((p ∨ ¬p) ∨ r) ∧ ((¬q ∨ ¬p) ∨ r)) [por (7)]
(p ∨ q ∨ r) ∧ (¬q ∨ q ∨ r) ∧ (p ∨ ¬p ∨ r) ∧ (¬q ∨ ¬p ∨ r)
≡ (p ∨ q ∨ r) ∧ (¬q ∨ ¬p ∨ r)
FORMA DISYUNTIVA
1
¬(p ∧ (q → r))
¬(p ∧ (¬q ∨ r)) [por (2)]
¬p ∨ ¬(¬q ∨ r) [por (3)]
¬p ∨ (¬¬q ∧ ¬r) [por (4)]
¬p ∨ (q ∧ ¬r) [por (5)]
2
¬(¬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)
Comentarios
Publicar un comentario