Fórmula dual

José A. Alonso

07-01-2016

Las fórmulas proposicionales construidas con las constantes verdadero (⊤), falso (⊥), las variables proposicionales y las conectivas de negación (¬), conjunción (∧) y disyunción (∨) se pueden definir usando el siguiente tipo de datos

data Prop = Const Bool
          | Var Char
          | Neg Prop
          | Conj Prop Prop
          | Disj Prop Prop
          deriving (Eq, Show)

Por ejemplo, la fórmula (A ∧ ⊥) ∨ (⊤ ∧ B) se representa por

Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B'))

La fórmula dual de una fórmula p es la fórmula obtenida intercambiando en p las ∧ por ∨ y también las ⊤ por ⊥. Por ejemplo, la dual de (A ∧ ⊥) ∨ (⊤ ∧ B) es (A ∨ ⊤) ∧ (⊥ ∨ B)

Definir la función

dual :: Prop -> Prop

tal que (dual p) es la dual de p. Por ejemplo,

λ> dual (Disj (Conj (Var 'A') (Const False)) (Conj (Const True) (Var 'B')))
Conj (Disj (Var 'A') (Const True)) (Disj (Const False) (Var 'B'))

Soluciones

data Prop = Const Bool
          | Var Char
          | Neg Prop
          | Conj Prop Prop
          | Disj Prop Prop
          deriving (Eq, Show)

-- 1ª solución
-- ===========

dual1 :: Prop -> Prop
dual1 (Const True)  = Const False
dual1 (Const False) = Const True
dual1 (Var x)       = Var x
dual1 (Neg p)       = Neg  (dual1 p)
dual1 (Conj p q)    = Disj (dual1 p) (dual1 q)
dual1 (Disj p q)    = Conj (dual1 p) (dual1 q)

-- 2ª solución
-- ===========

dual2 :: Prop -> Prop
dual2 (Const b)  = Const (not b)
dual2 (Conj p q) = Disj (dual2 p) (dual2 q)
dual2 (Disj p q) = Conj (dual2 p) (dual2 q)
dual2 p          = p