Menu Close

Simplificación de expresiones booleanas

José A. Alonso,

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)
Avanzado
, ,

Una solución de “Simplificación de expresiones booleanas”

  1. Responder
    Diego 
    valor :: Expr -> Bool -> Bool
valor X b = b
valor V _ = True
valor F _ = False
valor (Neg e) b = not (valor e b)
valor (Dis e f) b = (valor e b) || (valor f b)
 
simplifica :: Expr -> Expr
simplifica (Neg V) = F
simplifica (Neg F) = V
simplifica (Neg X) = Neg X
simplifica (Neg (Neg q)) = simplifica q
simplifica (Neg q)
  | q == sq   = Neg q 
    -- Nos aseguramos así de que no quede atrapado en una recursión infinita
  | otherwise = simplifica (Neg sq)
    where sq = simplifica q
simplifica (Dis V q) = V
simplifica (Dis F q) = simplifica q
simplifica (Dis q V) = V
simplifica (Dis q F) = simplifica q
simplifica (Dis q r)
  | sq == sr         = sq  -- Dis q q = q
  | (q,r) == (sq,sr) = Dis sq sr
  | otherwise        = simplifica (Dis sq sr)
    where (sq, sr) = (simplifica q, simplifica r)
simplifica q = q
 
-- La propiedad es
prop_simplifica :: Expr -> Bool -> Bool
prop_simplifica p i = valor p i == valor (simplifica p) i
 
-- La comprobación es
-- quickCheck prop_simplifica
-- +++ OK, passed 100 tests.

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.