Menu Close

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):

   data Expr = X
             | V
             | F
             | Neg Expr
             | Dis Expr Expr
             deriving (Eq, Ord)

Por ejemplo, la fórmula (¬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 fórmula 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 una 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 fórmula p y cualquier booleano i se verifica que (valor (simplifica p) i) es igual a (valor p i).

Para la comprobación, de define el generador

   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)

que usa las funciones liftM y liftM2 de la librería Control.Monad que hay que importar al principio.

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
--    λ> quickCheck prop_simplifica
--    +++ OK, passed 100 tests.
 
-- Generador de fórmulas
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)

Pensamiento

¿Dices que nada se pierde?
Si esta copa de cristal
se me rompe, nunca en ella
beberé, nunca jamás.

Antonio Machado

Avanzado

6 soluciones de “Simplificación de expresiones booleanas

  1. frahidzam
    import Control.Monad (liftM, liftM2)
     
    data Expr = X | V | F | Neg Expr | Dis Expr Expr deriving (Show,Eq,Ord)
     
    valor :: Expr -> Bool -> Bool
    valor X i = i
    valor V _ = True
    valor F _ = False
    valor (Neg x) i = not (valor x i)
    valor (Dis a b) i = valor a i || valor b i
     
    simplifica :: Expr -> Expr
    simplifica X = X
    simplifica V = V
    simplifica F = F
    simplifica (Neg q) = negate (simplifica q)
     where negate V = F
           negate F = V
           negate (Neg q) = q
           negate q = (Neg q)
    simplifica (Dis a b) = disyuncion (simplifica a) (simplifica b)
      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
     
    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)
     
    prop_bool :: Expr -> Bool -> Bool
    prop_bool p i = valor (simplifica p) i == valor p i
  2. adogargon
    valor :: Expr -> Bool -> Bool
    valor X n = n
    valor (Dis e f) n =  (valor f n) || (valor e n)
    valor (Neg e) n = not (valor e n)
    valor F _ = False
    valor V _ = True
     
    simplifica :: Expr -> Expr
    simplifica (Dis _ e) = e
    simplifica (Neg (Neg e)) = e
    simplifica (Dis e V) = V
    simplifica (Dis e F) = F
    simplifica (Neg V) = F
    simplifica (Neg F) = V
    simplifica e = e
     
    comprobacion :: Expr -> Bool -> Bool
    comprobacion e n = valor e n == valor (simplifica e) n
    • adogargon
      --La definicion de simplifica es incorrecta. Esta funciona bien ya:
      listaExp :: Expr -> [Expr]
      listaExp X = [X]
      listaExp V = [V]
      listaExp F = [F]
      listaExp (Neg e) = (Neg e):listaExp e
      listaExp (Dis e f) = [(Dis e f)]++listaExp e ++ listaExp f
       
      reglas :: Expr -> Expr
      reglas V = V
      reglas F = F
      reglas X = X
      reglas (Dis V e) = V
      reglas (Dis F e) =  e
      reglas (Neg (Neg e)) =  e
      reglas (Dis e F) =   e
      reglas (Dis e V) = V
      reglas (Dis e f) | e == f =   e
                       | otherwise = Dis e f
      reglas (Neg V) = F
      reglas (Neg F) = V
      reglas (Neg e) | irreducible e = Neg e
                     | otherwise = Neg (reglas e)
       
       
       
      irreducible :: Expr -> Bool
      irreducible e = map reglas (listaExp e) == listaExp e 
       
      simplifica :: Expr -> Expr
      simplifica (Neg e) | irreducible e && irreducible (Neg e) = Neg e
                         | not (irreducible e) = simplifica ( Neg ( simplifica e))
                         | otherwise = reglas (Neg e)
      simplifica (Dis e f) | irreducible e && irreducible f = reglas (Dis e f)
                           | not (irreducible e) = simplifica ( Dis (simplifica e) f)
                           | otherwise  = simplifica ( Dis e (simplifica f))
  3. luipromor
    valor      :: Expr -> Bool -> Bool
    valor X a = a
    valor F _ = False
    valor V _ = True
    valor (Neg x) a = not (valor x a)
    valor (Dis x y ) a = valor x a || valor y a
     
    simplifica :: Expr -> Expr
    simplifica X = X
    simplifica V = V
    simplifica F = F
    simplifica (Dis x y ) | x == V || x == F = simplifica y
                          | y == V || y == F = simplifica x
                          | x == y = simplifica x
                          | otherwise =  simplifica (Dis (simplifica x) (simplifica y))
    simplifica (Neg (Neg X)) = X                        
    simplifica (Neg x) | x == V = F
                       | x == F = V
                       | x == X = Neg X
                       | otherwise = simplifica (Neg (simplifica x))
    prop_ :: Expr -> Bool -> Bool
    prop_ x i = valor x i == valor (simplifica x) i
  4. diepedlop

    En lugar de seguir las reglas de simplificación podemos obtener la expresión simplificada observando la salida de valor.

    valor :: Expr -> Bool -> Bool
    valor X p = p
    valor V _ = True
    valor F _ = False
    valor (Neg e) p = not (valor e p)
    valor (Dis e f) p =  valor e p || valor f p
    
    simplifica :: Expr -> Expr
    simplifica e = case (valor e True, valor e False) of
        (True, True) -> V
        (False, False) -> F
        (True, False) -> X
        (False, True) -> Neg X
    

  5. javmarcha1
    import Control.Monad
     
    data Expr = X
                 | V
                 | F
                 | Neg Expr
                 | Dis Expr Expr
                 deriving (Eq, Ord)
     
    valor :: Expr -> Bool -> Bool
    valor X x = x
    valor F _ = False
    valor V _ = True
    valor (Neg a) x = not (valor a x)
    valor (Dis a b ) x = valor a x || valor b x
     
    simplifica :: Expr -> Expr
    simplifica X = X
    simplifica V = V
    simplifica F = F
    simplifica (Dis x y ) | x == V || y == V = V
                          | x == F && y == F = F
                          | x == X && y == X = X 
                          | (x == X || y == X) && (x == F || y == F) = X
                          | (x == Neg X || y == Neg X) && (x == F || y == F) = Neg X
                          | x == Neg X && y == Neg X = Neg X
                          | otherwise =  simplifica (Dis (simplifica x) (simplifica y))                      
    simplifica (Neg x) | x == V = F
                       | x == F = V
                       | x == X = Neg X
                       | x == Neg X = X
                       | otherwise = (Neg (simplifica x))
     
    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)
     
    prop_ :: Expr -> Bool -> Bool
    prop_ x i = valor x i == valor (simplifica x) i

Los comentarios están cerrados.