El siguiente tipo de dato algebraico representa las expresiones booleanas construidas con una variable (X), las constantes verdadera (V) y falsa (F), la negación (Neg) y la disyunción (Dis):
data Expr = X | V | F | Neg Expr | Dis Expr Expr deriving (Eq, Ord, Show) |
Por ejemplo, la expresión (¬X v V) se representa por (Dis (Neg X) V).
Definir las funciones
valor :: Expr -> Bool -> Bool simplifica :: Expr -> Expr |
tales que (valor p i) es el valor de la expresión p cuando se le asigna a X el valor i. Por ejemplo,
valor (Neg X) True == False valor (Neg F) True == True valor (Dis X (Neg X)) True == True valor (Dis X (Neg X)) False == True |
y (simplifica p) es la expresión obtenida aplicándole a p las siguientes reglas de simplificación:
Neg V = F Neg F = V Neg (Neg q) = q Dis V q = V Dis F q = q Dis q V = V Dis q F = F Dis q q = q |
Por ejemplo,
simplifica (Dis X (Neg (Neg X))) == X simplifica (Neg (Dis (Neg (Neg X)) F)) == Neg X simplifica (Dis (Neg F) F) == V simplifica (Dis (Neg V) (Neg (Dis (Neg X) F))) == X simplifica (Dis (Neg V) (Neg (Dis (Neg (Neg X)) F))) == Neg X |
Comprobar con QuickCheck que para cualquier expresión p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).
Nota: Escribir las soluciones usando la siguiente plantilla que contiene un generador de expresiones booleanas
import Test.QuickCheck import Control.Monad data Expr = X | V | F | Neg Expr | Dis Expr Expr deriving (Eq, Ord, Show) valor :: Expr -> Bool -> Bool valor = undefined simplifica :: Expr -> Expr simplifica = undefined -- La propiedad es prop_simplifica :: Expr -> Bool -> Bool prop_simplifica p i = undefined -- La comprobación es -- Generador de expresións instance Arbitrary Expr where arbitrary = sized expr where expr n | n <= 0 = atom | otherwise = oneof [ atom , liftM Neg subexpr , liftM2 Dis subexpr subexpr ] where atom = oneof [elements [X,V,F]] subexpr = expr (n `div` 2) |
Soluciones
import Test.QuickCheck import Control.Monad data Expr = X | V | F | Neg Expr | Dis Expr Expr deriving (Eq, Ord, Show) valor :: Expr -> Bool -> Bool valor X i = i valor V _ = True valor F _ = False valor (Neg p) i = not (valor p i) valor (Dis p q) i = valor p i || valor q i simplifica :: Expr -> Expr simplifica X = X simplifica V = V simplifica F = F simplifica (Neg p) = negacion (simplifica p) where negacion V = F negacion F = V negacion (Neg p) = p negacion p = Neg p simplifica (Dis p q) = disyuncion (simplifica p) (simplifica q) where disyuncion V q = V disyuncion F q = q disyuncion q V = V disyuncion q F = q disyuncion p q | p == q = p | otherwise = Dis p q -- La propiedad es prop_simplifica :: Expr -> Bool -> Bool prop_simplifica p i = valor (simplifica p) i == valor p i -- La comprobación es -- ghci> quickCheck prop_simplifica -- +++ OK, passed 100 tests. -- Generador de expresiones instance Arbitrary Expr where arbitrary = sized expr where expr n | n <= 0 = atom | otherwise = oneof [ atom , liftM Neg subexpr , liftM2 Dis subexpr subexpr ] where atom = oneof [elements [X,V,F]] subexpr = expr (n `div` 2) |
Una solución de “Simplificación de expresiones booleanas”