Simplificación de expresiones booleanas
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):
|
1 2 3 4 5 6 |
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
|
1 2 |
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,
|
1 2 3 4 |
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:
|
1 2 3 4 5 6 7 8 |
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,
|
1 2 3 4 5 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
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) |